Home

Graph Algorithms

Breadth-first and depth-first search, cycle detection, topological sort and Dijkstra's shortest path, one page each, all on the same small graph - with and without a cycle.

  • O(V + E)

    Breadth-first search

    Explore in rings, and the first path you find is the shortest.

  • O(V + E)

    Depth-first search

    Follow one branch to the end, then back up.

  • O(V + E)

    Cycle detection

    Three colours, and a back edge gives it away.

  • O(V + E)

    Topological sort

    An order where every dependency comes first.

  • O((V + E) log V)

    Dijkstra's algorithm

    Always expand the cheapest frontier vertex.

Developed by Akif Akkaya