Please enable JavaScript.

Coggle requires JavaScript to display documents.

Graphs, Paths and Cycles, Weighted graphs, Topological Sorting, Graph…

- - - - This problem is called Topological Sorting.
      - The problem cant have a solution if a digraph has a directed cycle. For topological sorting to be possible, a digraph in question must be a dag.
        
        It turns out that being a dag is not only necessary but also sufficient for topological sorting to be possible.
- - - - At a dead end, the algorithm backs up one edge to the vertex it came from and tries to continue viciting unvisited vertices from there. The algorithm eventually halts after backing up to the starting vertex, with the latter being a dead end
        
        By then, all the vertices in the same connected component as the starting vertex have been visited. I unvisited vertices still remain, the depth-first search must be restarted at any one of them.
  - - - Such edge is called a back edge because it connects a vertex to its ancestor, other than the parent, in the depth-first search forest.
- - - - After that, the front vertex is removed from the queue.
  - - - Whenever a new unvisited vertex is reached for the first time, the vertex is attached as a child to the vertex it is being reached from with an edge called a tree edge.
      - If an edge leading to a previously visited vertex other than its immediate predecessor is encountered, the edge is noted as a cross edge.