1
다음은 CS 알고리즘 강사의 Kruskal 's Minimum Spanning Tree 알고리즘에 대한 의사 코드입니다. MST 알고리즘이 비 결정적인지 알고 싶습니다. 동일한 가중치를 가진 두 개의 에지가 주어지면 알고리즘이 T에 더할 때 어떤 엣지가 사이클을 형성하지 않으면 어떻게 알고리즘을 결정할 것인가? 그렇다면 임의의 경우에 정확한 에지가 T에 추가되는 결과를 결정할 수 없습니까?Kruskal의 MST 알고리즘이 비 결정적입니까?
Given an undirected connected graph G=(V,E)
T=Ø //Empty set, i.e. empty
E'=E
while E'≠Ø do
begin
pick an edge e in E' with minumum weight
if adding e to T does not form a cycle then
T = T∪{e} //Set union, add e to T
E' = E'\{e} //Set difference, remove e from E'
end
고마워요!