배열과 연결리스트로 Graph 구현 및 기본 개념 정리

ㆍGraph의 구현 ( 인접행렬 )

- 2차원 배열 사용
- 장점 : 간선 정보의 확인과 업데이트가 빠름

- 단점 : 인접 행렬을 위한 메모리 공간 차지

오늘은 비선형자료구조인 그래프의 개념 및 배열과

연결리스트를 통해서 Graph로 간단히 구현해보는 시간을 가지려고 한다.

 

ㆍGraph의 개념

- 정점과 간선으로 이루어진 자료구조(Cycle 0) 

 

ㆍGraph의 구조

1. 정점 (Vertex)
   - 각 노드
2. 간선 (Edge)
   - 노드와 노드를 연결하는 선 (link, branch)
3. 인접정점 (Adjacent vertex)
   - 간선 하나를 두고 바로 연결된 정점
4. 정점의 차수 (Degree)
   - 무방향 그래프에서 하나의 정점에 인접한 정점의 수
5. 무방향 그래프 모든 정점 차수의 합 -> 그래프 간선의 수 2배
6. 진입차수(in-degree)
   - 방향 그래프에서 외부에서 오는 간선의 수
7. 진출차수 (Out-degree)
   - 방향 그래프에서 외부로 나가는 간선의 수
8. 경로길이 (Path length)
   - 경로를 구성하는데 사용된 간선의 수
9. 단순경로 (Simple path)
   - 경로 중에서 반복되는 정점이 없는 경우
10. 사이클 (Cycle)
    - 단순 경로의 시작 정점과 끝 정점이 동일한 경우

 

ㆍGraph의 종류

1. 무방향 그래프
   - 간선에 방향이 없는 그래프 (양방향 이동 가능)
   - 정점 A-B 간선의 표현 (A, B) = (B, A)
2. 방향 그래프
   - 간선에 방향이 있는 그래프 (양방향 이동 불가능)
   - 정점 A -> B 간선의 표현 (A, B) != (B, A)
3. 가중치 그래프
   - 간선에 값이 있는 그래프 (이동비용)
4. 완전 그래프
   - 모든 정점이 서로 연결되어 있는 그래프
   - 정점이 N개일 때, 간선이 수는 n(n - 1)/2

 

ㆍGraph의 탐색

1. 깊이우선탐색 = DFS (Depth First Search)
   - 각 노드에 방문했는지 여부르 체크할 배열과 스택 이용해서 구현
2. 너비우선탐색 = BFS (Breath First Search)
   - 각 노드에 방문했는지 여부를 체크할 배열과 큐 이용해서 구현

 

ㆍGraph의 구현 ( 인접행렬 )

- 2차원 배열 사용
- 장점 : 간선 정보의 확인과 업데이트가 빠름

- 단점 : 인접 행렬을 위한 메모리 공간 차지

class GraphArray {
    char[] vertices;
    int[][] adjMat;
    int eleCnt;

    GraphArray() {}

    public GraphArray(int size) {
        this.vertices = new char[size];
        this.adjMat = new int[size][size];
        this.eleCnt = 0;
    }

    public boolean isFull() {
        return this.eleCnt == this.vertices.length;
    }

    public void addVertex(char data) {
        if (isFull()) {
            System.out.println("Graph is Full");
            return;
        }

        vertices[eleCnt++] = data;
    }

    public void addEdge(int x, int y) {
        adjMat[x][y] = 1;
        adjMat[y][x] = 1;
    }

    public void addDirectEdge(int x, int y) {
        adjMat[x][y] = 1;
    }

    public void removeEdge(int x, int y) {
        adjMat[x][y] = 0;
        adjMat[y][x] = 0;
    }

    public void removeDirectEdge(int x, int y) {
        adjMat[x][y] = 0;
    }

    public void printAdjMat() {
        for (int i = 0; i < adjMat.length; i++) {
            for (int j = 0; j < adjMat.length; j++) {
                System.out.print(adjMat[i][j] + " ");
            }
            System.out.println();
        }
    }

