This lesson includes an expert video walkthrough — purchase once for a full year of unlimited replays to master every key point 🎬
Graph Connectivity
Knowledge Summary
Concepts of Connectivity
- Connected: in an undirected graph, there is a path between two vertices
- Connected graph: an undirected graph in which every pair of vertices is connected
- Connected component: a maximal connected subgraph of an undirected graph
- Strongly connected: in a directed graph, there is a path from u to v and from v to u
- Strongly connected graph: a directed graph in which every pair of vertices is strongly connected
The Relationship Between Trees and Graphs
- A tree is a special graph: connected and acyclic
- A tree with n vertices has exactly n-1 edges
- Adding one edge to a tree must create a cycle
- Removing one edge from a tree must make it disconnected
Spanning Trees
- A spanning tree of a connected graph is a minimal connected subgraph containing all vertices
- A spanning tree of a connected graph with n vertices has n-1 edges
- A minimum spanning tree (MST) is a spanning tree with the minimum total edge weight
Minimum Spanning Tree Algorithms
| Algorithm | Idea | Time Complexity |
|---|---|---|
| Kruskal | Sort edges by weight and greedily choose edges | O(m log m) |
| Prim | Start from one vertex and expand step by step | O(n²) or O(m log n) |
Frequently Tested Points
- Determine whether a graph is connected
- Find the number of connected components
- Minimum number of edges required to connect n vertices (answer: n-1)
- Number of edges in a spanning tree