Graph Traversals and Topological Sorting

Graph Traversal

  • BFS = A B D E C
  • DFS = A B C D E

Topological Sorting

  1. Theorem 17: A graph can be topologically sorted iff it is acyclic. There are two cycles in : BCD and BDE. Therefore, to get a graph that can be sorted topologically, we need to remove and .
  1. topological sorting = A D B C E

Explanation: ord of nodes:

  • A -> 0 incoming edges
  • B -> 2, from A & D
  • C -> 2, from A & B
  • D -> 0
  • E -> 2, from C & E
n | number of edges
--------------------------
1 | 0
2 | 1
3 | 2+1 = 3
4 | 3+2+1 = 6

Conjuncture: The maximum number of edges in a directed graph with vertices that can be topologically sorted is:

  • The bound is an upper bound: since there are no more edges one could add without creating a cycle. From node with there are possible edges to to nodes without creating a cycle. From node with there are possible edges to nodes without creating a cycle (all except node ), …
  • The bound is tight: because such a graph can be constructed by adding all edges with .