    public void dfs(int id) {
        boolean[] isVisit = new boolean[eleCnt];
        Stack<Integer> stack = new Stack<>();

        stack.push(id);
        isVisit[id] = true;

        while (!stack.isEmpty()) {
            int num = stack.pop();
            System.out.print(vertices[num] + " ");

            for (int i = eleCnt - 1; i >= 0; i--) {
                if (adjMat[num][i] == 1 && !isVisit[i]) {
                    stack.push(i);
                    isVisit[i] = true;
                }
            }
        }
        System.out.println();
    }

    public void bfs(int id) {
        boolean[] isVisit = new boolean[eleCnt];
        LinkedList<Integer> linkedList = new LinkedList<>();

        linkedList.addLast(id);
        isVisit[id] = true;

        while (!linkedList.isEmpty()) {
            int num = linkedList.removeFirst();
            System.out.print(vertices[num] + " ");

            for (int i = eleCnt - 1; i >= 0; i--) {
                if (adjMat[num][i] == 1 && !isVisit[i]) {
                    linkedList.addLast(i);
                    isVisit[i] = true;
                }
            }
        }
        System.out.println();
    }
}

 

ㆍGraph의 구현 ( 인접리스트)

- 연결리스트 사용
- 장점 : 메모리사용이 상대적으로 적고, 노드의 추가 삭제가 빠름

- 단점 : 간선 정보 확인이 상대적으로 오래걸림

class NodeGraph {
    int id;
    NodeGraph next;

    public NodeGraph(int id, NodeGraph next) {
        this.id = id;
        this.next = next;
    }
}

class GraphLinkedList {
    char[] vertices;
    NodeGraph[] adjList;
    int eleCnt;

    GraphLinkedList() {}
    GraphLinkedList(int size) {
        vertices = new char[size];
        adjList = new NodeGraph[size];
        eleCnt = 0;
    }

    public boolean isFull() {
        return eleCnt == vertices.length;
    }

    public void addVertex(char data) {
        if (isFull()) {
            System.out.println("Graph is Full");
            return;
        }

        vertices[eleCnt++] = data;
    }

    public void addEdge(int x, int y) {
        adjList[x] = new NodeGraph(y, adjList[x]);
        adjList[y] = new NodeGraph(x, adjList[y]);
    }
    public void addDirectEdge(int x, int y) {
        adjList[x] = new NodeGraph(y, adjList[x]);
    }
    public void printAdjMat() {
        for (int i = 0; i < eleCnt; i++) {
            NodeGraph cur = adjList[i];

            while (cur != null) {
                System.out.print(vertices[cur.id] + " ");
                cur = cur.next;
            }
            System.out.println();
        }
    }

    public void dfs(int id) {
        boolean[] isVisit = new boolean[eleCnt];
        Stack<Integer> stack = new Stack<>();

        isVisit[id] = true;
        stack.push(id);

        while (!stack.isEmpty()) {
            int num = stack.pop();
            NodeGraph cur = adjList[num];
            System.out.print(vertices[num] + " ");

            while (cur != null) {
                if (!isVisit[cur.id]) {
                    stack.push(cur.id);
                    isVisit[cur.id] = true;
                }
                cur = cur.next;
            }
        }
        System.out.println();
    }
    public void bfs(int id) {
        boolean[] isVisit = new boolean[eleCnt];
        LinkedList<Integer> linkedList = new LinkedList<>();

        isVisit[id] = true;
        linkedList.addLast(id);

        while (!linkedList.isEmpty()) {
            int num = linkedList.removeFirst();
            NodeGraph cur = adjList[num];
            System.out.print(vertices[num] + " ");

            while (cur != null) {
                if (!isVisit[cur.id]) {
                    linkedList.addLast(cur.id);
                    isVisit[cur.id] = true;
                }
                cur = cur.next;
            }
        }
        System.out.println();
    }
}

 

ㆍ인접행렬 vs 인접리스트

	인접행렬	인접리스트
사용하면 좋을 때	간선 개수 ↑ /  노드 수 ↓	간선 개수 ↓ / 노드 수 ↑
특정간선검색	O(1)	O(degree(V))
정점의 차수계산	O(N)	O(degree(V))
전체 노드 계산	O(N*N)	O(E)
메모리	N * N	N + E