비선형 구조
이며, 트리의 일반적인 개념
입니다. 정점
과 간선
으로 표현한 것이다.정점
: Vertex, 대상이나 개체간선
: Edge, 정점 간의 관계가중치
: Weight, 간선의 크기가 있는 경우|V|
{u, v}
무방향 그래프
방향 그래프
가중치 그래프
루트없는 트리
이분 그래프
사이클이 없는 방향 그래프
모든 정점을 탐색하는 것
입니다.크게 인접 행렬
과 인접 리스트
로 2가지 방법으로 분류할 수 있습니다.
인접 행렬
n²
에 비례하는 공간이 필요합니다.인접 리스트
무방향 그래프
를 위한 인접 리스트 표현에서 필요한 총 노드 수
는 총 간선 수의 2배 입니다.인접 행렬
방식을 쓰는 것이 낫습니다.인접 배열
정적 (static)
입니다.이진 탐색 가능
합니다.인접 해시 테이블
0.5
로 만들면 평균 2번의 비교로 가능하다. 너비 우선 탐색
과 깊이 우선 탐색
이다.G = (V, E) 에서의 BFS 수행 시간
(a) 시작 정점으로 정해진 정점을 방문한다.
(b) 정점 1에 인접한 정점을 모두 방문한다. (각각 2, 3, 4로 표시했다.)
(c) 정점 2에 인접한 정점 중 방문하지 않은 정점은 없다. 정점 3에 인접한 정점 중 방문하지 않은 정점을 모두 방문한다. 하나밖에 없다(5로 표시했다.). 정점 4에 인접한 정점 중 방문하지 않은 정점을 모두 방문한다. 2개가 있다.(각각 6, 7로 표시했다.)
(d) 정점 5에 인접한 정점 중 방문하지 않은 정점은 없다. 정점 6에 인접한 정점 중 방문하지 않은 정점을 모두 방문한다. 하나밖에 없다.(8로 표시했다). 정점 7에 인접한 정점 중 방문하지 않은 정점은 없다.
(e) 마지막으로 정점 8에 인접한 정점 중 방문하지 않은 정점이 없어 더 이상 갈 곳이 없으므로 끝낸다.
BFS 알고리즘
BFS(G, s): for each v ∈ V-{s} v.visited 🠔 NO s.visited 🠔 YES enqueue(Q, s) while (Q != Ø) u 🠔 dequeue(Q) for each v ∈ u.adj if (v.visited = NO) v.visited 🠔 YES enqueue(Q, v)
G = (V, E) 에서의 DFS 수행 시간
(a) 시작 정점으로 정해진 정점을 방문한다. (1로 표시했다.)
(b) 정점 1에 인접한 정점 중 하나를 방문한다. (2로 표시했다.)
(c) 정점 2에 인접하면서 방문하지 않은 정점은 총 3개다. 이 중 하나를 방문한다. (3으로 표시했다.)
(d) 정점 3에 인접하면서 방문하지 않은 정점은 총 2개다. 이 중 하나를 방문한다. (4으로 표시했다.)
(e) 정점 4에 인접하면서 방문하지 않은 정점은 총 하나뿐이다. 이 곳을 방문한다. (5으로 표시했다.) 5에 인접한 정점 중 방문하지 않은 정점은 없다. 따라서 왔던 길로 되돌아간다. 정점 4, 3, 2로 되돌아가는 과정에 정점 4, 3에 인접한 정점 중 방문하지 않은 정점은 없다.
(f) 정점 2로 되돌아가면 이에 인접한 정점 중 방문하지 않은 정점이 하나 있다. 이곳을 방문한다. (6으로 표시했다.)
(g) 정점 6에 인접한 정점 중 방문하지 않은 정점은 총 2개다. 이 중 하나를 방문한다. (7으로 표시했다.)
(h) 정점 7에 인접한 정점 중 방문하지 않은 정점은 없다. 정점 6으로 돌아간다. 정점 6에 인접한 정점 중 방문하지 않은 정점이 하나 있다. 이곳을 방문한다(8로 표시했다.). 정점 8에서 인접한 정점 중 방문하지 않은 정점은 없다. 정점 6으로 돌아간다. 정점 6에서도 인접한 정점 중 방문하지 않은 정점은 없다. 정점 2로 돌아간다. 정점 2에서도 방문하지 않은 정점은 없다. 정점 1로 돌아간다. 정점 1에서도 방문하지 않은 정점은 없다. 시작 정점(정점1)에서 더 이상 갈 곳이 없으므로 끝낸다.
DFS 알고리즘
DFS (G, v): v.visited 🠔 YES for each x ∈ v.adj if (x.visited = NO) DFS(G, x)
연결 그래프 (Connected Gratph)
|V| - 1
신장 트리 (Spanning Tree)
"싸이클이 없는 연결 그래프”
로 정의최소 신장 트리 (Minimum Spanning Tree)
|V|-1
수행O(ElogV)
O(logV)
여러
정점 집합으로 시작하여 집합을 합쳐 나감O(ElogV)
O(ElogE)
= O(ElogV)
O(E + VlogV)
조건
위상 순서
위상 정렬(Topological Sorting)
Θ(V+E)
의 시간 복잡도다익스트라 알고리즘
벨만-포드 알고리즘
쌍최단 경로 알고리즘
프림 알고리즘
과 원리 유사하다.욕심 (Greedy) 알고리즘
으로 최적해 보장한다.음의 싸이클
은 허용하지 않는다.