그래프 탐색, 가중치

P.460

그래프 내에서는 순서가 존재하지 않지만, 깊이 탐색의 경우 결론적으로 우선순위가 필요한데,

이를 해결하기 위해서 연결리스트로 연결한 경우, 연결된 순서대로 탐색을 진행한다.

 

그리고 이미 모두 탐색한 자리를 찾아갔을 경우, pop하여 while문의 진행을 막고, 위치이동을 한다.

 

---

신장트리

Spanning Tree

정점이 n개이고 간선이 n-1개인 트리 형태 부분 그래프를 신장 트리라고 한다.

 

 

• 크루스칼 알고리즘 I
  • 가중치가 높은 간선을 제거하면서 최소 비용 신장 트리를 만드는 방법
  • 끊긴 노드가 없도록

 

• 크루스칼 알고리즘 II
  • 가중치가 낮은 간선을 삽입하면서 최소 비용 신장 트리를 만드는 방법
  • 사이클을 형성하지 않도록

 

• 프림 알고리즘
  • 간선을 정렬하지 않고 하나의 정점에서 시작하여 트리를 확장해나가는 방법
  • 연결된 정점 전체에 부속된 모든 간선 중 가중치가 가장 낮은 간선을 삽입하여 트리 확장
  • 사이클을 형성하지 않도록

 

• 최단경로
  • 신장 트리가 아닌 가중치 그래프, 즉 네트워크에서 정점 u,v 간 연결 경로 중 가중치 합이 최소인 경로

 

• 가중치 인접 행렬
  • 가중치 그래프의 가중치 저장
  • 2차원 배열, 간선이 없으면 무한대
  • 각 정점은 자기 자신과 이어진 간선을 허용하지 않으므로 대각선 값 

 

• 다익스트라 최단 경로 알고리즘