+35 votes
8k views

Consider the following directed graph:

The number of different topological orderings of the vertices of the graph is _____________.

edited | 8k views
0

Although people have provided very good solution. But before looking at them think about  -

1. Counting and Discounting method of Permutation and combination. OR
2. Construct permutation tree. Desired answer could be obtained via any one of them.

PS: Same methods  are used in below mentioned solutions.

## 4 Answers

+83 votes
Best answer
Here, start with $a$ and end with $f$.
$$a \;\_ \; \_ \; \_ \; \_ \; f$$
Blank spaces are to be filled with $b$, $c$, $d$, $e$ such that $b$ comes before $c$, and $d$ comes before $e$.
Number of ways to arrange $b$, $c$, $d$, $e$ such that $b$ comes before $c$ and $d$ comes before $e$, will be =  $4!/(2!*2!) = 6$
by Loyal (9.7k points)
edited
+1
Can you apply standard algorithm and than can you prove your answer???
0
there are some other cases like d comes before b
0
d comes before b is an option meaning d can come even after b.
+2
additional thought which might help

we have $a$ _ _ _ _ $f$

So we have to fill these spaces with $b,c,d,e$ such that $b \rightarrow d$ and $d \rightarrow e$

We use $\binom{4}{2}$ to pick the spots for  $b \rightarrow d$ and $d$  and $e$ can be filled in one way

so we get 6 ways
+23

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

0

any other simpler method because this method take lots of time?

+2
@Hemant Parihar I understood your approach, but I am not clear with why do we call it as Topological BFS?? Since BFS typical implementation follows FIFO order so when 'b' is removed , making indegree of 'c' and 'd' as 0, then as per queue, 'd' MUST be evaluated prior to 'c' but here we have choices of both.So how its an application of BFS????...plz explain

And if we say it a pure bfs implementation than, will that give all possible orderings??
0

@Shaik Masthan I forgot the method you told and that question.

Can you please help in this using that method? Please give the link for that discussion if possible.

+1

you may directly check in my answers list !

https://gateoverflow.in/253496/number-of-topological-order

0

What you are suggesting works for weighted graph but for unweighted graphs we can fill the queue in any order.

+55 votes

In topological sorting all nodes are like tasks and edges show the dependency among the tasks.

Node i to j an edge is there means task i must complete before task j.(in the mean time some other task may get complete after task i and before task j..but task i and j sequence need to be maintained)

Here in following 6 ways all the 6 tasks can get completed.

by Boss (23.9k points)
edited
0
indeed a best reference @rajesh sir
0
Rajesh How did u prepare this graphical answer. Plz explain
0
thanks sir ..grt method
0
nice approach @rajesh pradhan
0
nice answer sir
0 votes
Bruteforce Method-

a bdce f

a bdec f

a dbce f

a dbec f

a bcde f

a debc f
by Active (3.9k points)
edited
0
2*2*2=6 ??
0
sorry :)
–1 vote

this is according to me I think it is 8 I may be wrong

by (175 points)
edited
0
in second last one.. f cannot occur before b and c occur,, hence it is wrong
Answer:

+50 votes
15 answers
1
+34 votes
7 answers
2
+34 votes
7 answers
3