If starting from any vertex we can visit all other vertices, then the graph is connected.

We can do the same with breadth-first search, however the depth-first recursive implementation is straight-forward, while the breadth-first search requires a queue.

A graph is biconnected, if there are no vertices whose removal will disconnect the graph.

We can remove any vertex and the rest of the graph will still be connected.

The next graph is not biconnected:

If we remove C, the graph will become disconnected. Such vertices are called articulation points or cut-vertices.

There is a related concept for edges:

Obviously, a bridge has at least one articulation point at its end, however an articulation point is not necessarily linked in a bridge. For example, none of the edges ending in C in the above graph, is a bridge

Example of bridges:

Here (C,D) and (D,E) are bridges, C and D are articulation points, while E is not an articulation point.

We can compute articulation points using depth-first search and a special numbering of the vertices in the order of their visiting.

Here are some more examples of articulation points, bridges, and biconnected graphs:

Example 1: C is an articulation point, there are no bridges

Example 2: C is an articulation point, CB is a bridge

Example 3: B and C are articulation points, BC is a bridge

Example 4: B and C are articulation points. All edges are bridges

Example 5: Biconnected graph - no articulation points and no bridges

Definition: A directed graph is said to be strongly connected if for any pair of nodes there is a path from each one to the other.

Definition: A directed graph is said to be unilaterally connected if for any pair of nodes at least one of the nodes is reachable from the other.

Definition: A directed graph is said to be weakly connected if the underlying undirected graph is connected.

Examples:

Strongly connected graph:

Unilaterally connected graph:

Weakly connected graph: