Suppose that G is a directed graph. In class we discussed an algorithm that will

Question

Suppose that G is a directed graph. In class we discussed an algorithm that will determine whether a given vertex can reach every other vertex in the graph (this is the 1-to-many reachability problem). Consider the following similar problem: given graph G, is there any node in G that can reach every other node in G? Such a node is called a "source node". We want to know whether any node of G is a source node. A trivial algorithm for this is to execute DFS n times, using each node in G as the start node of the DFS. But the total time for this algorithm is O(n* (n+m)). Describe a linear time algorithm for this "does di-graph G have a source node problem".

Explanation / Answer

Below is a solution for some of the types of adjacency lists:

Incoming edge list: For each node, there is a list of vertices from which there is an incoming edge to this node. You can simply scan all vertices and check if the size of their adjacency list is 0 or not. A size 0 list means no incoming edges, so the node is either a source or disconnected. Assuming a connected graph, this scan of each vertex will give you a list of all sources (or you can stop after finding one) in O(|V|) time - linear in the number of vertices.

Outgoing edge list: For each node, there is a list of vertices to which there is a directed edge from this node. Keep a bit-string with each bit representing a vertex, initialized to 0. Starting from the first node, start scanning its list for vertices to which there is an outgoing edge from this. Every such node (neighbour) cannot be a source, so keep setting their corresponding bit in the bit-string. At the end, all vertices whose corresponding bits are still unset, are the source vertices. You can do this in time linear in the size of the graph - O(|V|+|E|).

Both lists together: For each vertex, there is a mixed list of vertices which have an edge to or from this vertex, with some other attribute indicating which of the two is actually the case. The approach is similar to 2 above, with the addition that any incoming edge immediately rules out the current vertex (and you can mark its bit set). Unlike in point 2 where you need to go through all vertices, here, you might find some source sooner. If you don't stop, you will have all sources. For both cases, time is again linear in the size of the graph - O(|V|+|E|).

Both lists separately: Just pick the incoming edge list and follow 1.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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