[자료구조] Chap13 그래프의 응용

Chap13 그래프의 응용

1. 스패닝 트리 (신장트리)

• 원래 그래프의 노드는 모두 포함. 간선은 최소로, 연결그래프를 유지하며 노드수-1개로 줄인 트리. 사이클 없음.
• 종류
  1. 깊이 우선 스패닝 트리 : dfs로 방문한 간선들로 만듦
  2. 너비 우선 스패닝 트리 : bfs로 방문한 간선들로 만듦

 

2. 최소 스패닝 트리

• 간선의 가중치(비용) 합을 최소로 하는 스패닝 트리
• 구하는 방법 종류
  1. Kruskal 알고리즘(간선 수 e)
     • 모든 엣지들 중 비용이 최소인 엣지들부터 추가해가며 사이클이 만들어지지 않도록 추가여부를 선택함
     • 엣지를 크기순으로 정렬해두고 써도 되지만 min heap을 만들어 사용하면 더 효율적.
     • 이 경우 heap구성시간 O(e) + 최소 엣지 탐색 시간 O(loge) = O(e+loge)소요.
  2. Prims 알고리즘
     • 부속그래프를 만들어 점차 늘려가는 과정으로 만든다. 노드를 두 종류로 나누어 생각한다. 부속그래프에 추가된 노드와 아직 아닌 노드.
     • 추가할 노드를 선택하고 아직 추가되지 않은 노드와 이어주는 간선들 중 비용이 가장 작은 간선을 선택.(사이클 검사할 일이 없음)

 

3. 최단 경로 문제

• 한 지점에서 다른 지점까지의 최단거리를 구함. 그런데 이 과정에서 그 지점까지 가는 동안 거치는 노드들에게도 그 경로는 최단경로가 됨.
• Dijkstra 알고리즘
• 표 그려서 ... 
• 모든 노드와의 거리를 무한대로 시작. 현재 간선으로 연결된 노드들의 거리를 업데이트 함. 그 중 가장 작은 값의 노드를 선택하고 그 노드로 이동함. 그 노드의 간선으로 새로 연결된 노드가 있으면 값을 업데이트하고 기존에 연결되었던 노드라도 새 간선으로 인해 더 작은 값이 나타났다면 새 값으로 업데이트. 가장 작은 값 선택 반복.