Graph Theory Tutorials

Basics of Graph and Graph Traversals

  1. Read hackerearth article for basic terminology and graph representation

  2. Read the following articles for Breadth First Search (BFS) :
    (i) Hackerearth article on BFS
    (ii) CP-Algorithms article on BFS and its applications

  3. Read the following articles for Depth First Search (DFS) :
    (i) Hackerearth article on DFS
    (ii) CP-Algorithms article on DFS and its applications
    (iii) DFS using standard color coding and calculating discovery and finish times

  4. For better understanding of DFS and BFS, try DFS and BFS visualisation on VisuAlgo

Topological Sort

  1. Go through the hackerearth article or CP-Algorithms article for topological sort

Strongly Connected Components (SCC)

  1. Go through this article for Kosaraju's algorithm to find SCC
  2. For C++ implementation of the algorithm to find SCC, refer this article

Disjoint Set Union (DSU)

  1. Go through this article for DSU and its implementation.
  2. For more applications of DSU, refer this article

Shortest Path Algorithms

  • Read this article for the implementation of the standard shortest path algorithms - Dijkstra, Bellman Ford and Floyd Warshall.
tip

Do note the time and space complexities and the limitations of each method.

Minimum Spanning Tree (MST)

  • Go through this article for both Kruskal's and Prim's algorithm.

Session slides

  • Slides for basics of graph, graph representation and BFS, are available here

  • Slides for topological sort and SCC are available here

  • Slides for shortest-path algo, graph modeling and MST are available here

Additional Resource

  • Sometimes, in problems, it is required to construct a state graph out of the given graphs and then, apply any standard algorithm, to solve the problem. This technique is known as Graph Modelling. Refer this blog for more about it and some solved example problems.
Edit this page