C언어로 쉽게 풀어쓴 자료구조 11장 그래프II

ch.11 그래프II

11.1

신장트리(spanning tree)는 그래프의 모든 정점들을 연결한 트리이다. 하지만 전부 다 연결 되어서 사이클이 되어서는 안 된다. 또한 n개의 정점을 (n-1)개의 간선으로 연결 시킨다. 한 그래프에는 여러 개의 신장트리가 존재할 수 있다. 신장트리는 통신 네트워크 구축에 많이 사용되는데 회사 내의 모든 전화기를 신장트리를 구하여 가장 적은 수의 케이블을 사용하여 연결할 수 있다.

11.2

Kruskal의 MST알고리즘은 최소 비용 신장트리가 최소 비용의 간선으로 구성되고 사이클을 포함하지 않는다는 조건에서 각 단계에서 사이클을 이루지 않는 최소 비용 간선 선택

union-find 연산

비트 벡터, 배열, 연결리스트로 집합을 구현할 수 있지만 가장 효율적인 방법은 트리 형태로 구현하는 것이다. 부모 포인터 표현 1차원 배열로 구현이 가능한데 배열은 부모 노드의 인덱스를 저장하는데 예를 들면 배열의 값이 -1이면 부모 노드가 없는 것이다.

11.3

Prim의 방법은 신장 트리 집합에서 최소 거리에 있는 정점을 선택하여 트리를 확장하는데 이것을 트리가 n-1개의 간선을 가질 때까지 계속한다. prim의 알고리즘의 구현에는 먼저 distance라는 정점의 개수 크기의 배열이 있어야 한다. distance는 알려진, 신장 트리 정점 집합에서 각 정점까지의 거리를 가지고 있다. Prim의 최소 비용 신장 트리 알고리즘 ①우선 순위큐에 모든 정점을 삽입하고 이 때의 우선순위는 distance 배열값이 된다.②다음은 while루프를 이용하여 우선순위 큐에서 가장 작은 distance값을 가지는 정점을 끄집어낸다. 그 정점이 트리 집합에 추가된다. ③다음에는 트리 집합에 새로운 정점 u가 추가되어서 u에 인접한 정점 v들의 distance값을 변경시켜준다.

11.4

최단경로는 네트워크에서 정점 I와 j를 연결하는 경로 중 간선들의 가중치 합을 최소로 나오게 하는 경로를 찾는 것이다. 2가지의 알고리즘이 있는데 Dijkstra 알고리즘은 하나의 시작 정점에서 다른 정점까지의 최단경로를 구하는 알고리즘이고, Floyd 알고리즘은 모든 정점에서 다른 모든 정점까지의 최단 경로를 구한다.

11.5

가중치는 보통 가중치 인접 행렬에 저장되므로 가중치 인접 행렬을 weight라 하면 distance[w]= weight[v][w]가 된다.

11.6

Floyd의 최단 경로 알고리즘은 그래프에 존재하는 모든 정점 사이의 최단 경로를 한 번에 모두 찾아주는 알고리즘이다. Dijkstra알고리즘과 Flyod알고리즘이 둘다 시간 복잡도는 O(

)으로 같지만 Floyd의 알고리즘은 매우 간결한 반복구문을 사용하므로 Dijkstra의 알고리즘보다 상당히 빨리 모든 정점 간의 최단 경로를 찾을 수 있다.

11.7

예제밖에 없어서 생략