Given a graph G = (V, E), a vertex upsilon is called sink if there are no outgoi

Question

Given a graph G = (V, E), a vertex upsilon is called sink if there are no outgoing edges from upsilon. A vertex v is called super sink if upsilon is a sink and for every vertex u elementof V, there is an edge from u to upsilon. Prove that every DAG (Directed Acyclic Graph) has a sink. Suppose you are given a graph G = (V, E) in adjacency matrix representation. Give an algorithm to compute super sink, if exists. Derive the time bound of your algorithm. Your grade depends the run time of your algorithm.

Explanation / Answer

algorithm would like to find super sink.

For(i=0;i<n;i++)

{

//traversing adjacency list for node for 0 to n

For(j=0;j<n;j++)

{

If(A[i][j]!=1)

{

//edge doesnot exist at from 'I' to j so current node I is not super sink

No_sink=1;

}

If(No_sink==0)

Print I as super sink;

No_sink=0; //resetting for next node

}

}

Clearly this algorithm only traverse all edges once so complexity of algorithm is

O( e)

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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