[Seoul National Univ: Data Science] Lecture 7. Graphs

본 포스팅은 서울대학교 이준석 교수님의 M2480.001100 Principles & Applications of Data Science을 수강하고 공부한 내용을 정리하기 위한 포스팅입니다.

 

https://youtu.be/83XIXfdhx20?si=9LQ-8yzpuNljrGES

 

1. Graphs

 Graph는 정점 (Vertex)과 간선 (Edge)으로 이루어진 자료구조이다. 이때 Tree는 사이클이 없고 연결되어져 있는 특수한 그래프이다.

• Adjacency: 정점 u와 v 사이에 간선이 있으면 인접하다고 말한다.
• Degree: 한 정점에 연결된 간선 개수
• Path: 정점들을 연속해서 잇는 간선들의 나열
• Simple path: 정점을 중복해서 지나지 않는 경로
• Cycle: 시작 정점과 끝 정점이 같은 경로

Connected graph

→ 하나의 덩어리로 모두 이어져 있음

 

Disconnected graph

→ 정점들이 여러 덩어리로 나뉘어져 있음

 

Complete graph

→ 서로 다른 정점 모든 쌍 사이에 직접 간선이 있음. 정점이 N개면 간선이 N(N-1)/2개이다.

Weighted graph

→ 간선마다 가중치가 있는 그래프

 

Directed graph

→ 간선에 화살표 방향이 존재하는 그래프 

 Tree는 Graph의 Special case에 해당된다. 모든 노드가 연결되어 있고, 사이클이 하나도 없는 그래프를 Tree라고 부른다. 따라서 Tree는 무조건 N-1개의 Edge를 갖는다.

 

2.Graph Representation

 

 Graph를 표현하는 방법은 행렬과 리스트로 나뉜다.

 

Adjacency matrix

• 정점 수가 N개이면, N x N 2차원 배열을 만든다. 
• Memory Complexity: O(N^2)
• 그래프가 희소 (sparse)하면 메모리 낭비가 심하다는 단점 존재

(1) Unweighted graph

• matrix[i][j] → 간선이 존재하면 1, 없으면 0 

(2) Directed graph

• matrix[i][j] → 한쪽 방향만 고려해서 간선이 있는 경우 1, 없으면 0

(3) Weighted graph

• matrix[i][j] → 간선이 존재하면 가중치 값, 없으면 0 또는 무한대 값

Adjacency list

• 정점 수가 N개이면, 크기 N짜리 배열을 만들고, list[i]에 정점 i와 인접한 정점들의 연결 리스트를 저장한다.
• Memory Complexity: O(N + M)
• 그래프가 희소 (sparse)한 경우에 효율적이므로 간선이 적은 큰 그래프에 대해 보통 연결 리스트를 적용한다.

(1) Unweighted graph

• list[1] = {2, 4, 5}

(2) Directed graph

• list[1] = {2, 4, 5} / list[2] = { }

(3) Weighted graph

• list[1] = {(2, 3), (5, 10)}

 

3. Graph Traversal

 

Depth First Search (DFS)

DFS는 그래프를 순회하는 알고리즘 중 하나이다. 스택을 사용하여 새로운 정점에 도착하면 push()를 하고, 정점이 더 이상 갈 수 없는 상태면 pop()한다. 따라서 LIFO (Lats In, First Out) 구조이므로 스택을 사용한다. 

 

알고리즘 원리

• 임의의 시작 정점에서 시작
• 방문하지 않은 인접 정점으로 계속 이동
• 더 이상 갈 정점이 없다면 바로 직전에 왔던 정점으로 되돌아감 (Backtrack)
• 반복해서 모든 정점을 방문

 

 

Adjacency matrix로 구현한 경우 Time Complexity

• 정점 개수: |V|, 간선 개수: |E|
• 어떤 정점에서 인접한 정점들을 모두 찾으려면 → O(|V|)
• DFS 동안, 각 정점에서 한 번씩 진행하므로 → O(|V|^2)

Adjacency list로 구현한 경우 Time Complexity

• 정점 개수: |V|, 간선 개수: |E|
• 어떤 정점에서 인접한 정점들을 모두 찾으려면 → O(|E|)
• DFS 동안, 각 정점에서 한 번씩 진행하므로 → O(|V| + |E|)

 

