[자료구조/알고리즘] 그래프(Graph)

그래프(Graph)

• 정의
  - 정점과 간선으로 이루어진 자료구조(Cyclic)
• 특징
  - 연결된 정점간의 관계를 표현할 수 있는 자료구조
  • 지하철 노선도, 통신 네트워크, etc ...
• 구조
  정점(Vertex): 각 노드
  간선(Edge): 노드와 노드를 연결하는 선(link, branch)
  인접 정점(Adjacent vertex): 간선 하나를 두고 바로 연결된 정점
  정점의 차수(Degree)
  • 무방향(양방향) 그래프에서 하나의 정점에 인접한 정점의 수
    - 무방향(양방향) 그래프의 모든 정점 차수의 합 = 간선의 수 * 2
    진입 차수(In-Degree): 방향 그래프에서 외부에서 오는 간선의 수
    진출 차수(Out-Degree): 방향 그래프에서 외부로 나가는 간선의 수
    경로 길이(Path Length): 경로를 구선하는데 사용된 간선의 수
    단순 경로(Simple Path): 경로 중에서 반복되는 정점이 없는 경우
    사이클(Cycle): 단순 경로의 시작 정점과 끝 정점이 동일한 경우

그래프와 트리의 차이

	그래프	트리
개요	노드와 간선으로 이루어진 자료구조	그래프의 한 종류
방향성	방향 그래프, 무방향(양방향) 그래프	방향 그래프
사이클	Cyclic	Acyclic
모델	네트워크 모델	계층 모델
루트 노드	X	O
부모-자식 관계	X	O
간선 수	그래프에 따라 상이	N - 1개
순회	DFS, BFS	Pre-,In-,Post-Order/Level Order
경로	2개 이상의 경로 가능	두 노드 간의 경로는 1개

종류

• 무방향 그래프
  - 간선에 방향이 없는 그래프(양방향 이동 가능)
  - 정점 A - B 간선의 표현: (A,B) = (B,A)
• 방향 그래프
  - 간선의 방향이 있는 그래프(해당 방향으로만 이동 가능)
  - 정점 A -> B 간선의 표현: <A,B> $\neq$ <B,A>
  
• 가중치 그래프
  - 간선에 값이 있는 그래프(이동 비용 or 이동 거리)
• 완전 그래프
  - 모든 정점이 서로 연결되어 있는 그래프
  - 정점이 N개일 경우 간선의 수는 n(n-1)/2개
  

그래프 탐색

깊이 우선 탐색 DFS(Depth First Search)

• 각 노드 방문 여부를 체크할 배열과 스택을 이용해 구현

너비 우선 탐색 BFS(Breath First Search)

• 각 노드 방문 여부를 체크할 배열과 큐를 이용해 구현

그래프 구현

인접 행렬(Adjacency Matrix)

• 2차원 배열을 이용
• 간선 정보의 확인과 업데이트가 빠름 O(1)
• 인접 행렬을 위한 메모리 공간 차지
  

인접 리스트(Adjacency List)

• 연결 리스트를 이용
• 메모리 사용량이 상대적으로 적고, 노드의 추가 삭제가 빠름
• 간선 정보 확인이 상대적으로 느림
  

인접 행렬 vs 인접 리스트

• 노드의 개수가 적고 간선의 수가 많을 때
  인접 행렬 > 인접 리스트
• 노드의 개수가 많고 간선의 수가 적을 때
  인접 행렬 < 인접 리스트

	인접 행렬	인접 리스트
특정 간선 검색	O(1)	O(degree(V))
정점의 차수 계산	O(N)	O(degree(V))
전체 노드 탐색	O($N^2$)	O(E)
메모리	N x N	N + E

N: 전체 정점 개수
E: 전체 간선 개수
V: 해당 노드의 차수

구현

• 인접 행렬을 이용한 구현

class AdjacencyMatrix {
    char[] vertices;
    int[][] matrix;
    int elementCnt;

    public AdjacencyMatrix(int size) {
        this.vertices = new char[size];
        this.matrix = new int[size][size];
        this.elementCnt = 0;
    }

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

    public void addVertex(char data) {
        if (this.isFull()) {
            System.out.println("The matrix is already full");
            return;
        }

        this.vertices[this.elementCnt++] = data;
    }

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

    public void addDirectedEdge(int x, int y) {
        this.matrix[x][y] = 1;
    }

    public void deleteEdge(int x, int y) {
        this.matrix[x][y] = 0;
        this.matrix[y][x] = 0;
    }

    public void deleteDirectedEdge(int x, int y) {
        this.matrix[x][y] = 0;
    }

    public void printMatrix() {
        System.out.print("  ");
        for (char v : this.vertices) {
            System.out.print(v + " ");
        }
        System.out.println();

        for (int i = 0; i < this.elementCnt; i++) {
            System.out.print(this.vertices[i] + " ");
            for (int j = 0; j < this.elementCnt; j++) {
                System.out.print(this.matrix[i][j] + " ");
            }
            System.out.println();
        }
    }
}

public class Main {
    public static void main(String[] args) {
        AdjacencyMatrix adjMatrix = new AdjacencyMatrix(4);

        adjMatrix.addVertex('A');
        adjMatrix.addVertex('B');
        adjMatrix.addVertex('C');
        adjMatrix.addVertex('D');

        adjMatrix.addEdge(0, 1);
        adjMatrix.addEdge(0, 2);
        adjMatrix.addEdge(1, 2);
        adjMatrix.addEdge(1, 3);
        adjMatrix.addEdge(2, 3);

        adjMatrix.printMatrix();
    }
}

• 인접 리스트를 이용한 구현

class AdjacencyList {
    char[] vertices;
    Node[] nodes;
    int elementCnt;

    public AdjacencyList(int size) {
        this.vertices = new char[size];
        this.nodes = new Node[size];
        this.elementCnt = 0;
    }

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

    public void addVertex(char data) {
        if (this.isFull()) {
            System.out.println("The matrix is already full");
            return;
        }
        this.vertices[this.elementCnt++] = data;
    }

    public void addEdge(int x, int y) {
        this.nodes[x] = new Node(y, this.nodes[x]);
        this.nodes[y] = new Node(x, this.nodes[y]);
    }

    public void addDirectedEdge(int x, int y) {
        this.nodes[x] = new Node(y, this.nodes[x]);
    }

    public void printList(){
        for (int i = 0; i < this.elementCnt; i++) {
            System.out.print(this.vertices[i] + ": ");

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

public class Solution {
    public static void main(String[] args) {
        AdjacencyList adjList = new AdjacencyList(4);

        adjList.addVertex('A');
        adjList.addVertex('B');
        adjList.addVertex('C');
        adjList.addVertex('D');

        adjList.addEdge(0, 1);
        adjList.addEdge(0, 2);
        adjList.addEdge(1, 2);
        adjList.addEdge(1, 3);
        adjList.addEdge(2, 3);

        adjList.printList();
    }
}