In this course, you will :
- Learn how to represent graphs as data structures.
- Search algorithms are used to traverse graphs.
- In graphs, find the shortest paths.
- Find the most possible matches.
- Solve flow issues.
- Calculate the minimum spanning trees.
- Learn the fundamental concepts of graph theory as well as how to represent graphs as data structures in code.
- Learn how to solve more complex optimization problems on graphs, such as matching and network flow.
1. Graph Representations
- Adjacency Matrix
- Adjacency List
- Representing Weighted Graphs
- Comparison of Graph Representations
2. Graph Traversal
- Depth-first Search (DFS)
- Implementation of DFS
- Breadth First Search (BFS)
- Implementation of BFS
- Application 1: Topological Sort
- Application 2: Strongly Connected Components
- Implementation of Kosaraju's Algorithm
3. Shortest Paths
- Shortest Path Problems
- Dijkstra's Algorithm for the SSSP
- Implementation of Dijkstra
- Floyd-Warshall Algorithm for the ASSP
- Implementation of Floyd-Warshall
4. Spanning Trees
- The Minimum Spanning Tree Problem
- Kruskal's Algorithm
- Implementation of Kruskal's Algorithm
5. Flow Problems
- The Max Flow Problem
- The Ford-Fulkerson Method
- Max Flow = Min Cut
- Implementation of Ford Fulkerson (Edmonds-Karp)