A graph is a set of vertices joined by edges, and almost anything with connections can be modelled as one: roads, networks, dependencies, friendships, molecules. Graph theory studies their structure and the algorithms on them. A well-chosen graph often turns a messy question into a standard problem with a known solution.
Key concepts
- Representations: adjacency lists suit sparse graphs, adjacency matrices dense ones.
- Traversal: breadth-first search finds fewest-edge paths; depth-first search gives ordering, cycles and components.
- Shortest paths: Dijkstra's algorithm for non-negative weights, Bellman-Ford when weights can be negative.
- Spanning trees: Kruskal's and Prim's algorithms connect all vertices at minimum total weight.
- Flows and matchings: maximum flow equals minimum cut; matching pairs vertices without sharing.
Vocabulary
- Directed and undirected: whether edges have a direction.
- DAG: directed acyclic graph, the shape of dependencies, which can be topologically sorted.
- Connected component: a maximal set of vertices all reachable from each other.
- Planar graph: one that can be drawn with no crossing edges.
What to study, in order
- Build a graph class with adjacency lists and read a graph from a file.
- Implement BFS and DFS and use them for connected components and cycle detection.
- Implement Dijkstra with a priority queue and check it against a brute-force search.
- Add topological sort, minimum spanning tree and strongly connected components.
- Model a real problem as a flow or a matching and solve it.
Related tags
#algorithms #combinatorics #discrete-math #data-structures #knowledge-graphs