Connected components

Splits a graph into its connected pieces, the groups of vertices joined to each other by some path, with one search per piece.

Time complexity O(V+E), gograph function gograph.ConnectedComponents.

connectivity.ConnectedComponents returns the same components, because it calls gograph.ConnectedComponents.

How it works

Two vertices are in the same connected component when some path joins them. The components are the separate pieces of a graph: no edge runs between two of them, so nothing in one piece can reach anything in another.

gograph searches breadth-first from the first vertex and gives every vertex it reaches the same component. When that search runs out, it starts the next one at the first vertex no search has reached, and so on, so the components come out in the order of their first vertex. Every vertex and edge is looked at once, so it costs O(V+E).

On a directed graph, gograph ignores the edge directions and returns the weakly connected components. It joins the two ends of each edge with union-find instead of searching, since a vertex doesn't keep a list of the edges that end at it. To find the groups that can reach each other along the edge directions, use Tarjan, Kosaraju or Gabow. Use connected components to find the islands of a network after an outage, or to handle each piece of a graph on its own.

Campus outage

The campus network while the core switches A1 and A2 are down for maintenance. Each building keeps its own switches, and the two pairs of buildings with a direct link still reach each other, but nothing else does.

An undirected graph with 98 vertices and 91 edges.

While both core switches are down, which buildings can still talk to each other?

The graph falls into 9 connected components, with 7, 7, 14, 20, 10, 10, 8, 16 and 6 vertices. No edge joins two of them, so each vertex can reach only the vertices in its own component.

Step by step

ConnectedComponents searches breadth-first from each vertex no earlier search has reached, in the graph's vertex order. Every vertex a search reaches is in the same component as the vertex it started from. When the queue runs out, the component is complete.
Start component 1 at A3, the first vertex. Put it in the queue.
Take A3 from the front of the queue. Its neighbors A5, A6, A7, A8, A9 and A10 are new, so they join the back of the queue.
Take A5 from the front of the queue. Every neighbor it has is already in the component.
Take A6 from the front of the queue. Every neighbor it has is already in the component.
Take A7 from the front of the queue. Every neighbor it has is already in the component.

111 more steps lead to the last one:

Done. ConnectedComponents found 9 components. They come out in the order of their first vertex. Every vertex now shows the component it belongs to.

Use it in Go

for _, component := range gograph.ConnectedComponents(g) {
	var names []string
	for _, v := range component {
		names = append(names, v.Label())
	}
	fmt.Println(strings.Join(names, ", "))
}

Example graphs

Home network, 6 vertices and 6 edges
Office outage, 11 vertices and 9 edges
Locked maze, 30 vertices and 27 edges
Karate club split, 34 vertices and 67 edges
Campus outage, 98 vertices and 91 edges