Lets go over some basic terminology before getting into something serious.
Connected graph means where there is a path from any node to every node.
Strongly Connected Component (SCC) means the graph is divided into components or rather collection of nodes. Each component is a connected sub graph i.e. there is path from any node to every node within the sub graph.
In a DAG, the graph can be condensed to a smaller graph with less nodes by taking all connected component nodes into one node.
How to find connected components ?
1. Take any node and perform a DFS.
2. On the recursive way down, store the nodes in a stack.
3. Pop these nodes one by one and perform DFS from each.
4. The nodes that is reachable from each is the part of a new connected component and all the reachable nodes are part of that CC.
This algorithm is called Kosaraju algorithm.
Proof is pretty simple. Refer to CLRS for that.
Applications:
If you are given a graph and asked to find the set of nodes which are reachable from all other nodes, how to approach?
First Approach : TLE
My first approach was to reverse the edges of the graph. Now I have to find the node which can "reach" all other nodes. The first thing that pops in mind is DFS! Apply DFS to every node and if a node can reach all in the transverse graph, it is reachable rom all in the original.
The time for a DFS is O(V+E). and this has to done on every node.
So TIme complexity is O(V^2 + EV). Meh thats too high. Lets think of another solution.
Second Approach : Better than before
A good observation in this would be, if a node (say X) can be reached by all nodes, then they can also reach all the nodes connected to that node X. That implies that all the nodes connected to X are the nodes we are trying to find. This means that if if divide the graph into Strongly Connected Components, One of these will be the component which can be reached by all. Another observation is that there will be no outgoing edge in this SCC. Why? See all the SCC's are connected to each other by atmost one edge. Now if suppose one edge of the "Reachable from all" SCC X is out going then the SCC Y that it connects to can't reach the X back and hence wont be reachable from Y.
So this has been established that SCC X has no out going edge. Now if a SCC has no outgoing edge and all incoming then only one such SCC can exist. (obviously)
Hence find all SCC's and then find the one with no outgoing edges, thats the collection of nodes reachable from all.
Connected graph means where there is a path from any node to every node.
Strongly Connected Component (SCC) means the graph is divided into components or rather collection of nodes. Each component is a connected sub graph i.e. there is path from any node to every node within the sub graph.
In a DAG, the graph can be condensed to a smaller graph with less nodes by taking all connected component nodes into one node.
How to find connected components ?
1. Take any node and perform a DFS.
2. On the recursive way down, store the nodes in a stack.
3. Pop these nodes one by one and perform DFS from each.
4. The nodes that is reachable from each is the part of a new connected component and all the reachable nodes are part of that CC.
This algorithm is called Kosaraju algorithm.
Proof is pretty simple. Refer to CLRS for that.
Applications:
If you are given a graph and asked to find the set of nodes which are reachable from all other nodes, how to approach?
First Approach : TLE
My first approach was to reverse the edges of the graph. Now I have to find the node which can "reach" all other nodes. The first thing that pops in mind is DFS! Apply DFS to every node and if a node can reach all in the transverse graph, it is reachable rom all in the original.
The time for a DFS is O(V+E). and this has to done on every node.
So TIme complexity is O(V^2 + EV). Meh thats too high. Lets think of another solution.
Second Approach : Better than before
A good observation in this would be, if a node (say X) can be reached by all nodes, then they can also reach all the nodes connected to that node X. That implies that all the nodes connected to X are the nodes we are trying to find. This means that if if divide the graph into Strongly Connected Components, One of these will be the component which can be reached by all. Another observation is that there will be no outgoing edge in this SCC. Why? See all the SCC's are connected to each other by atmost one edge. Now if suppose one edge of the "Reachable from all" SCC X is out going then the SCC Y that it connects to can't reach the X back and hence wont be reachable from Y.
So this has been established that SCC X has no out going edge. Now if a SCC has no outgoing edge and all incoming then only one such SCC can exist. (obviously)
Hence find all SCC's and then find the one with no outgoing edges, thats the collection of nodes reachable from all.
No comments:
Post a Comment