Transcript PPT printable - Simpson College

Mark Allen Weiss: Data Structures and Algorithm Analysis in Java
Chapter 9: Graphs
Spanning Trees
Lydia Sinapova, Simpson College
Spanning Trees
 Spanning Trees in Unweighted
Graphs
 Minimal Spanning Trees in Weighted
Graphs - Prim’s Algorithm
 Minimal Spanning Trees in Weighted
Graphs - Kruskal’s Algorithm
 Animation
2
Definitions
Spanning tree: a tree that contains all vertices
in the graph.
Number of nodes: |V|
Number of edges: |V|-1
3
Spanning trees for unweighted
graphs - data structures
A table (an array) T
size = number of vertices,
Tv= parent of vertex v
Adjacency lists
A queue of vertices to be processed
4
Algorithm - initialization
1. Choose a vertex S and store it in a queue,
set
a counter = 0 (counts the processed nodes),
and Ts = 0 (to indicate the root),
Ti = -1 ,i  s (to indicate vertex not
processed)
5
Algorithm – basic loop
2. While queue not empty and counter < |V| -1 :
Read a vertex V from the queue
For all adjacent vertices U :
If Tu = -1 (not processed)
Tu  V
counter  counter + 1
store U in the queue
6
Algorithm
– results and complexity
Result:
Root: S, such that Ts = 0
Edges in the tree: (Tv , V)
Complexity: O(|E| + |V|) - we process
all edges and all nodes
7
Example
2
3
1
Table
0
// 1 is the root
1 // edge (1,2)
2 // edge (2,3)
4
5
1 // edge (1,4)
2 // edge (2,5)
Edge format: (Tv,V)
8
Minimum Spanning Tree Prim's algorithm
Given: Weighted graph.
Find a spanning tree with the minimal sum
of the weights.
Similar to shortest paths in a weighted graphs.
Difference: we record the weight of the
current edge, not the length of the path .
9
Data Structures
A table : rows = number of vertices,
three columns:
T(v,1) = weight of the edge from
parent to vertex V
T(v,2) = parent of vertex V
T(v,3) = True, if vertex V is fixed in the tree,
False otherwise
10
Data Structures (cont)
Adjacency lists
A priority queue of vertices to be processed.
Priority of each vertex is determined by
the weight of edge that links the vertex
to its parent.
The priority may change if we change
the parent, provided the vertex is not yet
fixed in the tree.
11
Prim’s Algorithm
Initialization
For all V, set
first column to –1 (not included in the tree)
second column to 0 (no parent)
third column to False (not fixed in the tree)
Select a vertex S, set T(s,1) = 0 (root: no parent)
Store S in a priority queue with priority 0.
12
While (queue not empty) loop
1. DeleteMin V from the queue, set T(v,3) = True
2. For all adjacent to V vertices W:
If T(w,3)= True do nothing – the vertex is fixed
If T(w,1) = -1 (i.e. vertex not included)
T(w,1)  weight of edge (v,w)
T(w,2)  v (the parent of w)
insert w in the queue with
priority = weight of (v,w)
13
While (queue not empty) loop
(cont)
If T(w,1) > weight of (v,w)
T(w,1)  weight of edge (v,w)
T(w,2)  v (the parent of w)
update priority of w in the queue
remove, and insert with new priority
= weight of (v,w)
14
Results and Complexity
At the end of the algorithm, the tree
would be represented in the table with its
edges
{(v, T(v,2) ) | v = 1, 2, …|V|}
Complexity: O(|E|log(|V|))
15
Kruskal's Algorithm
The algorithm works with :
set of edges,
tree forests,
each vertex belongs to only one
tree in the forest.
16
The Algorithm
1. Build |V| trees of one vertex only - each vertex
is a tree of its own. Store edges in priority queue
2. Choose an edge (u,v) with minimum weight
if u and v belong to one and the same tree,
do nothing
if u and v belong to different trees,
link the trees by the edge (u,v)
3. Perform step 2 until all trees are combined into
one tree only
17
Example
Edges in
Priority
Queue:
1
1
2
4
3
5
6
4
3
2
4
5
(1,2)
(3,5)
(2,4)
(1,3)
(4,5)
(2,5)
(1,5)
1
2
3
4
4
5
6
18
Example (cont)
Forest of 5 trees
1
2
3
4
5
Edges in
Priority Queue:
(1,2)
(3,5)
(2,4)
(1,3)
(4,5)
(2,5)
(1,5)
1
2
3
4
4
5
6
Process edge (1,2)
1
1
2
3
4
5
Process edge (3,5)
1
1
2
4
2
3
5
19
Edges in
Priority
Queue:
(2,4)
(1,3)
(4,5)
(2,5)
(1,5)
Example (cont)
3
4
4
5
6
Process edge (2,4)
1
1
2
3
2
3
5
4
Process edge (1,3)
1
1
2
4
3
2
3
5
4
All trees are
combined in
one, the
algorithm
stops
20
Operations on Disjoint Sets
Comparison: Are the vertices in the same tree
Union: combine two disjoint sets to form one set the new tree
Implementation
Union/find operations: the unions are represented
as trees - nlogn complexity.
The set of trees is implemented by an array.
21
Complexity of Kruskal’s
Algorithm
O(|E|log(|V|)
Explanation:
The complexity is determined by the heap operations and the
union/find operations
Union/find operations on disjoint sets represented as trees:
tree search operations, with complexity O(log|V|)
DeleteMin in Binary heaps with N elements is O(logN),
When performed for N elements, it is O(NlogN).
22
Complexity (cont)
Kruskal’s algorithm works with a binary heap that
contains all edges: O(|E|log(|E|))
However, a complete graph has
|E| = |V|*(|V|-1)/2, i.e. |E| = O(|V|2)
Thus for the binary heap we have
O(|E|log(|E|)) = O(|E|log (|V|2) = O(2|E|log (|V|)
= O(|E|log(|V|))
23
Complexity (cont)
Since for each edge we perform DeleteMin
operation and union/find operation, the overall
complexity is:
O(|E| (log(|V|) + log(|V|)) =
O(|E|log(|V|))
24
Discussion
Sparse trees - Kruskal's algorithm :
Guided by edges
Dense trees - Prim's algorithm :
The process is limited by the
number of the processed vertices
25