Should I measure time number to get topological sort on directed graph?

Question

I'm implementing topological sort on directed graph using DFS without modifying graph. So I chose a time measuring method.

IMO, it's enough just having boolean flags indicates started or finished for all vertices.

1. If I visit started, but unfinished vertex, it's a back-edge and a cycle.
2. If I save vertex in order it finishes, it's topologically sorted list.

But all the texts on the internet just says to measure time number, so I'm not sure my opinion is right. (I'm self learner and not good at algorithms) Did I miss something? Or is that just a conceptual description?

Answer 1

Measuring the time complexity for this problem is easy when using DFS. Since the sort implements the same search as DFS, whose time complexity is O(V+E), the overall topological sort is also O(V+E) since it only adds a stack to the implementation.

Topological sort graphs are usually implemented using adjacency lists which means you could discover each vertex's neighbors by traversing the list once in linear time, O(V). Since this is a directed graph, the sum size of the lists of every vertex is its total number of edges, O(E). Since you perform both processes, you would get O(V+E).

Considering that your time complexity is now O(V+E), you can more accurately measure the time of your program if you could find your V and E.