Chapter 7. Connected Components
One basic question about a network is which vertices are reachable from one another. For example, a well designed Web site should have enough links between Web pages so that all pages can be reached from the home page. In addition, it is often nice to have links going back to the home page, or at least to the previous page in a sequence. In a directed graph, groups of vertices that are mutually reachable are called strongly connected components. In an undirected graph, groups of vertices that are reachable from one another are called connected components.
A study of 200 million Web pages has shown that 56 million of the Web pages on the Internet form one large strongly connected component [7]. The study also showed ...
Get The Boost Graph Library: User Guide and Reference Manual now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
