# Graph Theory Tutorials

## Basics of Graph and Graph Traversals

Read hackerearth article for basic terminology and graph representation

Read the following articles for Breadth First Search (BFS) :

(i) Hackerearth article on BFS

(ii) CP-Algorithms article on BFS and its applicationsRead 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 timesFor better understanding of DFS and BFS, try DFS and BFS visualisation on VisuAlgo

## Topological Sort

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

## Strongly Connected Components (SCC)

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

## Disjoint Set Union (DSU)

- Go through this article for DSU and its implementation.
- 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.