Graphs
Graphs are versatile data structures consisting of vertices (nodes) and edges (connections). They model relationships and networks, from social connections to routing algorithms, making them essential for solving complex real-world problems.
Key points
- Directed vs Undirected, Weighted vs Unweighted
- Representations: Adjacency Matrix, Adjacency List
- Traversals: BFS (shortest path), DFS (connectivity)
- Shortest path: Dijkstra, Bellman-Ford, Floyd-Warshall
- Minimum Spanning Tree: Prim's, Kruskal's algorithms
Problems
Number of Islands
Coming soonCount connected components in 2D grid
DFSBFSUnion Find
Clone Graph
Coming soonDeep copy an undirected graph
DFSBFSHash Map
Course Schedule
Coming soonDetect cycle in directed graph (topological sort)
Topological SortDFS
Pacific Atlantic Water Flow
Coming soonFind cells that can flow to both oceans
DFSMatrix
Network Delay Time
Coming soonFind minimum time for signal to reach all nodes
DijkstraShortest Path