[자료구조] 그래프(graph)

 

 

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

 

 

그래프(graph)

• 객체 사이의 연결 관계를 표현할 수 있는 자료구조
• 정점(vertex)과 간선(edge)들의 유한 집합

 

 

용어 정리

• 정점 : 여러 가지 특성을 가질 수 있는 객체를 의미
  ex) V(G) : 그래프 G의 정점들의 집합
• 정점의 차수(degree) : 인접 정점의 개수
  인접 정점(adjacent vertex) : 간선에 의해 직접 연결된 정점
• 간선 : 링크(link)라고도 한다. 간선의 종류에 따라 무방향 그래프와 방향 그래프로 구분된다.
  ex) E(G) : 그래프 G의 간선들의 집합
  - 브리지(bridge) : 제거하면 정점과의 연결이 끊어지는 간선
  
  
• 단순 경로(simple path) : 반복되는 간선이 없는 경로
• 사이클(cycle) : 시작 정점과 종료 정점이 동일한 단순 경로

 

 

그래프의 종류

• 무방향 그래프(undirected graph) : 간선이 양방향으로 갈 수 있는 그래프
   ex) (A, B) : 정점 A와 정점 B를 연결하는 간선.
         (A, B) == (B, A)
  ``무방향 그래프의 모든 정점의 차수합 == 간선 * 2`` (간선이 두 개의 정점에 인접하기 때문)
• 방향 그래프(directed graph) : 간선에 방향성이 존재하는 그래프. 간선은 한쪽 방향으로만 갈 수 있다.
   ex) <A, B> : 정점 A에서 정점 B로만 갈 수 있는 간선
         <A, B> != <B, A>
  - 진입 차수(in-degree) : 외부에서 오는 간선의 개수
  - 진출 차수(out-degree) : 외부로 향하는 간선의 개수
• 가중치 그래프(weighted graph), 네트워크(network) : 간선에 비용이나 가중치가 할당된 그래프
• 부분 그래프(subgraph) : 어떤 그래프의 정점의 일부와 간선의 일부로 이뤄진 그래프. V(S)⊆V(G), E(S)⊆E(G)를 만족시키는 그래프이다.
• 연결 그래프(connected graph) : 모든 정점 쌍에 대하여 항상 경로가 존재하는 무방향 그래프
     + 트리는 사이클을 가지지 않는 연결 그래프이다.
  - 비연결 그래프(unconnected graph)
• 완전 그래프(complete graph) : 그래프에 속해있는 모든 정점이 서로 연결되어있는 그래프
  그래프 정점의 수가 n인 경우 하나의 정점은 n - 1개의 다른 정점으로 연결되므로 간선의 수는 $\frac{n * (n - 1)}{2}$이 된다.

 

 

그래프의 연산

객체 : 정점의 집합과 간선의 집합
연산 :
    create_graph() ::= 그래프 생성
    init(g) ::= 그래프 g를 초기화
    insert_vertex(g, v) ::= 그래프 g에 정점 v를 삽입
    insert_edge(g, u, v) ::= 그래프 g에 간선 (u, v)를 삽입
    delete_vertex(g, v) ::= 그래프 g의 정점 v를 삭제
    delete_edge(g, u, v) ::= 그래프 g의 간선 (u, v)를 삭제
    is_empty(g) ::= 그래프 g가 공백 상태인지 검사
    adjacent(v) ::= 정점 v에 인접한 정점들의 리스트 반환
    destroy_graph(g) ::= 그래프 g를 제거

 

 

그래프 구현 방법

1. 인접 행렬(adjacency matrix) : 2차원 배열을 이용
   - 시간 복잡도
      * 두 정점의 간선 존재 여부 : $O(1)$
         ex) 정점 u와 정점 v를 연결하는 간선 : ``M[u][v]``
      * 정점의 차수 : $O(n)$ 인접 행렬의 행이나 열을 보면 됨
      * 모든 간선의 수 : $O(n^2)$ 인접 행렬 전체를 봐야 하기 때문
   - n개의 정점을 가지는 그래프를 표현하기 위해서는 항상 $n^2$개의 메모리 공간이 필요
   - 간선이 많이 존재하는 밀집 그래프(dense graph)를 표현할 때는 적합하나 간선이 적은 희소 그래프(sparse graph)에는 메모리 낭비가 큼
