[알고리즘] 01. Graph

첫 알고리즘 공부를 시작했을 때, Graph 이론에 대해 노트에 정리한 것을 가지고 왔다.

 

 

 

 

이후에 java로 Graph를 아래와 같이 구현했다.

 

    public class Graph {

        private static int numOfVertex;
        private static int numOfEdge;
        public static Scanner input = new Scanner(System.in);

        public Graph(int numOfVertex, int numOfEdge){
            this.numOfVertex = numOfVertex;
            this.numOfEdge = numOfEdge;
        }

        public static int[][] adjacencyMatrix() {
            int[][] vertex = new int[numOfVertex][numOfVertex];
            for (int i = 0; i < numOfVertex; i++)
                vertex[input.nextInt()][input.nextInt()] = 1;
            return vertex;
        }

        public static ArrayList[] adjacencyList() {
            ArrayList<Integer> [] head = new ArrayList[numOfVertex];
            for (int i = 0; i < numOfVertex; i++)
                head[i] = new ArrayList<>();

            for (int i = 0; i < numOfEdge; i++)
                head[input.nextInt()].add(input.nextInt());

            return head;
        }

        public static Node[] adjacencyMultiList() {
            Node [] head = new Node[numOfVertex];
            Node [] link = new Node[numOfVertex +1];
            for (int p = 0; p < numOfVertex; p++)
                link[p] = new Node(input.nextInt(), input.nextInt());

            for (int p = 0; p < numOfVertex; p++){
                link[p].i_link = link[input.nextInt()];
                link[p].j_link = link[input.nextInt()];
            }

            for (int p = 0; p < numOfVertex; p++) {
                head[p] = link[input.nextInt()];
            }
            return head;
        }

        private static class Node{
            public boolean mark;
            public int i, j;
            public Node i_link, j_link;

            public Node(int i, int j){
                this.i = i;
                this.j = j;
            }
        }
    }