- Undirected Graphs
average degree:
Paste_Image.png
- DFS, depth first search
example trace:
Paste_Image.png
The output is 0-2-1-3-5-4.
DFS implementation:
Paste_Image.png
Proposition A. DFS marks all the vertices connected to a given source in time proportional to the sum of their degrees.
Paste_Image.png
Why the preprocessing time is E + V?
For example:
Paste_Image.png
The source is s. s has adjacent vertices A, C, D.
The trace will be:
Stack: s a b c d
output: s a b c d e v
- BFS, breadth-first search:
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.
Paste_Image.png
