3
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ Where did your definition come from? $\endgroup$
    – dtldarek
    Mar 30, 2015 at 12:43

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ I'm not sure that your approach works with the definition in the question. Please see my post, in particular observe how your algorithm would act on the example graph when started from vertex $1$. $\endgroup$
    – dtldarek
    Mar 30, 2015 at 12:42
  • $\begingroup$ It seems that the simple graph with two directed edges $A \to B$ and $A \to C$ is a counter-example to your algorithm. $\endgroup$
    – hengxin
    May 14, 2016 at 10:06
  • $\begingroup$ @hengxin I don't see how that would be a counter-example. For example, if you start at $x=B$, you would first mark $B$ as visited. Then, you would look at all the unvisited neighbors of $B$. $B$ has one neighbor, which is $A$, so you would set $x=A$. You mark $A$ as visited, and move on to $C$, and mark that one as visited as well. $\endgroup$
    – 5xum
    May 14, 2016 at 11:37
  • 1
    $\begingroup$ However, there is neither a directed path from $B$ to $C$ nor a directed path from $C$ to $B$. That is, the example graph is not weakly connected. $\endgroup$
    – hengxin
    May 14, 2016 at 11:44
2
$\begingroup$

On the definition:

Your definition of weakly connected graph is:

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

There is another definition of weakly connected graph, that is

  1. Directed graph $G=(V,E)$ is weakly connected if and only if it is connected as an undirected graph.

Please note that this definitions are not equivalent, in particular consider the following graph $G$ with $E(G) = \{(1,0),(1,2)\}$, that is, $$0 \gets 1 \to 2$$

which does not have any directed path $0 \to^* 2$ nor $2 \to^* 0$. It means that it is not weakly connected according to the first definition, but it is according to the second.

Solution using the second definition:

Checking if a graph is weakly connected according to the second definition is easy: just run a DFS ignoring edge directions and test if you have visited all the vertices.

Solution using the first definition:

On the other hand, the case of the first definition is more tricky. To put it in different words, it means that there are no incomparable elements in the transitive closure of the graph. The transitive closure might take some time to calculate, but we don't have to. Such elements can easily be spotted using the DAG of strongly connected components.

To check whether a graph is weakly connected according to the first definition you should check if the DAG of strongly connected components is a path (possibly of length zero).

I hope this helps $\ddot\smile$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .