그래프가 주어지고 해당 그래프에서 '최소 스패닝 트리'(MST)를 찾으라고 요청한다고 가정합니다. 그래프의 MST는 모든 정점이 존재하고 연결된 가중치 그래프의 하위 집합이며 하위 집합에 주기가 없습니다. MST의 총 간선 가중치가 그래프에서 가능한 최소값이기 때문에 MST를 최소값이라고 합니다. 그래서 여기에서 Prim의 MST 알고리즘을 사용하고 주어진 그래프에서 MST의 총 간선 가중치를 찾습니다.
따라서 입력이 다음과 같으면
, 정점 수(n)는 4이고 시작 정점(s) =3이면 출력은 14가 됩니다.
이 그래프의 MST는 다음과 같습니다. -
이 MST의 총 가장자리 가중치는 14입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- mst_find() 함수를 정의합니다. G, s
- distance :=음의 무한대로 초기화된 크기 G의 새 목록
- 거리[s] :=0
- itr :=False 값으로 초기화된 G 크기의 새 목록
- c :=0
- 참일 때 수행
- min_weight :=무한대
- m_idx :=-1
- 0~G 크기 범위의 i에 대해
- itr[i]가 False와 같으면
- 거리[i]
- 최소 무게 :=거리[i]
- m_idx :=나
- 거리[i]
- itr[i]가 False와 같으면
- m_idx가 -1과 같으면
- 루프에서 나오다
- c :=c + min_weight
- itr[m_idx] :=참
- G[m_idx] 값의 각 쌍 i, j에 대해 do
- distance[i] :=최소 거리[i], j
- 반환 c
- u :=항목[0]
- v :=항목[1]
- w :=항목[2]
- u :=u - 1
- v :=v - 1
- min_weight =min(G[u, v], w)
- G[u, v] :=min_weight
- G[v, u] :=min_weight
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def mst_find(G, s):distance =[float("inf")] * len(G) distance[s] =0 itr =[False] * len(G) c =0 동안 True:min_weight =float("inf") m_idx =-1 for i in range(len(G)):if itr[i] ==False:if distance[i] 입력
4, [(1, 2, 5), (1, 3, 5), (2, 3, 7), (1, 4, 4)], 3
출력
14