[자료구조] Graph (그래프) - 정의, 예제, 시간복잡도, 장단점

# 자료 구조 시리즈

1. Array (배열)
2. Linked List (연결 리스트)
3. Stack
4. Queue
5. Tree (Binary / Segment)
6. Graph
7. Deque
8. Heap & Priority Queue
9. Trie

---

자료구조(Data Structure)에서는 자료에 효율적으로 접근하고 수정할 수 있도록, 데이터를 구성하고 저장하는 방법을 공부합니다. 자료구조는 데이터의 형태에 따라 크게 선형과 비선형으로 구분됩니다. 선형 자료구조는 데이터가 일렬로 나열되어 있는 반면, 비선형 자료구조는 데이터가 특정한 형태를 띄고 있다는 것이 핵심입니다. 전자의 예시로는 Array, Linked List, Stack, Queue 등이 있으며 후자에는 Tree, Graph 등이 있습니다.

 

Graph (그래프)

---

1. 정의

 

  Graph(그래프)는 Node(노드)와 노드를 연결하는 Edge(간선)을 모은 자료 구조입니다. 선형 자료구조나 트리 자료구조로 표현이 힘든 n:m 관계의 원소들을 표현하기 위해 사용됩니다.

 

  그래프 용어

1. 정점, 노드 (Vertex, Node)
2. 간선 (Edge)
  - 무향 간선 (Undirected Edge) : 방향이 존재하지 않는 간선, 양방향
  - 유향 간선 (Directed Edge) : 방향이 존재하는 간선
3. 인접 (Adjacent) : (정점 관점) 두 정점 A, B 사이에 간선이 존재한다면 A, B는 인접한다.
4. 부속 (Incident) : (간선 관점) 두 정점 A, B 사이에 간선 e가 존재한다면 간선 e는 정점 A, B에 부속한다.
5. 차수 (Degree) : 한 정점에 연결된 간선의 수
  - (방향 그래프) in-degree : 정점에 들어오는 간선의 수, out-degree : 나가는 간선의 수
6. 자기 간선과 다중 간선
  - 자기 간선 (Self-loop) : 자신으로 다시 돌아오는 간선
  - 다중 간선 (Multiple / Parallel edges) : 두 개 이상의 간선이 똑같은 두 정점에 부속할 때
7. 경로 (Path) : 정점 + 간선이 교대로 구성된 sequence
  - 단순 경로 (Simple Path) : 같은 정점을 두 번 이상 가지 않는 경로
8. 회로 (Cycle) : A 정점에서 출발했을 때 다시 A 정점으로 돌아오는 경로
  - 단순 회로 (Simple Cycle) : 같은 정점을 두 번 이상 가지 않는 싸이클
9. 연결됨 (Connected) : 정점 A에서 정점 B로의 경로가 존재할 때 A와 B는 연결되어 있다.

 

  그래프의 종류는 크게 여섯 가지로 구분됩니다. (아래 그림 참고)

https://laboputer.github.io/ps/2017/09/29/graph/

---

  그래프를 구현하는 방법으로는 Edge List(간선 리스트), Adjacency Matrix(인접 행렬), Adjacency List(인접 리스트)가 존재합니다. (Node가 V개, Edge가 E개라고 가정)

 

  1) Edge List(간선 리스트)

• E x 2 (or E x 3) 이차원 배열 A에 정보를 저장합니다.
• 두 정점 x, y 를 연결하는 간선 k에 대해서 A[k][0] = x, A[k][1] = y
• 가중치 그래프의 경우 A[k][2] 에 가중치 정보를 저장합니다.

---

  2) Adjacency Matrix(인접 행렬)

• V x V 이차원 배열 A에 정보를 저장합니다.
• V_i, V_j를 연결하는 간선이 존재한다면 A[i][j] = 1, 존재하지 않는다면 A[i][j] = 0
• 방향 그래프와 달리 무방향 그래프는 각 노드의 Edge의 방향성이 없기 때문에 대칭행렬로 표현됩니다.
• 가중치 그래프의 경우 1 대신 가중치 정보를 저장합니다.

메모리 복잡도가 V^2 이기 때문에 V의 값이 클 경우 쓰지 않는 것이 좋다. Edge의 수가 적더라도(노드끼리 하나도 연결이 되어 있지 않은 그래프라 할지라도) 항상 VxV 만큼의 메모리 공간이 필요하게 됩니다.

---

  3) Adjacent List(인접 리스트)

