演算法第一次作業 Java版

AlgroithmHW1.java

package algroithmhw1;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

/**
 *
 * @author Takeshi
 */
public class AlgroithmHW1 {

    public static void main(String[] args) throws FileNotFoundException {
        Scanner scanner = new Scanner(System.in);
        String sInput;

        int numVertices, u, v, vertexStartNo;

        if (args.length >= 2) {
            sInput = args[1];
        } else {
            System.out.println("Enter the filename of the graph: ");
            sInput = scanner.next();
        }

        File inFile = new File(sInput);

        if (!inFile.exists()) {
            System.out.println("Error: Failed to open " + sInput + " for input! \n");
            return;
        }

        if (!inFile.canRead()) {
            System.out.println("Error: Empty input file! \n");
            return;
        }

        Scanner fileScanner = new Scanner(inFile);

        numVertices = fileScanner.nextInt();
        int[][] matrix = new int[numVertices][numVertices];


        while (fileScanner.hasNext()) {
            u = fileScanner.nextInt();
            v = fileScanner.nextInt();
            if (u < numVertices && v < numVertices) {
                matrix[u][v] = 1;
            }
        }
        fileScanner.close();

        Graph graph = new Graph(matrix, numVertices);

        while (true) {
            System.out.println("");
            System.out.println("Enter L to List All Edges, F to Find Back Edges,");
            System.out.println("      A to Add Edges, R to Remove Edges,");
            System.out.println("      B to BFS, D to DFS, S to Sort Topologically, or X to Exit");
            sInput = scanner.next();
            sInput = sInput.toUpperCase();
            if (sInput.equals("L")) {
                graph.showAdjMatrix();
            } else if (sInput.equals("B")) {
                System.out.println("Enter start vertex #: ");
                vertexStartNo = scanner.nextInt();


                if (vertexStartNo < numVertices) {
                    graph.doBFS(vertexStartNo);
                } else {
                    System.out.println("Error: Vertex no out of range!");
                }

            } else if (sInput.equals("D")) {
                System.out.println("Enter start vertex #: ");
                vertexStartNo = scanner.nextInt();

                if (vertexStartNo < numVertices) {
                    graph.doDFS(vertexStartNo);
                } else {
                    System.out.println("Error: Vertex # out of range!");
                }

            } else if (sInput.equals("F")) {
                System.out.println("Enter start vertex #:");
                vertexStartNo = scanner.nextInt();


                if (vertexStartNo < numVertices) {
                    System.out.println("Back edges:");

                    graph.doFindBackEdges(vertexStartNo);

                } else {
                    System.out.println("Error: Vertex # out of range!");
                }

            } else if (sInput.equals("S")) {
                System.out.print("Topological order by DFS");
                graph.doTopologicalSort_DFS();
                System.out.println("Topological order by DBO");
                graph.doTopologicalSort_DBO();
            } else if (sInput.equals("R")) {
                System.out.println("Enter start vertex #:");
                u = scanner.nextInt();
                System.out.println("Enter end vertex #:");
                v = scanner.nextInt();
                graph.doRemoveEdge(u, v);
            } else if (sInput.equals("A")) {
                System.out.println("Enter start vertex #:");
                u = scanner.nextInt();
                System.out.println("Enter end vertex #:");
                v = scanner.nextInt();

                if (u < numVertices && v < numVertices) {
                    graph.addEdge(u, v);
                } else {
                    System.out.println("Error: Vertex # out of range!");
                }

            } else if (sInput.equals("X")) {

                break;
            } else {
                System.out.println("Unknown command!");

            }
        }

    }
}

Graph.java

package algroithmhw1;


import java.util.LinkedList;
import java.util.Queue;

/**
 *
 * @author Takeshi
 */
public class Graph {

