[Math] Weakly connected graph test

algorithmsgraph theory

What is the right algorithm for testing whether the graph is "weakly connected"?

The theory says:

Oriented graph $G=(V,E)$ is weakly connected graph if and only if for every two vertices $u,v \in V$ exists a directed path from $u$ to $v$ or directed path from $v$ to $u$.

Best Answer

The best way to go about this is to perform some sort of either depth first or breadth-first search through the graph: for example, the depth first search would look something like this in pseudocode (y in the code is a "neighbor" of x if there exists an edge from x to y or from y to x)

start at random vertex x
initialize an empty stack
repeat:
    mark x as visited
    push x onto the stack
    if x has an unvisited neighbor y:
        x = y
    else:
        y = stack.pop()
untill the stack is empty

If the search concludes after visiting all vertices, then the graph is weakly connected. Otherwise, all visited vertices form a weakly connected component.

Related Question