The Gateway to Computer Science Excellence
+36 votes
8.1k views

Consider the following directed graph:

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

in Algorithms by Loyal (7.2k points)
edited by | 8.1k 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.

+1

The topological ordering should start with a and end with f. Just one possibility here.

For the four remaining places in between; b should come before c, and d should come before e.

 

b __ __ __

b can be at the first position, and c can be anywhere in the remaining three positions => 3.

 

__ b __ __

b can be at the second position, and therefore c should be in one of the later two spots only. => 2

 

__ __ b __

b can be at the third position, and therefore c gets the last position. => 1.

 

Total = 6 cases. (Sum rule)

 

Now, after filling in b and c, only two spots would remain. d and e must fill those two spots in their predetermined order.

So, 6*1 = 6. (Product rule)

 

Hence, 6

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 by
+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

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

0

@Hemant Parihar 

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 by
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 (4k points)
edited by
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 by
0
in second last one.. f cannot occur before b and c occur,, hence it is wrong
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,391 answers
198,589 comments
105,442 users