Introduction to Intermediate Graph Theory
Date: February 8, 2021
Conducted By: Rishik and Hemant
Agenda
-
How to apply DFS for detecting a cycle in a graph?
- Dynamically coloring nodes white, grey and black.
- Why does it work?
-
How to apply DFS for finding out if a path exists between two nodes?
- Using simple DFS bruteforce to check.
- Component coloring to answer multiple queries.
-
Dijkstra
- Introduction to Priority Queue
- Why is Priority Queue needed for Dijkstra?
- Functioning of Dijkstra Algorithm.
- Negative Implementation of Dijkstra Algorithm.
Resources
- Cycle Detection using DFS
- Component Coloring using DFS
- Dijkstra Implementation using Sets
- Dijkstra Implementation using PQ
Further Reading
- Graph Theory 2 - Hackerearth
- William Fiset - Graph Theory Playlist
- Algorithm Gym :: Graph Algorithms - Codeforces