Strongly Connected Component
A directed graph is strongly connected if there is a path between all pairs of vertices. A strongly connected component of a directed graph is a maximal strongly connected subgraph.
A graph is said to be strongly connected if every vertex is reachable from every other vertex.
Finding SCC
First we’ll depth-first, basically starting at a point and seeing what path it has to take. For this instance I started at A, in order for us to keep track we will simply put a number above the node we’re currently on. And go down a path that is reachable from said node, so I went to B. Incrementing the number by one for each node we reach. Let’s ignore the forward-slash for now.
If there isn’t anymore paths you can take from the node you’re at, then we’ll make a note of what the next number would have been in the sequence in the denominator, so D would have 5 under 4. Then return to the pervious node and see if that node has any other path we can take that have not been visited. In our example C has another path which is G. Repeat the process until it’s impossible for you to backtrack any further.
Now if you can’t backtrack anymore but there’s still node(s) that have not been reach, we’ll simple mark them as the next two numbers in the sequence.
Second, we’ll ignore the top number and only look at bottom number, see who has the highest number, the node with the highest will be first in our sequence. Write the node down and repeat the progress from highest to lowest number. After all nodes are down then that’s our sequence
Third, reverse all the arrows from the original graph and make a new graph. This time we’re going to start from the first node that is in our sequence and go down the list. By doing so it’s going to tell us where are strongly connected components are. In our example H is the first.
H doesn’t have any path it can take so it’s a strongly connected component on its own. But if H did have a path to take then any node that is reachable from H is part of the same strongly connected component. Repeat the progress until all nodes are accountant for (8 vertices).
Problem Solving
Let’s say we have more nodes and components. And you’re trying to find a path you can take from point A to point B from given paths, and these paths are one way and not all path are reachable from your starting point. We’ll first compress all the components into nodes, making each node it’s own component. What I mean is making the original directed graph into a new graph, basically taking the big circles and making them into new nodes.
By making the new graph we’ll achieve an acyclic graph, this is true because if we have 1, 2, 3 formed a cycle then they’re actually be part of the same component so it’s impossible for the new graph to have any cycles.
So after making a new graph we’ll start at any node. We’ll then add a new directed edges from S (Start) to other nodes that aren’t reachable from it. The nodes that aren’t reachable from S have a N degree of 0 (Inbound Edges). They don’t have any nodes pointing toward them so it’s impossible for S to reach them. This means we need to add edges to S so it can reach these unreachable nodes. By doing so we’ll have S access to all the nodes and the other nodes reachable from S.