2. 인접 리스트(adjacency list) : 연결 리스트를 이용
   - 정점의 개수만큼 포인터 배열이 필요

 

 

그래프 탐색

1. 깊이 우선 탐색(DFS : depth first search)
   - 구현 방법
      1) 순환 호출 이용
      2) 명시적인 스택을 사용
   - 시간 복잡도 (정점의 수가 n이고 간선의 수가 e인 그래프인 경우)
      * 인접 리스트로 표현되어 있는 경우 : $O(n + e)$
      * 인접 행렬로 표현되어 있는 경우 : $O(n^2)$
2. 너비 우선 탐색(BFS : breath first search) : 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
     - 시간 복잡도
       * 인접 리스트로 표현되어 있는 경우 : $O(n + e)$
       * 인접 행렬로 표현되어 있는 경우 : $O(n^2)$ 

 

 

 

 

 

---

신장 트리(spanning tree)

• 그래프 내의 모든 정점을 포함하는 트리(그래프의 최소 연결 부분 그래프이다.)
• 모든 정점들이 연결되어 있어야 한다.
• 사이클을 포함해서는 안된다.
• 정점이 n개일 때 (n - 1)개의 간선으로 연결된다.
• 최소 비용 신장 트리(MST: minimum spanning tree) : 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장 트리

 

 

최소비용 신장 트리를 구하는 알고리즘

  결과는 두 방법 모두 동일하다. 희소 그래프를 대상으로 한 경우에는 Kruskal의 알고리즘, 밀집 그래프의 경우에는 Prim의 알고리즘이 더 효율적이다.

1. Kruskal (간선 기반 알고리즘) : 탐욕적인 방법을 이용
   • 탐욕적인 방법(greedy method) : 매 순간 가장 좋다고 생각되는 것을 선택함으로써 최종 답에 도달하는 방식
   • 시간 복잡도 : union-find 알고리즘을 쓰면 $|e|log_2|e|$ (간선들을 정렬하는 시간에 좌우되기 때문)
   • union-find 알고리즘
     - 간선의 양끝 정점이 같은 집합에 속해있는지 검사하는 알고리즘(같은 집합이면 간선을 추가할 경우 사이클이 형성됨)
        ex) ``union(x, y)`` : 원소 x와 y가 속해있는 집합을 입력으로 받아 2개의 합집합을 만듦
              ``find(x)`` : 원소 x가 속해있는 집합을 반환
2. Prim (정점 기반 알고리즘) : 시작 정점부터 신장 트리 집합을 단계적으로 확장해나가는 방법. 간선이 n - 1개가 될 때까지 반복하며, 앞 단계에서 만들어진 신장 트리 집합에 인접한 정점들 중에서 최저 간선으로 연결된 정점을 선택하여 트리를 확장한다.
   • 시간 복잡도 : $O(n^2)$

 

 

최단 경로 알고리즘

   최단 경로(shortest path)  : 네트워크 안의 특정한 정점 두 개를 연결하는 경로 중에서 간선들의 가중치의 합이 최소가 되는 경로

1. Dijkstra : 하나의 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 구하는 알고리즘. 최단 경로는 경로의 길이 순으로 구해진다.
   
   • 시간 복잡도 : $O(n^2)$
2. Floyd : 그래프에 존재하는 모든 정점 사이의 최단 경로를 한 번에 모두 찾아주는 알고리즘
   • 시간 복잡도 : $O(n^3)$

 

 

위상 정렬

• 위상 정렬(topological sort) : 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것. 하나의 그래프에는 여러 개의 위상 순서가 존재할 수 있다.
• 위상 순서(topological order) : 위상 정렬 과정에서 선택되는 정점의 순서