Depth first search
CS122 Algorithms and Data Structures
n
n
n
n
n
MW 11:00 am - 12:15 pm, MSEC 101
Instructor: Xiao Qin
Lecture 15: Graphs (2)
Starting from vertex v
Mark v as marked
Select u as an unmarked node adjacent to v
If no u, quit
If u, begin depth first search from u
When search from u quits, select another
node from v
Similar to preorder tree traversal
Breadth first search
n
n
n
n
n
n
An Example
Starting from node v
Identify all nodes adjacent to v
Add these to the set
Determine set of unvisited nodes which
are adjacent to this set
Add these to the set
Continue until no new nodes are
encountered
What would the visit orders for
DFS(1), DFS(5), BFS(1), BFS(5)
look like?
3
Unweighted Shortest Path
Algorithm
Find the shortest path (measured by
number of edges) from a designated
vertex S to every vertex
n Simplified case of weighted shortest
path
n
n
n
n
n
n
Starting from node S
Distance from S to S is 0, so label as 0
Find all nodes which are distance 1 from S
Label as distance 1
Find all nodes which are distance 2 from S
These are 1 step from those labeled 1
This is precisely a breadth first search
6
Positive Weighted Shortest Path
n
n
n
n
n
Distance at each node v is shorted path
distance from s to v using only known
vertices as intermediates
n An example of a Greedy Algorithm
n Solve problem in stages by doing what
appears to be the best thing at each
stage
n Decision in one stage is not changed
later
n
Length is sum of the edges costs on the
path
All edges have nonnegative cost
Find shortest paths from some start
vertex to all vertices
similar process to unweighted case
Dijkstra's Algorithm
7
start at v1, all distances are infinity
2
1
2
10
4
3
1
2
2
3
4
5
8
4
5
6
1
6
7
Ford Algorithm
mark v1 is removed from the toBeChecked set, with distance 0
0
2
1
2
10
4
3
1
2
2
3
4
5
8
4
5
6
1
6
7
FordAlgorithm(G, s)
for all vertices v do
dist[v] = ; p[v] = NULL;
dist[s] = 0;
while there is (v,u) that dist[u]>dist[v] + weight(v,u) do
dist[u] = dist[v] + weight(v,u);
p[u] = v;
endwhile
10
Spanning tree
Minimum spanning tree
subgraph of G
contains all vertices of G
n connected graph with no cycles
spanning tree with minimum cost
only exists if G is connected
n number of edges is |V|-1
n two greedy methods
Kruskal's algorithm
Prim's algorithm
n
11
differ in how next edge is selected
12
Kruskal's algorithm
n
Construct MST for this graph using Kruskal's algorithm
2
1
2
10
4
3
1
2
7
3
4
5
8
4
6
5
1
6
7
select edge with smallest weight as accept
the edge if it does not cause a cycle
determining if it causes a cycle: essentially
the equivalence class (union/find) problem
two vertices belong to the same set iff they
are connected in the current spanning forest
4
2
4
8
2
3
10
4
1
13
14
Prim's algorithm
Prim's algorithm (cont.)
grow the tree in successive stages
n in each stage, one node is picked as the
root, we add an edge, and thus a vertex
is added to the tree
n have a set on vertices in the tree and a
set that is not in the tree
15
at each stage, a new vertex to add to
the tree is selected by choosing edge
(u, v) such that the cost of (u,v) is the
smallest among all edges where u is in
the tree and v is not
n Build spanning tree starting from v1
n Result in the same spanning tree as
that given by the Kruskal algorithm
16
Construct MST from v1 for this graph using Prim's algorithm
2
4
2
4
8
1
2
4
8
10
2
3
10
4
1
6
17
