1
$\begingroup$

In depth first search each vertex can be associated with a discovery time and a finish time. I am reading the following implementation of topological sort in terms of depth first search

TOPOLOGICAL-SORT(G)
1 call DFS(G) to compute finish times for each vertex
2 as each vertex is finished, insert it to the front of a linked list
3 return the linked list of vertices

I don't see why it's necessary to compute the finish time for each vertex. Also the finish time is not used anywhere in the algorithm after it's being computed, so why do we need it?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Is the snippet from CLRS? Please edit your question and add a reference to it. $\endgroup$ Commented Jan 3, 2023 at 7:22

2 Answers 2

Reset to default
1
$\begingroup$

I guess the algorithm you presented is from CLRS. You are right that the finishing time is not necessary for the algorithm to work. Once the vertex is completely explored (all its neighbors are visited) then you can just marked the vertex as explored and then add it to the linked list. In a way, the finish time will be implied by the order of the vertices in the list.

However, if you will read the proof used in CLRS to show that the algorithm works correctly, that is the time they make use of the finish time. So I guess they add that to the algorithm for the sake of making the proof easier to state.

Improve this answer
$\endgroup$
1
$\begingroup$

Denote $\text{post}(v)$ (for postvisit number) its finish time. Then for any directed graph $G = (V, E)$, the two following properties are equivalent:

  1. $G$ contains a cycle;
  2. there exists an edge $(u, v)\in E$ such that $\text{post}(u)<\text{post}(v)$.

So the postvisit ordering can be used to decide the existence of a cycle, or to find a topological ordering when there is no cycle: the reverse of a postvisit ordering is a topological ordering given the previous equivalence.

See Algorithms from Dasgupta, Papadimitriou and Vazirani for more details.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.