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 O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.