Can a DAG have strongly connected components

directed graphsgraph-connectivity

It seems to me, a DAG (the directed graph has no cyclic.) is not possible to have strongly connected components (SCC), but it can have weakly connected components (WCC).

The definition of SCC and WCC:

SCC: The SCC is an arbitrary directed graph form a partition into subgraphs that are themselves strongly connected (from wiki).
WCC: WCC is a subgraph of the original graph where all vertices are connected to each other by some path, ignoring the direction of edges (from GeeksforGeeks).

There are some references:

Is my understanding correct? I tried to search references which have more strict claim, but cannot any. If anyone knows, please point out. A ton of thanks!

Best Answer

Every graph has a decomposition into SCCs, and Wikipedia's page for SCCs explicitly states

A directed graph is acyclic if and only if it has no strongly connected subgraphs with more than one vertex, because a directed cycle is strongly connected and every non-trivial strongly connected component contains at least one directed cycle.

So the truth is that DAGs must have no SCCs on more than one vertex, not that they have no SCCs at all.

It is trivial to see that all DAGs have WCCs.

Related Solutions

Partition a directed graph into cycles

Let us start by making some observing that if some set of vertices induces a simple cycle, then these vertices are in the same strongly connected component (SCC), so any simple cycle of a directed graph must reside completely in one SCC. Also note that two vertices which are connected by edges in both directions is a simple cycle, so the only SCCs which do not contain a simple cycle are singletons (i.e. they consist of exactly 1 vertex). The vertex contained in such a SCC is not part of any simple cycle (otherwise it would be in a different SCC by our first observation) so any graphs with singleton SCCs does not admit a partition of the kind you are seeking.

It follows that such a partition can be obtained (if it exists) by partitioning the graph into SCCs.

Does Tarjan’s algorithm actually find all SCCs

I did a quick and dirty python implementation of the algorithm as described in the Wikipedia article, and tested it on your digraph.

# Implement Trajan's algorithm for strongly connected components

SCC = []
indices = { }
lowlinks = { }
stack = []
index = 0

G = {1:[3], 2:[1,4],3:[2],4:[5],5:[4,6],6:[5]}

def strongConnect(v):
    global index
    
    indices[v] = index
    lowlinks[v] = index
    index += 1
    stack.append(v)
    for w in G[v]:
        if w not in indices:
            strongConnect(w)
            lowlinks[v] = min(lowlinks[v], lowlinks[w])
        elif w in stack:
            lowlinks[v] = min(lowlinks[v], indices[w])
    if lowlinks[v] == indices[v]:
        scc = []
        while True:
            w = stack.pop(-1)
            scc.append(w)
            if w == v:
                break
        SCC.append(scc)
            
for v in G:
    if v not in indices:
        strongConnect(v)
        
for scc in SCC:
    print(scc)

This outputs

[6, 5, 4]
[2, 3, 1]

so the algorithm does indeed work in this case. The algorithm is very well known, and the chance that it is incorrect is negligible.

Best Answer

Related Solutions

Partition a directed graph into cycles

Does Tarjan’s algorithm actually find all SCCs

Related Question