Graph. Set of vertices connected pairwise by edges.
Path. Sequence of vertices connected by edges.
Cycle. Path whose first and last vertices are the same.
Two vertices are connected if there is a path between them.
Path. Is there a path between s and t?
Shortest path. What is the shortest path between s and t?
Cycle. Is there a cycle in the graph?
Euler tour. Is there a cycle that uses each edge exactly once?
Hamilton tour. Is there a cycle that uses each vertex exactly once.
Connectivity. Is there a way to connect all of the vertices?
MST. What is the best way to connect all of the vertices?
Biconnectivity. Is there a vertex whose removal disconnects the graph?
Planarity. Can you draw the graph in the plane with no crossing edges?
Graph isomorphism. Do two adjacency lists represent the same graph?
Maintain vertex-indexed array of lists.
Design pattern. Decouple graph data type from graph processing.
- Create a Graph object.
- Pass the Graph to a graph-processing routine.
- Query the graph-processing routine for information.
To visit a vertex v:
- Mark vertex
- Recursively visit all unmarked vertices adjacent to
Goal. Find all vertices connected to s (and a corresponding path).
Idea. Mimic maze exploration.
- Use recursion (ball of string).
- Mark each visited vertex (and keep track of edge taken to visit it).
- Return (retrace steps) when no unvisited options.
booleanmarked to mark visited vertices.
intedgeTo to keep tree of paths.
edgeTo[w] == v) means that edge v-w taken to visit w for first time
Proposition. DFS marks all vertices connected to s in time proportional to the sum of their degrees.
Proposition. After DFS, can find vertices connected to s in constant time and can find a path to s (if one exists) in time proportional to its length.
Repeat until queue is empty:
- Remove vertex v from queue.
- Add to queue all unmarked vertices adjacent to v and mark them.
Depth-first search. Put unvisited vertices on a stack.
Breadth-first search. Put unvisited vertices on a queue.
Shortest path. Find path from s to t that uses fewest number of edges.
Proposition. BFS computes shortest paths (fewest number of edges) from s to all other vertices in a graph in time proportional to E + V.