단순 경로(simple path), 사이클(cycle), 단순 사이클(simple cycle)
- 단순 경로(simple path): 반복되는 정점이 없는 경로
- 사이클(cycle): 시작 정점과 종료 정점이 같은 경로
- 단순 사이클(simple cycle): 시작 정점과 종료 정점이 같고, 반복되는 정점이 없는 경로 (사이클, 단순 경로)
연결 그래프(connected graph), bridge
그래프 탐색
: 하나의 정점(source node)로부터 시작하여, 차례대로, 모든 정점들을 한 번씩 방문한다. (target node를 찾을 때까지)
그래프 탐색 알고리즘
- 깊이 우선 탐색 (DFS: Depth-First Search)
- 너비 우선 탐색 (BFS: Breadth-First Search)
깊이 우선 탐색 (DFS: Depth-First Search)
: Source node에서 멀어지는 방향으로 갈 수 있을 때까지 가다가, 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서, 이곳으로부터 다른 방향으로 다시 탐색을 진행한다.
- 스택: Last In First Out
--> 되돌아가기 위해서는 스택이 필요하다.
깊이 우선 탐색 (DFS) 알고리즘
깊이 우선 탐색 (DFS) 과정
: Source node, 그리고 아직 방문되지 않은 노드부터 스택에 쌓이다가, 더 이상 push할 것이 없으면 pop!
Cf) 그래프에 사이클(cycle)이 있는지 검사하는 알고리즘
깊이 우선 탐색 (DFS) 프로그램 - 인접 행렬
- 인접 행렬: O(n^2)
깊이 우선 탐색 (DFS) 프로그램 - 인접 리스트
- 인접 리스트: O(n+e)
행렬은 간선이 있든 없든 자료구조가 저장되고 처리를 해야 하나, 리스트는 간선이 있는 것만 자료구조를 저장하고 처리한다.
따라서 행렬은 간선이 없는 것도 한 번의 비교연산을 하게 되므로, 총 연산의 횟수가 행렬의 크기와 동일하게 |V| x |V| 가 된다.
그러나 리스트는 간선이 있는 것만 처리하므로, vertex (|V|) 들이 자신의 간선 (2 x |E| in undirected graph)들만 처리하므로, 리스트에서 노드(data + link)들의 개수와 동일하게, |V| + |E| 가 된다.
깊이 우선 탐색 (DFS) 명시적 스택 버전 알고리즘
너비 우선 탐색 (BFS: Breadth-First Search)
- 큐: First In First Out
너비 우선 탐색 (BFS) 알고리즘
너비 우선 탐색 (BFS) 과정
: Source node, source node와 연결되어 있는 인접 정점부터 방문하여 큐에 push하고, 더 이상 방문하지 않은 정점이 없으면 멈춘다.
너비 우선 탐색 (BFS) 프로그램 - 인접 행렬
- 인접 행렬: O(n^2)
너비 우선 탐색 (BFS) 프로그램 - 인접 리스트
- 인접 리스트: O(n+e)
출처: 이화여자대학교 이숙영교수님 자료구조
'자료구조' 카테고리의 다른 글
| [자료구조] 1110 - 11. 그래프(2) (1) | 2023.11.26 |
|---|---|
| [자료구조] 1110 (0) | 2023.11.11 |
| [자료구조] 1103 - 10. 그래프 (1) (0) | 2023.11.04 |
| [자료구조] 3. 배열, 구조체, 포인터 (0) | 2023.10.26 |
| [자료구조] 2. 순환 (0) | 2023.10.26 |