• 노드 자체는 Array로 배열하되, 노드에 인접한 다른 노드들은 Linked List로 그래프 정보를 저장합니다.
• 연결된 Edge에 대한 값만 저장하므로 공간복잡도 상의 이점이 있고, Edge 수보다 Node 수가 많은 sparse graph에 주로 이용됩니다.
• 가중치 그래프의 경우 (정점 정보, 가중치 정보)를 함께 저장합니다. (C++ : pair, Java : class)

  * 그래프 표현 방식 비교 (정점 개수 : V개, 간선 개수 : E개)

반응형

---

2. Graph의 시간복잡도

0) 그래프 탐색 알고리즘

1. 깊이 우선 탐색(DFS, Depth-First Search)
  - Stack 자료구조를 이용하여, root 노드를 Stack에 삽입하고 인접 노드로 내려가 방문 처리합니다.
  - 임의의 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다. 즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것으로서, 결국에는 모든 노드를 방문 하고자 할 때 이 방법을 선택합니다. 깊이 우선 탐색이 너비 우선 탐색보다 간단합니다.

def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
 
# 각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [
    [],
    [2,3,8], # 1번 노드와 연결
    [1,7], # 2번 노드와 연결
    [1,4,5], # ...
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

---

2. 너비 우선 탐색(BFS, Breadth-First Search)
  - Queue 자료구조를 이용하여, root 노드를 Queue에 삽입하고 인접 노드 중 방문하지 않은 노드를 모두 Queue에 넣어 방문 처리합니다.
  - 임의의 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법입니다. 즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것으로, 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택합니다. (Edge 비용이 동일한 상황에서)

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력하기
        v = queue.popleft()
        print(v, end=' ')
        # 아직 방문하지 않은 인접한 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

# 각 노드가 연결된 정보를 표현(인접 리스트)
graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9

# 정의된 DFS 함수 호출
bfs(graph, 1, visited)

ex) 
Instagram의 모든 팔로우 관계를 그래프로 표현한 후 Marcel와 Ko 사이에 존재하는 경로를 찾는 경우
깊이 우선 탐색 - (최악의 경우) 모든 친구 관계를 다 살펴봐야 할 수도 있음
너비 우선 탐색 - Marcel과 가까운 노드(관계)부터 탐색

---

1) Adjacency Matrix (인접 행렬)

시간복잡도

1) 두 특정 노드(i, j)에 연결된 Edge가 있는지 확인하는 연산
- 인접 행렬 i행, j열을 참조하면 되므로 O(1)

2) 임의의 노드(i)에 연결된 노드를 탐색하는 연산
- 인접 행렬 i행 전체를 참조하면 되므로 O(V)

---

공간 복잡도

- 행렬을 만들기 위해 노드 수(V) x 노드 수(V)만큼의 공간이 필요하여 O(VxV)

---

2) Adjacency List (인접 리스트)

시간복잡도

1) 두 특정 노드(i, j)에 연결된 Edge가 있는지 확인하는 연산
- 노드 i에 있는 Linked List를 순회하면서 j를 찾으면 되므로 O(d) 
  (여기서의 d는 노드 i의 Linked List 사이즈)

2) 임의의 노드(i)에 연결된 노드를 탐색하는 연산
- 노드 i에 있는 Linked List를 순회하면서 임의의 노드를 찾으면 되므로 O(d) 
  (여기서의 d는 노드 i의 Linked List 사이즈)

---

공간 복잡도

- 노드 수(V) 및 특정 노드에 연결된 Edge 수(E)를 고려하여 O(V+E)

---

3. Graph의 장단점

  1) 장점

1. 인접 행렬
 - 구현이 쉽고, 두 특정 노드(i, j)끼리의 인접 여부 확인이 빠릅니다.

2. 인접 리스트
 - 인접한 노드에 한해 Linked List가 저장되므로 Edge 수에 비례하는 만큼의 메모리만 사용합니다.
 - 특정 노드(i)에 인접한 다른 노드들을 알고 싶을 때 효율적입니다.

---

   2) 단점

1. 인접 행렬
 - 특정 노드(i)와 인접한 노드를 찾을 때 모든 Edge를 확인해야 합니다.
 - Edge 수가 적은 희소(Sparse) 행렬도 VxV 만큼의 메모리 공간이 필요합니다.

2. 인접 리스트
 - 두 특정 노드(i, j)의 연결 여부를 판단할 때 Linked List를 순차적으로 확인해야 합니다.

 

 

관계 표현이 필요한 경우 Graph의 활용도가 높습니다. 최단 경로 탐색(도로 정보),
관계 분석(Social Media 관계망 또는 네트워크)에서 사용됩니다.

---

참고자료 
 - https://velog.io/@cha-suyeon/알고리즘-깊이-우선-탐색DFS-과-너비-우선-탐색BFS
 - https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html
 - https://laboputer.github.io/ps/2017/09/29/graph/
 - https://gitub.com/Seogeurim/CS-study