- 그래프
- 그래프 용어
- 그래프 정의
- 무방향 그래프, 방향 그래프
- 가중치 그래프
- 부분 그래프
- 그래프 용어
- 인접 정점
- 정점의 차수
- 진입 차수(in-degree)
- 진출 차수(out-degree)
- 경로(path)
- 단순 경로(simple cycle): 반복되는 정점 없음
- 사이클(cycle): 시작 정점 = 종료 정점
- 단순 사이클(simple cycle)
- 오일러 사이클: 모든 edge 한번씩만 거쳐서 제자리로으로 돌아온다. (단순 사이클 x)
- 헤밀턴 사이클: 모든 node 한번씩만 거쳐서 제자리로 돌아온다. (단순 사이클)
- 그래프 연결 정도
- 연결 그래프
- 비연결 그래프
- 완전 그래프: 모든 정점이 연결되어 있는 그래프
- 그래프 정의
- 그래프의 표현 방법
- 인접 행렬(adjacent matrix)
- 인접 리스트(adjacent list)
- 그래프의 탐색
- 깊이 우선 탐색(DFS: Depth-First Search)
- 너비 우선 탐색(BFS: Breadth-First Search)
- 깊이 우선 탐색(DFS)
- 스택: Last in First out
--> Source node, 아직 방문되지 않은 노드부터 스택에 push하다가, 더이상 push할 것이 없으면 pop한다.- 인접 행렬
- 인접 리스트
- 명시적 스택
- 스택: Last in First out
- 너비 우선 탐색(BFS)
- 큐: First in First out
--> Source node부터 큐에 push하고, pop하면서 방문한 후, 인접 노드를 push하고, pop하면서 방문한다. 더이상 push할 것이 없으면 멈춘다.- 인접 행렬
- 인접 리스트
- 큐: First in First out
10.1 그래프 (Graph)
▶ 그래프란?!
: 객체 사이의 연결 관계를 표현할 수 있는 자료구조
- 정점(vertex, node)
- 간선(edge)
▶ G = (V, E)
: 정점(vertex)와 간선(edge)들의 유한집합
- V(G): 그래프 G의 정점(vertex)들의 집합 --> |V| = 총 정점의 개수
- E(G): 그래프 G의 간선(edge)들의 집합 --> |E| = 총 간선의 개수
- 오일러 경로: 그래프에 존재하는 모든 간선(edge)를 한번만 통과하면서 처음 정점(node)로 되돌아오는 경로
10.2 그래프 용어
무방향 그래프 (undirected graph) vs. 방향 그래프 (directed graph)
- 무방향 그래프(undirected graph)
- 방향 그래프(directed graph)
가중치 그래프 (weighted graph)
: 간선에 가중치(weight)가 할당된 그래프
부분 그래프 (subgraph)
: 어떤 그래프의 정점(vertex)와 간선(edge)의 일부로 이루어진 그래프
그래프 기본 용어
- 인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결된 정점
▶ 정점의 차수(degree)
- 무방향 그래프: 그 정점에 인접한 정점의 수
- 방향 그래프
- 진입 차수(in-degree): 외부에서 오는 간선의 개수
- 진출 차수(out-degree): 외부로 향하는 간선의 개수
경로 (path)
: 하나의 정점으로부터 다른 정점까지의 경로 --> 정점의 나열
- 단순 경로 (simple path): 반복되는 정점이 없는 경로
- 사이클 (cycle): 시작 정점과 종료 정점이 동일한 경로
- 단순 사이클 (simple cycle): 반복되는 정점이 없고, 시작 정점과 종료 정점이 동일한 경로 (단순 경로 + 사이클)
▶ 대표적인 사이클 문제:
- 오일러 사이클: 모든 edge를 한번씩만 거쳐서 제자리로 돌아오는 사이클 (단순 사이클 x)
- 헤밀턴 사이클: 모든 vertex를 한번씩만 거쳐서 제자리로 돌아오는 사이클 (단순 사이클 o)
그래프의 연결 정도
- 연결 그래프 (connected graph)
- 비연결 그래프 (unconnected graph)
- 완전 그래프 (complete graph): 모든 서로 다른 정점들이 서로 연결되어 있는 그래프
Cf) bridge: 없어지면 비연결 그래프가 되도록 하는 edge.
▶ bridge의 존재 여부를 판단하는 알고리즘:
- 현재 정점의 자식 정점 중에서, 현재 정점을 거치지 않고는 현재 정점 이전에 방문했던 정점에 갈 수 없는 정점이 있다면, bridge이다.
10.3 그래프의 표현 방법
- 인접 행렬 (adjacent matrix)
- 인접 리스트 (adjacent list)
1) 인접 행렬 (adjacent matrix)
- 무방향 그래프의 경우 대칭 행렬이기 때문에, 배열의 상위 삼각이나 하위 삼각만 저장하면 메모리를 절약할 수 있다.
- n개의 정점을 가지는 그래프를 인접 행렬로 표현하기 위해서는 간선의 수에 무관하게 항상 (n x n)개의 메모리 공간이 필요하다.
--> 인접 행렬 방법은 그래프에 간선이 많이 존재하는 밀집 그래프(dense graph)를 표현하는 경우에는 적합하나, 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(sparse graph)의 경우에는 메모리 낭비가 심하므로, 적합하지 않다. - 인접 행렬을 이용하면 두 정점을 연결하는 간선의 존재 여부를 O(1) 시간 안에 즉시 알 수 있다는 장점이 있다. 정점 u와 정점 v를 연결하는 정점이 있는지를 알기 위해서는 M[u][v]의 값을 조사하면 된다.
- 정점의 차수는 인접 행렬의 행이나 열을 조사하면 알 수 있으므로, O(n)의 연산에 의해 알 수 있다.
- 반면에 그래프에 존재하는 모든 간선의 수를 알아내려면 인접 행렬 전체를 조사해야 하므로, n^2 번의 조사가 필요하게 되어, O(n^2)의 시간이 요구된다.
2) 인접 리스트 (adjacent list)
- 리스트의 헤더 노드: 정점
--> 해당 정점과 연결된 다른 정점을 리스트로 표현한다.
10.4 그래프의 탐색
- 깊이 우선 탐색 - 스택
- 너비 우선 탐색 - 큐
10.5 깊이 우선 탐색 (DFS; Depth First Search)
- 스택: Last In First Out
- 0 --> 1
- 1 --> 3 --> 4
- 4 --> 2
- 2 --> 5 --> 6
--> 스택에 가장 최근에 들어간 정점이 다시 빠져나와, 새로운 source node 역할을 하며 정점을 찾는다.
DFS 알고리즘
DFS 과정
▶ 그래프에 사이클이 있는지 검사하는 알고리즘
: 임의의 노드에서 ancestor로의 간선이 있으면, 사이클이 존재한다.
- Cf) Bridge: 임의의 노드에서의 자식 노드가 그 자식 노드에서 ancestor로의 간선이 없으면, bridge이다.
깊이 우선 탐색 (DFS) 프로그램 - 인접 행렬
- 인접 행렬: O(n^2)
깊이 우선 탐색 (DFS) 프로그램 - 인접 리스트
깊이 우선 탐색 (DFS) 프로그램 - 인접 리스트
- 인접 리스트: O(n+e)
: 리스트는 간선이 있는 것만 처리하므로, vertex (|V|) 들이 자신의 간선 (2 x |E| in undirected graph)들만 처리하므로, 리스트에서 노드(data + link)들의 개수와 동일하게, |V| + |E| 가 된다.
깊이 우선 탐색 (DFS) - 명시적 스택 버전 알고리즘
10.6 너비 우선 탐색
- 큐: First In First Out
: 시작 정점에서 가까운 정점부터 탐색한다.
너비 우선 탐색 (BFS) 알고리즘
너비 우선 탐색 (BFS) 과정
: Source node, source node와 연결되어 있는 인접 정점부터 방문하여 큐에 push하고, 더 이상 방문하지 않은 정점이 없으면 멈춘다.
너비 우선 탐색 (BFS) 프로그램 - 인접 행렬
- 인접 행렬: O(n^2)
너비 우선 탐색 (BFS) 프로그램 - 인접 리스트
- 인접 리스트: O(n+e)
깊이 우선 탐색 (DFS) - example
▶ 깊이 우선 탐색 (DFS)
: 숫자가 작은 것부터 시작해서, 간선이 있는 숫자들로 내려간다.
- 스택: Last In First Out
- 0
- 0 --> 1 --> 3 --> 7 --> 6 --> 5
- 5 --> 2
- 2 --> 4
- 4 --> 8
- 8 --> 9
출처: 이화여자대학교 이숙영교수님 자료구조
'자료구조' 카테고리의 다른 글
| [자료구조] 12. 정렬 (0) | 2023.12.14 |
|---|---|
| [자료구조] 11. 그래프(2) (0) | 2023.12.14 |
| [자료구조] 1205 (2) 14. 해싱 (1) | 2023.12.07 |
| [자료구조] 1205 (1) (1) | 2023.12.07 |
| [자료구조] 1201 (2) 13. 탐색 (1) | 2023.12.06 |
