Our discussion of minimum spanning tree algorithms assumed that the graph was re

Question

Our discussion of minimum spanning tree algorithms assumed that the graph was represented using adjacency lists. Assume now that the graph is represented using a weighted adjacency matrix A, where A[x,y] = + if there is no edge between x and y, and otherwise A[x,y] is equal to the weight of the edge between x and y. Give a simple* implementation of Prim’s algorithm that runs in time O(n2) where n is the number of vertices in the graph. Be sure to carefully explain why your method runs in time O(n2).

Here, simply means that you cannot use sorting, heaps or binary search tree

Explanation / Answer

If Graph A = (X, Y) is represented as an adjacency matrix, for an vertex u, to find its adjacent vertices, instead of searching the adjacency list, we search the row of u in the adjacency matrix. We assume that the adjacency matrix stores the edge weights. |X|=n

MST-PRIM2(A, r)

for each u X[A] do

key[u] = ;

[u] = NIL;

end

key[r] = 0;

Q=X[A];

while Q not equal to do

u=EXTRACT-MIN(Q);

for each x X[A] do

if A[x,y] not equal to 0 and x Q and A[x,y] < key[x] then

[x] = u;

key[x] = A[x, y];

end

end

end

The outer loop (while) has |X | variables and the inner loop (for) has |X | variables. Hence the algorithm runs in

O(X 2 ). and here |X| == n (number of vertices)

Hence time compexity = O(n2)

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.