双语离散数学期末考试_2012年春季_试卷A

双语教师的考核激励制度与应用 VIII. (6%) The pseudo-code of Prim’s algorithm is given as following: Procedure Prim(G: connected weighted undirected graph with n vertices) T := a minimum-weight edge

for i := 1 to n?2 begin

e := an edge of minimum weight incident to a vertex in T and not forming a simple circuit in T if added to T T := T with e added

Print e

end {T is a minimum spanning tree of G}

(a) Find a minimum spanning tree using Prim’s algorithm given above. For every iterative in for-loop, list the

result for “Print e” statement.

(b) Compute the total weight of the spanning tree.

页脚内容6