Graph & Network Modeling¶
Graph and network modeling techniques are essential for solving problems involving relationships, connections, and hierarchical structures. These algorithms form the foundation for many real-world applications including social networks, transportation systems, and computer networks.
Techniques in This Category¶
| Technique | Description | Link |
|---|---|---|
| Graph Terminology & Representation | Vocabulary, adjacency list vs matrix, weighted graphs. | Graph Basics |
| DFS / BFS | Depth-first and breadth-first traversal. | DFS / BFS |
| Dijkstra / Bellman-Ford | Single-source shortest paths (non-negative vs general weights). | Dijkstra / Bellman-Ford |
| Floyd–Warshall | All-pairs shortest paths in \(O(n^3)\). | Floyd–Warshall |
| Union-Find | Disjoint sets for connectivity and Kruskal’s MST. | Union-Find |
| Minimum Spanning Tree | Kruskal and Prim for minimum-weight spanning trees. | Minimum Spanning Tree |
| Tree Algorithms | Diameter and longest paths in trees. | Tree Algorithms |
| LCA & Tree Queries | Lowest common ancestor, distances on trees, subtree ideas. | LCA & Tree Queries |
| Strong Connectivity & 2SAT | SCC (e.g. Kosaraju) and 2-satisfiability. | Strong Connectivity & 2SAT |
| Eulerian & Hamiltonian | Euler paths/circuits vs Hamiltonian (hard) paths. | Eulerian & Hamiltonian |
| Flows & Matchings | Max flow, bipartite matching, path covers in DAGs. | Flows & Matchings |
When to Use Graph Algorithms¶
Graph techniques are essential when: - Data has inherent relationships or connections - You need to find paths, cycles, or connectivity - Working with hierarchical or network structures - Solving optimization problems on connected components
Common Graph Problems¶
- Shortest Path: Finding the minimum cost path between nodes
- Connectivity: Determining if nodes are reachable from each other
- Cycle Detection: Identifying cycles in directed or undirected graphs
- Topological Sorting: Ordering nodes based on dependencies
- Minimum Spanning Tree: Finding the minimum cost tree connecting all nodes