Section 7.18 Strongly Connected Components
For the remainder of this chapter we will turn our attention to some extremely large graphs. The graphs we will use to study some additional algorithms are the graphs produced by the connections between hosts on the internet and the links between web pages. We will begin with web pages.
Search engines like Google and Bing exploit the fact that the pages on the web form a very large directed graph. To transform the World Wide Web into a graph, we will treat a page as a vertex, and the hyperlinks on the page as edges connecting one vertex to another. Figure 7.18.1 shows a very small part of the graph produced by following the links from one page to the next, beginning at Luther College’s Computer Science home page. Of course, this graph could be huge, so we have limited it to websites that are no more than 10 links away from the CS home page.
If you study the graph in Figure 7.18.1 you might make some interesting observations. First you might notice that many of the other websites on the graph are other Luther College websites. Second, you might notice that there are several links to other colleges in Iowa. Third, you might notice that there are several links to other liberal arts colleges. You might conclude from this that there is some underlying structure to the Web that clusters together websites that are similar on some level.
One graph algorithm that can help find clusters of highly interconnected vertices in a graph is called the strongly connected components algorithm, or SCC. We formally define a strongly connected component, \(C\text{,}\) of a graph \(G\text{,}\) as the largest subset of vertices \(C \subset V\) such that for every pair of vertices \(v, w \in C\) we have a path from \(v\) to \(w\) and a path from \(w\) to \(v\text{.}\) Figure 7.18.2 shows a simple graph with three strongly connected components that are identified by the different shaded areas.
Once the strongly connected components have been identified, we can show a simplified view of the graph by combining all the vertices in one strongly connected component into a single larger vertex. The simplified version of the graph in Figure 7.18.2 is shown in Figure 7.18.3.
Once again we will see that we can create a very powerful and efficient algorithm by making use of a depth-first search. Before we tackle the main SCC algorithm we must look at one other definition. The transposition of a graph \(G\) is defined as the graph \(G^T\) where all the edges in the graph have been reversed. That is, if there is a directed edge from node A to node B in the original graph, then \(G^T\) will contain an edge from node B to node A. Figure 7.18.4 and Figure 7.18.5 show a simple graph and its transposition.
Look at the figures again. Notice that the graph in Figure 7.18.4 has two strongly connected components. Now look at Figure 7.18.5. Notice that it has the same two strongly connected components.
We can now describe the algorithm to compute the strongly connected components for a graph.
- Call
dfsfor the graph \(G\) to compute the closing times for each vertex. - Compute \(G^T\text{.}\)
- Call
dfsfor the graph \(G^T\) but in the main loop of DFS explore each vertex in decreasing order of closing time. - Each tree in the forest computed in step 3 is a strongly connected component. Output the vertex IDs for each vertex in each tree in the forest to identify the component.
Let’s trace the operation of the steps described above on the example graph in Figure 7.18.2. Figure 7.18.6 shows the starting and closing times computed for the original graph by the DFS algorithm. Figure 7.18.7 shows the starting and closing times computed by running DFS on the transposed graph.
Finally, Figure 7.18.8 shows the forest of three trees produced in step 3 of the strongly connected components algorithm. You will notice that we do not provide you with the Java code for the SCC algorithm; we leave writing this program as an exercise.
You have attempted of activities on this page.
