Consider a directed graph on n vertices, where each vertex has exactly one outgo
ID: 3664643 • Letter: C
Question
Consider a directed graph on n vertices, where each vertex has exactly one outgoing edge. This graph consists of a collection of cycles as well as additional vertices that have paths to the cycles, which we will call the branches. We define the weight of the cycle to be the total number of vertices that are either on the cycle or on branches that are connected to the cycle. Give pseudocode for a linear time algorithm that identifies all of the cycles and computes the length and weight of each cycle.
Explanation / Answer
//Pseudocode to calculate the weight of the cycle:
//Traverse all the vertices
for i=1 to all verices v
{
//Assign the weight as 0
W(v) ß 0
//If its your first node then visit that node
//assign that node as 1
if (i = = 1)
{
Node1=i.node
//Continue the loop
Continue
}
//If its not your first node then
Else
{
//Traverse to the next node
i.Nodeài.NextNode
//Add weight of the vertex to the recent weight
W(v)ß W(v)+1
}
//If compiler reach to the first node in cycle
if(i. Node = =i. NextNode)
{
//Returns weight
Return W(v)
}
}
// Pseudocode to calculate the weight of the branches:
For j=1 to all vertex
{
//Assign weight 0 to another weight variable
Weight(v) ß 0
if(j==1)
{
Node1 = j.node
//Continue the loop
continue
}
else
{
j.Nodeàj.NextNode
Weight(v)=Weight(v)+1
}
//If compiler reach to the first node in cycle
if (i. Node1 = =j. NextNode)
{
Return Weight(v)
}
}
//Total weight of the graph
TotalWeight(v)=Weigh(v)+W(v)
//Returns total weight of the graph
Return TotalWeight(v)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.