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

create an empty queue create an empty set to store seen vertices create an empty set for sink nodes add source node to queue while queue is not empty get next vertex from queue, add vertex to seen vertices if num of adjacent nodes == 0 add sink nodes to sink node set else for each node in adjacent nodes if node is not in seen vertices add node to queue return size of sink nodes == 1 && size of seen vertices == total number in graph

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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