Create Time: 11th May 2024
Title: "[[DAA-Assignment-2]]"
status: DONE
Author:
- AllenYGY
tags:
- DAA
- Assignment
created: 2024-05-11T13:58
updated: 2024-06-11T01:14
A tree is the maximum spanning tree of a graph if is a spanning tree of and the weight on the tree is maximized.
Mr. Smart designs an algorithm to find the maximum spanning tree. Is his algorithm correct?
Algorithm MaxST(G, w)
Require: a connected graph G=(V,E) with a weight function w:E→Z
Ensure: the maximum spanning tree T of G
begin
E←sort(E) in decreasing order based on w
A←{}
for all u∈V do
CREATE-SET(u)
end for
for all (u,v)∈E do
if FIND-SET(u)=FIND-SET(v) then
add (u,v) to A
UNION(u,v)
end if
end for
return (V,A)
end
Note that his algorithm is exactly same as Kruskal’s algorithm
except that the loop from line 7 to 12 iterates on edges in the decreasing order. (15pts)
I think his opinion is correct.
Case I: Heavy Edge is Safe Edge
Case II: Heavy Edge is Not Safe Edge
Given a weighted connect graph
Mr. Smart designs the following algorithm to find the maximum simple path from one vertices to all other vertices. Is his algorithm correct? Prove your answer.
Algorithm MaxSP(G, w, s)
Require: a connected graph G=(V,E) with a weight function w:E→Z, a source vertex s∈V
Ensure: the maximum distance Δ(s,v) for all v∈V
begin
for all u∈V do
d[u]←∞
color[u]←W
end for
d[s]←0
pred[s]←NULL
Q←new PriorityQueue(V)
while Q is not empty do
u←Q.extractMax()
for all v∈adj[u] do
if d[u]+w(u,v)>d[v] then
d[v]←d[u]+w(u,v)
Q.increaseKey(v,d[v])
pred[v]←u
end if
end for
color[u]←B
end while
return d[u] for each u∈V
end
Note that his algorithm is exactly same as Dijkstra’s algorithm
except that the priority queue is implemented by a Max Heap. Each round of the loop from line 9 to 19 extract the largest weight edge. And is updated if . (15pts)
I think his algorithm is not correct.
From the lecture, Mr. Smart knows that Prim’s algorithm runs in Kruskal’s algorithm
runs in Kruskal’s algorithm
. Is he correct? Prove your answer. (10pts)
I think he is not correct.
The time complexity of Prim's algorithm
is
The time complexity of Kruskal's algorithm
is
In this case, the time complexity of Prim's algorithm
is lower than Kruskal's algorithm
.
The time complexity of Kruskal's algorithm
is
The time complexity of Prim's algorithm is
In this case, the time complexity of Kruskal's algorithm
is lower than that of Prim algorithm.
Therefore, it cannot be said that the time complexity of Prim's algorithm
is always lower than that of Kruskal's algorithm
.