Graph Algorithms

This course is all about a very important data structure which is obviously GRAPHS. This course is going to be very descriptive about GRAPH data structure where you will learn about the implementation of this data structure in C++ and a lot of other algorithms within the graph data structure!

This course demands learners to have an intermediate knowledge in C++ and must know how to work with classes and objects in C++. The course structure goes something like this :

1- Introduction to graph data structure

2- Fundamentals and types of graphs.

3- Implementation of graph data structure

1. Adjacency Matrix Representation of graphs.
2. Adjacency List representation of graphs.

4- Graph Traversals

1. Breadth First Search(BFS) or Level Order Traversal in Graphs.
2. Depth First Search(DFS) in Graphs.

5- Cycle detection in Graphs

1. Cycle detection in an undirected graph
2. using BFS
3. using DFS

1. Cycle detection in a directed graph
2. using DFS
3. using BFS(Pre-requisite : Topological ordering

6- Topological Ordering in Graphs

1. using BFS or Level Order Traversal(Kahn's Algorithm)
2. using DFS

7- Strongly Connected Components in Graphs(KOSARAJU ALGORITHM)

8- Shortest Path Algorithms

1. Single source shortest path(SSSP algorithm)
2. Dijkstra's Algorithm
3. Bellman Ford Algorithm
4. Floyd Warshall Algorithm

9- Bridges in a graph(TARJAN'S ALGORITHM)

10- Minimum Spanning Tree in a graphs

1. Disjoint Set Union(DSU)
2. Prims Algorithm
3. Kruskal's Algorithm(Pre-requisite : Disjoint Set Union(DSU))