4. Graph (그래프)
그래프는 연결되어있는 원소 간의 관계를 표현하는 자료구조다!
- 연결할 객체인 정점(Vertex)와 객체를 연결하는 간선(Edge)의 집합으로 구성
- 그래프를 나타내는 G = (V, E)로 정의
4. 1 그래프의 종류에는 무엇이 있을까?
(1) 무방향 그래프 (Undirected Graph): 두 정점을 연걸하는 간선에 방향이 없는 그래프
- 무방향 그래프는 방향이 없어서 정점 $ V_I $와 $V_j$를 연결하는 간선을 ($ V_I $, $V_j$)으로 표현하는데, 둘이 같은 간선임
- G = {존재하는 모든 노드}, E(G) = {(정점1, 정점2), ... 등 존재하는 모든 간선}
(2) 방향 그래프 (Directed Graph): 간선에 방향이 있는 그래프
- 방향이 있기 때문에 정점 $ V_I $와 $V_j$를 연결하는 간선을 <$ V_I $, $V_j$>로 표현하는데 앞의 것을 꼬리(tail), 뒤의 것을 머리(head)라고 하고 순서가 바뀌면 다른 간선임
- G = {존재하는 모든 노드}, E(G) = {(정점1, 정점2), ... 등 존재하는 모든 방향이 있는 간선}
(3) 완전 그래프 (Complete Graph): 한 정점에서 모든 다른 정점과 연결되어 최대 간선 수를 갖는 그래프
- 정점이 n개인 완전 그래프에서 무방향 그래프의 최대 간선 수 : n(n-1)/2
- 방향 그래프 최대 간선 수 : n(n-1)
(4) 부분 그래프 (Subgraph): 기존 그래프에서 일부 정점이나 간선을 제외하여 만든 그래프
- 오른쪽이 왼쪽의 부분 그래프
(5) 가중 그래프 (Weight Graph): 정점을 연결하는 간선에 가중치(weight)를 할당한 그래프
- 각 간선마다 가중치 값이 있음
(6) 유향 비순환 그래프 (DAG, Directed Acyclic Graph): 방향 그래프에서 사이클이 없는 그래프
(7) 연결 그래프 (Connected Graph): 떨어져 있는 정점이 없는 그래프
(8) 단절 그래프 (Disconnected Graph): 연결되지 않는 정점이 있는 그래프
4.2 그래프에서 사용하는 용어에는 무엇이 있을까?
- 그래프에서 두 정점 A, B가 연결되어 간선 (A,B)가 있을 때, 이 두 정점을 인접(adjacent)한다고 하고, 간선 (A,B)는 정점 A와 B에 부속(incident)되어 있다고 함
- 정점(Vertex): 위치 = node
- 간선(edge): 위치 간 관계, 노드 연결하는 선
- 인접 정점(adjacent vertex)
- 차수(Degree) : 정점에 부속되어 있는 간선의 수
- 진입 차수(in-degree): 방향 그래프에서 외부에서 들어오는 간선 수 (내차수)
- 진출 차수(out-degree): 방향 그래프에서 외부로 나가는 간선 수 (외차수)
- 경로(Path) : 정점 A에서 B까지 간선으로 연결된 정점을 순서대로 나열한 리스트
- 단순 경로(Simple Path): 경로 중 반복이 없는 경우
- 경로 길이(Path Length): 경로 구성 간선의 수
- 사이클(Cycle): 단순 경로 중 경로의 시작 정점과 마지막 정점이 같은 경우
4.3 그래프에는 어떤 특징이 있지?
- 그래프는 네트워크 모델임
- 2개 이상의 경로가 가능함 = 노드들 사이에 무방향/방향에서 양방향 경로 가능
- self-loop뿐 아니라 loop/circuit 가능
- 루트 노드가 없음 (트리랑 다른 점)
- 부모-자식 개념 없음
- 순회는 DFS/BFS
- 간선 유무는 그래프 따라 다름
4.4 그래프는 어떻게 구현할 수 있을까?! (Python)
(1) 인접 리스트 (Adjacency List) - 가장 일반적
- 모든 정점을 인접 리스트에 저장함 -> 즉, 각각 정점에 인접한 정점들을 리스트로 표시
- 배열과 각 인덱스마다 존재하는 또 다른 리스트를 이용해 인접 리스트 표현
0: 1
1: 2
2: 0, 3
3: 2
4: 6
5: 4
6: 5- 무방향 그래프는 간선 두 번 저장
- 트리는 특정 노드 (루트 노드)에서 다른 모든 노드로 접근 가능 => Tree class가 굳이 불필요
- 근데 그래프는 모두 가능하지는 않기 때문에 Graph class가 필요
class Graph { public Node[] nodes; }
// 트리의 노드 클래스와 동일
class Node {
public String name;
public Node[] children;
}(2) 인접 행렬 (Adjacency Matrix)
- 인접 행렬은 NxN Boolean Matrix 로써 matrix[i][j]가 true면 i->j의 간선 존재한다는 의미
if(간선 (i, j)가 그래프에 존재)
matrix[i][j] = 1;
else
matrix[i][j] = 0;- 정점의 개수가 N인 그래프를 인접 행렬로 표현 => 간선 수와 무관하게 항상 N^2개의 메모리 공간 필요
- 무방향 그래프를 인접 행렬로 표현하면 대칭 행렬 (Symmetric Matrix)
- 인접 리스트는 어떤 노드에 인접한 노드를 쉽게 찾을 수 있음. 하지만 인접 행렬은 모든 노드를 전부 순회해야함
(3) 그럼 둘 중에 어떻게 고르지?
[1] 인접 리스트
- 그래프 내에 적은 숫자의 간선을 가지는 희소 그래프 (Sparse Graph)의 경우
- 장점: 인접 노드 찾기 쉬움, 모든 간선 수는 O(N+E)만에 알 수 있음
- 단점: 정점의 차수만큼의 시간 필요
[2] 인접 행렬
- 그래프 내 간선 많은 밀집 그래프 (Dense Graph) 의 경우
- 장점: 간선 존재 여부 (M[i][j])를 O(1)만에 알 수 있음, 정점 차수는 O(N)만에 알 수 있음
- 단점: 인접 노드 찾으려면 전부 순회해야함, 모든 간선의 수는 O(N^2)걸림 (전수조사)
4.5 그래프를 탐색(Search)해보자!
[1] 너비 우선 탐색 (BFS, Breadth-First Search)
- 노드에서 시작해서 노드와 같은 거리에 있는 노드를 우선으로 탐색
- 파이썬에선 큐로 주로 구현, 대신 그냥 리스트로 해서 pop(0)으로하면 시간복잡도 O(n)으로 비효율적이라 deque로 구현 추천
def bfs(nodes, root):
visited = []
graph = deque([root])
while graph:
n = graph.popleft()
if n not in visited:
visited.append(n)
items = sorted(nodes[n])
for item in items:
if item not in graph and item not in visited:
graph.append(item)
return visited
[2] 깊이 우선 탐색 (DFS, Depth-First Search)
- 노드에서 시작해서 다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색
- 스택으로 구현
def dfs(nodes, root):
visited = []
graph = [root]
while graph:
n = graph.pop()
if n not in visited:
visited.append(n)
items = sorted(nodes[n], reverse=True)
for item in items:
if item not in visited:
graph.append(item)
return visited- 둘다 구현의 메인은 연결된 노드 저장하기, visit한 노드 저장하기!!!
- 이번에 제대로 bfs/dfs를 공부하면서 느낀건데, 되게 어렵다고 생각했는데,, 간단하게 보면 그냥 bfs는 시작 노드에서 인접(adjacent) 노드 불러와서 탐색하고 visit에 넣고,, dfs도 마찬가지. 생각보다 어렵게 생각한 거 치고 간단한 알고리즘이었다!
'Algorithm > STUDY' 카테고리의 다른 글
| [알고 스터디] 7. 최단 거리 알고리즘 - 1647 (0) | 2023.08.09 |
|---|---|
| [알고 스터디] 6. 그리디 알고리즘 (Greedy Algorithm) (0) | 2023.08.09 |
| [알고 스터디] 3. 트리(Tree) - 2606 (0) | 2023.08.03 |
| [알고 스터디] 3. 트리(Tree) - 11725 (0) | 2023.08.03 |
| [알고 스터디] 2. 큐(Queue) - 11286 (0) | 2023.07.27 |