    int[][] matrix;
    int numVertices;
    /**
     * initial grapg by adjacency matrix and number of vertices
     * @param matrix
     * @param numVertices 
     */
    public Graph(int[][] matrix, int numVertices) {
        this.matrix = matrix;
        this.numVertices = numVertices;
    }
    
    /**
     * add a direct edge (uv)
     * @param u
     * @param v 
     */
    void addEdge(int u, int v) {
        if (matrix[ u][ v] == 0) {
            matrix[ u][ v] = 1;
            System.out.println("Edge ( " + u + ", " + v + " ) added!");

        } else {
            System.out.println("Edge ( " + u + ", " + v + " ) already existed!");

        }
    }
    
    /**
     * adjacency matrix
     */
    void showAdjMatrix() {
        int r, c;
        System.out.print("     ");
        for (c = 0; c < numVertices; c++) {
            System.out.print("[" + c + "] ");
        }
        for (r = 0; r < numVertices; r++) {
            System.out.print("[" + r + "]");
            for (c = 0; c < numVertices; c++) {
                System.out.print(matrix[r][c] + " ");
            }
            System.out.println("");
        }
    }

    /**
     * Use BFS(Breadth-first search) to show this matrix
     * @param vertexNo vertex which is the first vertex to search
     */
    void doBFS(int vertexNo) {
        Queue<Integer> myQueue = new LinkedList<Integer>();
        boolean[] visited = new boolean[numVertices];

        for (int c = 0; c < numVertices; c++) {
            visited[c] = false;
        }

        myQueue.add(vertexNo);

        while (!myQueue.isEmpty()) {
            int v = myQueue.poll();
            System.out.print(" v" + v);
            for (int c = 0; c < numVertices; c++) {
                if (matrix[v][c] == 1 && !visited[c]) {
                    myQueue.add(c);
                    visited[c] = true;
                }
            }
        }
    }

    /**
     * Use DFS(Depth-first search) to show this graph by recursive
     * @param vertexNo vertex which is the first vertex to search
     * @param visited a boolean array to show which vertices visited and which doesn't
     */
    void doDFS_Recu(int vertexNo, boolean[] visited) {
        System.out.println(" v" + vertexNo);
        for (int c = 0; c < numVertices; c++) {
            if (matrix[vertexNo][c] == 1 && !visited[c]) {
                visited[c] = true;
                doDFS_Recu(c, visited);
            }
        }
    }

    /**
     * Use DFS(Depth-first search) to show this graph by iterator
     * @param vertexNo vertex which is the first vertex to search
     * @param visited a boolean array to show which vertices visited and which doesn't
     */
    void doDFS_Iter(int vertexNo, boolean[] visited) {
        System.out.println("Not Implement Yet!");
    }

    /**
     * do DFS by two method
     * @param verticesNo vertex which is the first vertex to search
     */
    void doDFS(int verticesNo) {
        boolean[] visited = new boolean[numVertices];

        for (int c = 0; c < numVertices; c++) {
            visited[c] = false;
        }
        System.out.print("DFS_Recu:");
        doDFS_Recu(verticesNo, visited);

        for (int c = 0; c < numVertices; c++) {
            visited[c] = false;
        }
        System.out.print("DFS_Iter:");
        doDFS_Iter(verticesNo, visited);

    }
    
    /**
     * find back edes to vertex
     * @param verticesNo vertex which is the target vertex
     */
    void doFindBackEdges(int verticesNo) {
        System.out.println("Not Implement Yet!");
    }
    
    /**
     * remove an edge (uv)
     * @param u start vertex
     * @param v end vertex
     */
    void doRemoveEdge(int u, int v) {
        System.out.println("Not Implement Yet!");
    }

    /**
     * To show TopologicalSort by using DFS algorithm
     */
    void doTopologicalSort_DFS() {
        System.out.println("Not Implement Yet!");
    }

    /**
     * To show TopologicalSort by using DBO algorithm
     */
    void doTopologicalSort_DBO() {
        System.out.println("Not Implement Yet!");
    }
}