Let G be a weighted undirected connected graph. Write, in pseudo-code, an algori
ID: 3707718 • Letter: L
Question
Let G be a weighted undirected connected graph. Write, in pseudo-code, an algorithm sumCrossEdges(G) that performs DFS of G and returns the sum of weights of edges that get labeled as 'cross' edges.
Answer in pseudo-code that resembles the below example for a BFS on the same question.
Algorithm sumCrossEdges (G) sum = 0 for e E G.edges(0) mark e unvisited for v E G.vertices() mark v unvisited s - G.vertices().getFirst() Q new empty sequence Q.insertlast(s) mark s visited while Q is not empty u = Q.first() for all e E G.incidentEdges(v) do w opposite(v, e) if w is not visited mark ww set label of e to DISCOVERY Q.insertLast (w) else if e is not visited set label of e to CROSS sum sume.getWeightO return sumExplanation / Answer
Here I am providing the PSEUDOCODE for sum of weights of edges that get labeled as 'cross' edges.
We will do DFS(depth first search).
In PSEUDOCODE, we will use following terms :
1. ) S :- It will denote stack . (Initially at top)
2.) S.push(v) : We are pushing v at the top of stack
3.) S.pop() : We are popping top element.
4.) S.top() : returns top element of stack
5.) G = Graph
------------------------PSEUSOCODE-------------------------
Algorithm sumCrossEdges(G)
sum = 0;
for e {belongs to } G.edges()
mark e as unvisited
end for
for v {belongs to } G.vertices()
mark v as unvisited
end for
t = G.vertices().getFirst()
S = new Empty Stack
S.push( t )
mark t as visited
while S is not empty
v = S.top();
S.pop();
for all e { belongs to } G.incidentEdges( v ) // for all edges connected to that vertex
do
w = opposite(v,e); // finding the opposite vertex
if w is not visited
mark w as visited
set label of e to DISCOVERY
S.push(w); // Putting that nodes to the the top of stack
else if e is not visited
set label of e to CROSS
sum = sum + e.getWeight()
end else if
end for
end while
return sum
-------------------------------------------------
FInally we gets the sum of crossedges
PLEASE RATE POSITIVELY....
MEANS A LOT TO ME
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.