Which of the following lists are possible topological sorts

Which of the following lists are possible topological sorts of the graph G below? e, f, b, a, d, c c, e, b, f, a, d f, b, c, e, a, d e, c, f, b, d, a f, a, d, c, e, b e, b, f, a, c, d

Solution

The correct option is C E B F A D.

The topoligical sort is a linear order of vertices in a way that each directed edge uv, vertex u comes before v in the ordering. And to find this we need to first get the vertex which a having a zero degree that means no incoming edges.Once we identify such vertex we will take it and all its connected vertex(but the only one which is connected just to this one) out of the graph and put in output

Here we have F and E zero degree vertices, so we will start with E

C E and then connected vertex is B and D but D is connected to F as well so we will just take out B

C E B ,

then next is F to which A and D are connected, now D is connected to E, A ( E is already in output so no issues, A which is connected to F hence it will go int output anyways). A is connected to D, F, B, E (B and E we already have in output, F will be in output as this vertex for which we are listing connected vertex)

C E B F A D