A graph is a structure for representing relationships that are not naturally linear. Once the course reaches graphs, the main skill is to separate the abstract object from the representation and then choose the traversal or optimization method that matches the question.
Graph vocabulary
Definition
Graph
A graph consists of vertices and edges. Edges may be directed or undirected, and they may also carry weights.
Directed edges have orientation: (u, v) is not the same as (v, u).
Weighted edges carry a cost, distance, or capacity. Those two features change
which algorithms make sense.
The local lecture material also distinguishes paths, simple paths, cycles, acyclic graphs, connectivity, and degree. These terms are not decoration; they decide whether an algorithm is even applicable.
Representations
The two most common representations are adjacency matrices and adjacency lists.
- An adjacency matrix gives constant-time edge lookup, but it uses space proportional to the square of the number of vertices.
- An adjacency list stores neighbors of each vertex, making it more natural for sparse graphs where the number of edges is much smaller than .
When analyzing graph algorithms, always state the representation or express the cost using both and .
Depth first search
DFS explores as far as possible along a branch before backtracking. The tutorial traces this with a stack of current nodes and a visited array.
Definition
Depth first search
DFS visits a start vertex, recursively or explicitly explores one unvisited neighbor path as far as possible, then backtracks when no unvisited neighbor is available.
DFS is useful for reachability, connected components, cycle-related reasoning, and DFS-based topological sorting.
Breadth first search
BFS visits vertices by distance layers from the starting vertex. The tutorial uses a queue rather than a stack.
Definition
Breadth first search
BFS visits the start vertex, then all vertices at distance one, then all vertices at distance two, and so on, using a queue to preserve layer order.
In an unweighted graph, BFS gives shortest path distances measured by number of edges. DFS does not guarantee that.
Minimum spanning trees
For a connected undirected weighted graph, a spanning tree contains all vertices and exactly edges. A minimum spanning tree minimizes the total edge weight.
Kruskal's algorithm sorts edges by weight and adds the next lightest edge that does not create a cycle. Prim's algorithm grows one tree, repeatedly adding the lightest edge that connects the current tree to a new vertex.
Theorem
What MST algorithms protect
Both Kruskal's and Prim's algorithms preserve acyclicity while adding the cheapest safe edge according to their current view of the graph.
Dijkstra-style shortest paths
Dijkstra's algorithm solves a different problem: shortest paths from a start vertex to other vertices in a weighted graph with nonnegative edge weights. It keeps the best known cost to each vertex, repeatedly finalizes the unvisited vertex with smallest current cost, and relaxes outgoing edges from that vertex.
The meaning of "visited" is strong: once a vertex is finalized, the shortest path to it has been found.
Quick check
Which traversal uses a queue: DFS or BFS?
Think about layer order.
Solution
Answer
Quick check
Why does an MST have exactly V minus 1 edges?
Assume the graph is connected and the spanning subgraph is a tree.
Solution
Answer
Exercises
- Explain when an adjacency list is preferable to an adjacency matrix.
- Explain why BFS gives shortest paths in unweighted graphs.
- Distinguish the MST problem from the single-source shortest path problem.
Solution