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