Card 08/ 10
Counting Components and Testing for Two Colours
Start a traversal from every vertex not yet seen; colour alternately, and an edge between equal colours ends the test.
One traversal visits everything a start vertex can reach, so running one from every vertex not yet seen visits the whole graph and counts its connected components: the groups of vertices joined to each other by paths and to nothing outside the group. The same pass can test whether a graph is bipartite, meaning its vertices split into two sets with every edge going between the sets and none inside one. This card does both with breadth-first search on one graph.
The counting is an outer loop. Go through the vertices in order, and each time one is not yet marked, add one to the count and start a breadth-first search from it, labelling everything it reaches with the count. Isolated vertices, with no edges at all, are components of one vertex, and the loop counts them because it tries every vertex rather than only those that appear in an edge.
The bipartite test colours as it goes. Give each start vertex colour 0, and give every vertex the search finds the other colour from the vertex that found it. If an edge ever joins two vertices of the same colour, no split into two sets exists. The graph here has vertices A to G and edges A-B, B-C, C-A, D-E and E-F; G has no edges. The table is from a run.
| Vertex | Component | Colour |
|---|---|---|
| A | 1 | 0 |
| B | 1 | 1 |
| C | 1 | 1 |
| D | 2 | 0 |
| E | 2 | 1 |
| F | 2 | 0 |
| G | 3 | 0 |
There are 3 components: A B C, D E F, and G alone. A count of 2 is the usual mistake, made by starting searches only from vertices that appear in an edge.
The colouring fails in the first component. A gets 0, and B and C, both found from A, get 1. Then the edge B-C joins two vertices of colour 1. A, B and C form a cycle of 3 edges, and a cycle with an odd number of edges can never be split: going round it, the colours must alternate, and after an odd number of steps the last vertex has the same colour as the first. So a graph is bipartite exactly when it has no odd cycle. The run removed A-B and the colouring then succeeded, with the components still 3.
Both jobs cost O(V + E), one visit per vertex and one look at each edge, because the outer loop starts a search only from unmarked vertices and no vertex is searched twice. Depth-first search works for both as well; breadth-first search is shown here only because its colouring is easy to follow ring by ring.
← → move through sections and cards