Connected Graphs

Connectivity

Some path terminology:

• Connected: V and W are connected when a path exists between them.

• Path: an ordered sequence $(V,v_1,v_2,\dots,v_n,W)$ in which each consecutive pair is joined by an edge.

• Path length: the number of edges in an unweighted graph, or the sum of weights in a weighted graph.

• Simple path: no vertex appears twice.

• Cycle: a path whose start and end coincide.

An undirected graph is connected when every pair of vertices is connected.

A connected component is a maximal connected subgraph:

1. Its vertex set cannot be enlarged while retaining connectivity within the original graph.

2. It includes all original edges between its vertices.

In a directed graph, strong connectivity requires paths in both directions between every pair V and W. The two paths need not follow the same route.

If a directed graph is not strongly connected but becomes connected when directions are ignored, it is weakly connected.

A maximal strongly connected subgraph is a strongly connected component.

Traversing a disconnected graph

A traversal from one source can leave vertices unvisited. Invoke DFS or BFS again from an unvisited vertex. Repeating this covers all vertices; in an undirected graph, each new traversal covers another connected component.

Depth-first traversal across components

dfs(Vertex V)
    isVisited[V] = true
    for v in neighbors(V)
        if !isVisited[v]
            DFS(v)

listComponents(Graph G)
    for V in vertices(G)
        if !isVisited[V]
            DFS(V)