Topological sorting algorithm on a directed graph

Question

Consider a directed graph $D = (V, A)$ with $n$ vertices and $m$ arcs. I came up with this $O(m + n)$ algorithm (a modification of the Breadth first search algorithm) that finds a topological sort of the vertices or decides that there is a directed cycle in G.

Let s be a vertex such that there is no arc $(v,s)\in A$ that goes into it. We assume $G$ is connected, otherwise there would be elements that aren't comparable $\implies$ no total order

The vector $D$ will contain the distances from $s$ to each vertex.

INPUT: a directed graph
OUTPUT: state that there is a cycle or give an ordering of V

D[s]:=0 the distance from s to itself is zero
D[v]:=infinity for all v != s
L:={}
Q:={s}
While Q is non empty
    u:=Head(Q)
        For v in the set of vertices such that u->v is in A
            If D[v]=infinity
                D[v]:=D[u]+1
            Else If D[v]!=D[u]+1
                output "there is a directed cycle)
                STOP
            add v to the end of Q
            add v to the end of L
        Delete the first element of Q
For s' such that D[s']=infinity (the vertices without a path s->...->s')
    do the while loop from above
    add L' (the ordering of the children of v) to the beginning of L (this is because we can
              start at any vertex that has no parent and the order of
              those sub-sequences doen't matter in the final ordering)
output L

I am now wondering if this algorithm works well. Any comment would be appreciated, thanks.

Answer 1

First, even if there is no total order, it is still possible to have a topological ordering. The difference being that this is no longer unique. Secondly, your algorithm is almost correct. Consider a graph with three vertices $1,2,3$ with $1 \to 2, 1 \to 3, 2 \to 3$. So you would have vertex $3$ as $s$. You won't actually add $3$ to $L$, and you may add vertex $1$ before vertex $2$. What you want to do is to add vertices to the front of $L$ as you delete them from your queue.

Last point is that, I assume repeat the while loop is done by choosing another such vertex with no outdegree. (Else this step is wrong as is) You might want to add a bit more detail as how to do this efficiently. As it is possible that you take too much time in this step. Note that as you repeat, you should initialize the variables accordingly as well as your loop invariant of what your $D$ stores is now invalid. I suggest you to use a boolean array keeping track of visited instead.

Answer 2

What has already been done though is to (a) partition the vertices of a digraph $G$ into its strong connected components, and then (b) once this has been done, give a topological sort of the equivalence classes of $G$.

But (a) has been done already in linear time, google Kosaraju strongly connected components--beautiful linear-time algorithm that is a classic and is in any worthwhile graph algorithms book. And once given (a) doing (b) is easy. Collapse each strongly connected component of $G$ into a single vertex (if it isn't one already) and call the resulting graph $G'$. Then $G'$ is necessarily directed acyclic. Then at each stage,

While $G'$ is nonempty:

--$i \leftarrow i+1$

--remove from $G'$ the vertices w indegree 0 from $G'$. Give these removed vertices an index of $i$.

--$G' \leftarrow G' \setminus$ {removed vertices}

Each vertex in $G'$ corresponds to a strongly connected component of $G$. Each vertex $v$ in $G$ falls in the topological sort in the same place the strongly connected component $v$ is in falls into the topological sort of $G'$