If we apply BFS to find topological sort, then we can also count all topological ordering with some order.

Topological sort using BFS.

**Step 1:** Pick any vertex 'v', whose in-degree is zero. (There is at least one vertex who has in-degree zero, if not then you can not find any topological sort (Why? Think !) ).

**Step 2: **Print 'v'. Remove the vertex 'v' and all edges coming out of it.

**Step 3**: Repeat step 2 and 3, till all the vertices are printed.

To find all topological sort, At any point, whenever we have 2 or more choices to pick the vertex 'v', whose in-degree is 0. Then we need to consider all the cases one by one.

Example as in this graph.

Vertex A has in-degree 0, no other vertex has in-degree zero. So we have only 1 choice.

Pick A, print A, remove A and all its out-going edges.

Output: A _ _ _ _ _ _

At this point, the graph will look like this.

Now we have two choices who has in-degree zero, b and d, we will consider both one by one.

If we pick b, remove b and all out-going edges.

Output: A B _ _ _ _

(Case of choosing D after A (instead of B), will be discussed later).

Now C and D have in-degree zero.

If we pick C, then

Output: A B C _ _ _

Now, Only D has in-degree 0, We pick D, then E, then F.

Output: A B C D E F

If we pick D after we have picked B, then

Output: A B D _ _ _

Now we have two choices, C and E

Output: A B D C E F

Output: A B D E C F.

Now we got 3 output sequence (when we have chosen B after A).

What if we have chosen D after A, we still have to count these sequences. Try to count will our self you will get 3 more sequences.

If you understood this try for this graph with this method, you will get 13 topological sorts for this graph.

Image source: Geekforgeeks

References: https://www.quora.com/Can-topological-sorting-be-done-using-BFS