Graph

Directed Acyclic Graphs (DAG)

A directed graph with no directed cycles

Topological Sort

Ordering of nodes in a directed graph where for each directed edge from node A to node B, node A appears before B.

• $O(V+E)$ time complexity
• The result might not be unique
• Only a Directed Acyclic Graphs (DAG) can have a valid topological order, in other words, a graph containing cycle cannot have a valid ordering (since there is no starting node)

Reference

Kahn’s Algorithm (BFS)

• Maintain an array indegree for n nodes
• Enqueue nodes with indegree of zero
• While queue is not empty
  • Dequeue and add node to the topological order
  • Decrease the indegree for every connected nodes
  • Enqueue nodes with indegree of zero
• The topological order is found if order.size() == n
• Otherwise the graph contains cycle

Reference

DFS Approach

Dijkstra’s Algorithm

• Must only contains non-negative edge weights
  • Allows the greedy approach since optimal distance cannot be improved once we visited a node

Tarjan’s Strongly Connected Components Algorithm

• Verifying a graph does not contain a directed cycle

Flood Fill Algorithm

• BFS or DFS