Bridth First Search (BFS)

 

 BFS는 그래프를 순회하는 알고리즘 중 하나이다. 큐를 사용하여 새로운 정점에 도착하면 방문 여부를 확인한 후 enqueue()를 하고, 큐의 가장 앞에 있는 정점을 dequeue한다. 따라서 FIFO (First In, First Out) 구조이므로 큐를 사용한다. 

 

알고리즘 원리

• 임의의 시작 정점을 큐에 넣고 방문 표시
• 큐에서 하나 꺼내고 방문하지 않은 인접 정점을 큐에 삽입
• 큐 맨 앞에 있는 정점을 꺼내고, 해당 정점에서 인접한 정점 중 미방문한 정점을 큐에 삽입
• 반복해서 모든 정점을 방문

Adjacency matrix로 구현한 경우 Time Complexity

• 정점 개수: |V|, 간선 개수: |E|
• 큐에서 정점 한개  꺼내기 → O(1)
• 꺼낸 정점에서 인접한 정점들을 모두 찾으려면 → O(|V|)
• BFS 동안, 각 정점에서 한 번씩 진행하므로 → O(|V|^2)

Adjacency list로 구현한 경우 Time Complexity

• 정점 개수: |V|, 간선 개수: |E|
• 큐에서 정점 한 개 꺼내기 → O(1)
• 꺼낸 정점에서 list 안의 인접한 정점들만 찾으므로, 연결된 간선 수만큼만 찾는다. → O(|E|)
• BFS 동안, 각 정점에서 한 번씩 진행하므로 → O(|V| + |E|)

 

DFS vs. BFS

• DFS: 깊이 우선, Stack, Time Complexity O(|V|^2)
• BFS: 너비 우선, Queue, Time Complexity O(|V| + |E|)

BFS는 간선 가중치가 모두 동일할 때 최단 경로(간선 개수 기준)를 찾는 용도로 많이 사용된다.

 

3. Minimum Spanning Trees (MST, 최소 신장 트리)

 주어진 Undirected connected graph에서 모든 정점을 포함하면서 사이클이 없는 부분 그래프를 찾는 문제이다. 그래프 전체에서 간선을 몇 개만 추출하여 Tree를 만들면 Spanning Tree에 해당된다.

 

 따라서 DFS/BFS로 그래프 한 번만 순회하면 Spanning Tree를 얻을 수 있다. 다만, 트리의 모형은 어떤 알고리즘을 사용하고 어떤 정점에서 시작하냐에 따라 달라지게 된다.

 만약 weighted graph에서의 Spanning Tree를 만든다고 하면, 어떤 알고리즘을 사용하냐에 따라 간선 가중치의 합이 변화하게 된다. 이를 최소화 하는 것을 Minimum Spanning Tree (MST)라고 한다.

 

Prim's algorithm (Greedy)

 

알고리즘 순서

• 임의의 시작 정점을 선택하고 방문 집합으로 둔다.
• 현재 정점과 인접한 정점을 잇는 간선들 중에서 가장 가중치가 작은 간선을 하나 고른다.
• 그 간선을 트리에 추가하고, 그 반대쪽 끝 정점을 방문 집합에 추가한다. 
• 모든 정점이 방문될 때까지 반복한다.

 방문된 영역과 아직 방문되지 않은 영역 사이를 잇는 최소 비용 간선을 고르는 것이 핵심이다. 원래는 Greedy 알고리즘을 사용하면 가장 최적의 값을 찾지 못하지만, MST의 경우에는 전체 합이 전역 최적이라는 게 증명되어져 있다. 따라서 Prim 알고리즘은 Greedy인데도 보장되는 드문 케이스에 해당된다.

 

4. Topological Sorting

 

 사이클이 없는 방향 그래프에서 모든 간선에 대해 간선 방향을 거슬러 올라가지 않도록 정점들을 나열하는 문제이다. 항상 여러 개의 답이 있을 수 있고, 그래프에 사이클이 하나라도 있으면 이런 순서를 만들 수 없으므로, 사이클이 존재하지 않는다고 가정한다.

 

알고리즘

• 나가는 간선이 없는 노드를 뒤에서 하나 고른다.
• 그 노드를 현재 출력 리스트의 맨 뒤에 붙인다.
• 그래프에서 그 노드와 그 노드로 향하는 모든 간선을 삭제한다.
• 그래프가 빌 때까지 반복한다.

 알고리즘의 핵심은 뒤에서부터 노드를 선택하는 것이다. 그리고 이미 리스트에 넣어버린 노드로 향하는 간선들은 더 이상 고려하지 않아도 되므로 삭제하는 것이다.