Graph Traversal (cont)
COMP9312_22T2
Minimum spanning tree
Copyright By PowCoder代写 加微信 powcoder
Minimum Spanning Tree
In this topic, we will
• Define a spanning tree
• Define the weight of a spanning tree in a weighted graph • Define a minimum spanning tree
• Applications
• Solutions
Given 5 vertices, how many undirected edges are needed at least to connect these vertices together?
Given n vertices, how many undirected edges are needed at least to connect these vertices together?
Minimum Spanning Tree
In this topic, we will
• Define a spanning tree
• Define the weight of a spanning tree in a weighted graph • Define a minimum spanning tree
• Applications
• Solutions
Given 5 vertices, how many undirected edges are needed at least to connect these vertices together?
Given n vertices, how many undirected edges are needed at least to connect these vertices together?
Spanning trees
Given a connected graph with n vertices, a spanning tree is defined a collection of n – 1 edges which connect all n vertices.
• Thenverticesandn–1edgesdefineaconnectedsub-graph.
A spanning tree is not necessarily unique.
Spanning trees
Such a collection of edges is called a tree because if any vertex is taken to be the root, we form a tree by treating the adjacent vertices as children.
Spanning trees on weighted graphs
The weight of a spanning tree is the sum of the weights on all the edges which comprise the spanning tree
The weight of the above spanning tree is 20
The weight of the above spanning tree is 28
Minimum Spanning Trees
Which spanning tree which minimizes the weight? • Such a tree is termed a minimum spanning tree
The weight of this spanning tree is 14
Spanning forests
Suppose that a graph is composed of N connected vertex-induced sub-graphs
• Inthiscase,wemaydefineaspanningforestasacollectionofNspanningtrees,oneforeach
• AminimumspanningforestisthereforeacollectionofNminimumspanningtrees,onefor each connected vertex-induced sub-graph
connected vertex-induced sub-graph
Application
Consider supplying power to
• All circuit elements on a board
• A number of loads within a building
A minimum spanning tree will give the lowest-cost solution
www.commedore.ca
www.kpmb.com
Application
The first application of a minimum spanning tree algorithm was by the Czech mathematician Otakar Borůvka who designed electricity grid in Morovia in 1926
www.commedore.ca
www.kpmb.com
Application
Consider attempting to find the best means of connecting a number of LANs
• Minimize the number of bridges
• Costs not strictly dependant on distances
Application
Consider an ad hoc wireless network
• Any two terminals can connect with any others
• Errors in transmission increase with transmission length
• Can we find clusters of terminals which can communicate safely?
Application
Find a minimum spanning tree
Application
Remove connections which are too long
This clusters terminals into smaller and more manageable sub-networks
Prim’s Algorithm
Algorithms for finding MST
Prim’s algorithm for finding the minimum spanning tree states:
• Start with an arbitrary vertex to form a minimum spanning tree on one vertex
• At each step, add that vertex v not yet in the minimum spanning tree that has an edge
with least weight that connects v to the existing minimum spanning sub-tree • Continue until we have n – 1 edges and n vertices
Motivation for Prim’s algorithm
Suppose we take a vertex
• Given a single vertex e1, it forms a minimum spanning tree on one vertex
Motivation for Prim’s algorithm
Add that adjacent vertex v2 that has a connecting edge e1 of minimum weight • This forms a minimum spanning tree on our two vertices and e1 must be in any minimum
spanning tree containing the vertices v1 and v2
Motivation for Prim’s algorithm
• Suppose we have a known minimum spanning tree on k < n vertices • How could we extend this minimum spanning tree?
Motivation for Prim’s algorithm
Add that edge ek with least weight that connects this minimum spanning
tree to a new vertex vk + 1
• This does create a minimum spanning tree on k + 1 nodes—there is no other edge we could add that would connect this vertex
• Does the new edge, however, belong to the minimum spanning tree on all n vertices? Yes
Motivation for Prim’s algorithm
Proof: Suppose it does not
• Thus, vertex vk + 1 is connected to the minimum spanning tree via another sequence of edges
Motivation for Prim’s algorithm
Proof: Because a minimum spanning tree is connected, there must be a path from vertex vk + 1 back to our existing minimum spanning tree
• It must be connected along some edge e!
Motivation for Prim’s algorithm
Proof: Let w be the weight of this minimum spanning tree
• Recall, however, that when we chose to add vk + 1, it was because ek was the edge
connecting an adjacent vertex with least weight e! > ek
• Therefore ek – e! < 0 where |e| represents the weight of the edge e
Motivation for Prim’s algorithm
Proof: Consider, however, suppose we swap edges and instead choose to include ek and exclude e!
• The result is still a minimum spanning tree, but the weight is now w + ek +1 - e! £ w
vk + 1 ek + 1
Motivation for Prim’s algorithm
Proof: Thus, by swapping ek for e! , we have a spanning tree that has less weight than the so-called minimum spanning tree containing e!
• This contradicts our assumption that the spanning tree containing e! was minimal
• Therefore, our minimum spanning tree must contain ek
Recall that we did not prescribe the value of k, and thus, k could be any value, including k = 1
Prim’s Algorithm
Associate with each vertex three items of data: • A Boolean flag indicating if the vertex has been visited,
• The minimum distance to the partially constructed tree, and
• A pointer to that vertex which will form the parent node in the resulting tree
Prim’s Algorithm
Initialization:
• Select a root node and set its distance as 0 • Set the distance to all other vertices as ∞
• Set all vertices to being unvisited
• Set the parent pointer of all vertices to 0
Iterate while there exists an unvisited vertex with distance < ∞
– Selectthatunvisitedvertexwithminimumdistance
– Markthatvertexashavingbeenvisited
– Foreachadjacentvertex,iftheweightoftheconnectingedgeisless than the current distance to that vertex:
• Update the distance to equal the weight of the edge
• Set the current vertex as the parent of the adjacent vertex
Prim’s Algorithm
Stopping Conditions:
• There are no unvisited vertices which have a distance < ∞
If all vertices have been visited, we have a spanning tree of the entire graph
If there are vertices with distance ∞, then the graph is not connected and we only have a minimum spanning tree of the connected sub-graph containing the root
Prim’s Algorithm
Let us find the minimum spanning tree for the following undirected weighted graph.
First we set up the appropriate table and initialize it
Prim’s Algorithm
Visiting vertex 1, we update vertices 2, 4, and 5
Prim’s Algorithm
What these numbers really mean is that at this point, we could extend the trivial tree containing just the root node by one of the three possible children:
As we wish to find a minimum spanning tree, it makes sense we add that vertex with a connecting edge with least weight
Prim’s Algorithm
The next unvisited vertex with minimum distance is vertex 4 • Update vertices 2, 7, 8
• Don’t update vertex 5
Prim’s Algorithm
Now that we have updated all vertices adjacent to vertex 4, we can extend the tree by adding one of the edges
(1, 5), (4, 2), (4, 7), or (4, 8)
We add that edge with the least weight: (4, 2)
Prim’s Algorithm
Next visit vertex 2 • Update3,5,and6
Prim’s Algorithm
Again looking at the shortest edges to each of the vertices adjacent to the current tree, we note that we can add (2, 6) with the least increase in weight
Prim’s Algorithm
Next, we visit vertex 6: • update vertices 5, 8, and 9
Prim’s Algorithm
The edge with least weight is (2, 3)
• This adds the weight of 2 to the weight minimum spanning tree
Prim’s Algorithm
Next, we visit vertex 3 and update 5
Prim’s Algorithm
At this point, we can extend the tree by adding the edge (3, 5)
Prim’s Algorithm
Visiting vertex 5, we update 7, 8, 9
Prim’s Algorithm
At this point, there are three possible edges which we could include which will extend the tree
The edge to 8 has the least weight
Prim’s Algorithm
Visiting vertex 8, we only update vertex 9
Prim’s Algorithm
There are no other vertices to update while visiting vertex 9
Prim’s Algorithm
And neither are there any vertices to update when visiting vertex 7
Prim’s Algorithm
At this point, there are no more unvisited vertices, and therefore we are done
If at any point, all remaining vertices had a distance of ∞, this would indicate that the graph is not connected
• in this case, the minimum spanning tree would only span one connected sub-graph
Prim’s Algorithm
Using the parent pointers, we can now construct the minimum spanning tree
Prim’s Algorithm
To summarize:
• we begin with a vertex which represents the root
• starting with this trivial tree and iteration, we find the shortest edge which we can add to this already existing tree to expand it
This is a reasonably efficient algorithm: the number of visits to vertices is kept to a minimum
Implementation and analysis
The initialization requires O(|V|) memory and run time
We iterate |V| – 1 times, each time finding the closest vertex
• Iterating through the table requires is O(|V|) time
• Each time we find a vertex, we must check all of its neighbors
• With an adjacency matrix, the run time is O(|V|(|V| + |V|)) = O(|V|2)
• With an adjacency list, the run time is O(|V|2 + |E|) = O(|V|2) as |E| = O(|V|2)
Can we do better?
Recall, we only need the vertex with the shortest distance next How about a min heap?
Min-heap-based optimization
The initialization still requires O(|V|) memory and run time
– TheminheapwillalsorequireO(|V|)memorywhichcontainsthedistanceofall
the vertices
We iterate |V| – 1 times, each time finding the closest vertex
– ObtaintheshortestdistancefromtheminheapO(1),maintaintheheapO(log(|V|))
– Thus,theworkrequiredforthisisO(|V|log(|V|)) Is this all the work that is necessary?
– Recallthatfortheclosestvertexinaniteration,wetrytoupdatethedistanceof all its neighbors, thus there are O(|E|) updates in total and each update in the heap requires O(log(|V|)).
– Thus,theworkrequiredforthisisO(|E|log(|V|))
Thus, the total run time is O(|V| log(|V|) + |E| log(|V|)) = O(|E| log(|V|))
a min heap
Min-heap-based optimization
1𝑑=0 2𝑑=∞ 3𝑑=∞
4𝑑=∞ 5𝑑=∞6𝑑=∞ 7𝑑=∞ 𝑑=∞ 9𝑑=∞
Min-heap-based optimization
9𝑑=∞ 5𝑑=86𝑑=∞ 7 𝑑=∞
Visiting vertex 1, we update vertices 2, 4, and 5
Kruskal’s Algorithm
Kruskal’s Algorithm
Kruskal’s algorithm sorts the edges by weight and goes through the edges from least weight to greatest weight adding the edges to an empty graph so long as the addition does not create a cycle
The halting point is:
• When |V| – 1 edges have been added
• In this case we have a minimum spanning tree
• We have gone through all edges, in which case, we have a forest of minimum spanning trees on all connected sub-graphs
Consider the game of Risk from • A game of world domination
• The world is divided into 42 connected regions
• The regions are vertices and edges indicate adjacent regions
http://thunderbird37.com/tag/parker-brothers/
Here is our abstract representation of Asia. Let us give a weight to each of the edges. First, we sort the edges based on weight.
{C, E} {H, I} {G, I} {F, G} {B, E} {E, H} {B, C} {H, K} {H, L} {D, E} {G, H} {I, K} {B, D} {D, F} {E, G} {K, L} {J, K} {J, I} {J, G} {A, B} {A, D}
{E, F} 22T2
We start by adding edge {C, E}
{G, I} {F, G}
{B, E} {E, H} {B, C} {H, K} {H, L} {D, E} {G, H} {I, K} {B, D} {D, F} {E, G} {K, L} {J, K} {J, I} {J, G} {A, B}
58 {A, D} 22T2 {E, F}
We add edge {H, I}
{C, E} {H, I} {G, I} {F, G} {B, E} {E, H} {B, C} {H, K} {H, L} {D, E} {G, H} {I, K} {B, D} {D, F} {E, G} {K, L} {J, K} {J, I} {J, G} {A, B}
{A, D} 22T2 {E, F}
We add edge {G, I}
{C, E} {H, I} {G, I} {F, G} {B, E} {E, H} {B, C} {H, K} {H, L} {D, E} {G, H} {I, K} {B, D} {D, F} {E, G} {K, L} {J, K} {J, I} {J, G} {A, B}
60 {A, D} 22T2 {E, F}
We add edge {F, G}
{C, E} {H, I} {G, I} {F, G} {B, E} {E, H} {B, C} {H, K} {H, L} {D, E} {G, H} {I, K} {B, D} {D, F} {E, G} {K, L} {J, K} {J, I} {J, G} {A, B}
61 {A, D} 22T2 {E, F}
We add edge {B, E}
{C, E} {H, I} {G, I} {F, G} {B, E} {E, H} {B, C} {H, K} {H, L} {D, E} {G, H} {I, K} {B, D} {D, F} {E, G} {K, L} {J, K} {J, I} {J, G} {A, B}
62 {A, D} 22T2 {E, F}
We add edge {E, H}
• This coalesces the two spanning sub-trees into one
{C, E} {H, I} {G, I} {F, G} {B, E} {E, H} {B, C} {H, K} {H, L} {D, E} {G, H} {I, K} {B, D} {D, F} {E, G} {K, L} {J, K} {J, I} {J, G} {A, B}
63 {A, D} 22T2 {E, F}
We try adding {B, C}, but it creates a cycle
{C, E} {H, I} {G, I} {F, G} {B, E} {E, H} {B, C} {H, K} {H, L} {D, E} {G, H} {I, K} {B, D} {D, F} {E, G} {K, L} {J, K} {J, I} {J, G} {A, B}
64 {A, D} 22T2 {E, F}
We add edge {H, K}
{C, E} {H, I} {G, I} {F, G} {B, E} {E, H} {B, C} {H, K} {H, L} {D, E} {G, H} {I, K} {B, D} {D, F} {E, G} {K, L} {J, K} {J, I} {J, G} {A, B}
65 {A, D} 22T2 {E, F}
We add edge {H, L}
{C, E} {H, I} {G, I} {F, G} {B, E} {E, H} {B, C} {H, K} {H, L} {D, E} {G, H} {I, K} {B, D} {D, F} {E, G} {K, L} {J, K} {J, I} {J, G} {A, B}
66 {A, D} 22T2 {E, F}
We add edge {D, E}
{C, E} {H, I} {G, I} {F, G} {B, E} {E, H} {B, C} {H, K} {H, L} {D, E} {G, H} {I, K} {B, D} {D, F} {E, G} {K, L} {J, K} {J, I} {J, G} {A, B}
67 {A, D} 22T2 {E, F}
We try adding {G, H}, but it creates a cycle
{C, E} {H, I} {G, I} {F, G} {B, E} {E, H} {B, C} {H, K} {H, L} {D, E} {G, H} {I, K} {B, D} {D, F} {E, G} {K, L} {J, K} {J, I} {J, G} {A, B}
68 {A, D} 22T2 {E, F}
We try adding {I, K}, but it creates a cycle
{C, E} {H, I} {G, I} {F, G} {B, E} {E, H} {B, C} {H, K} {H, L} {D, E} {G, H} {I, K} {B, D} {D, F} {E, G} {K, L} {J, K} {J, I} {J, G} {A, B}
69 {A, D} 22T2 {E, F}
We try adding {B, D}, but it creates a cycle
{C, E} {H, I} {G, I} {F, G} {B, E} {E, H} {B, C} {H, K} {H, L} {D, E} {G, H} {I, K} {B, D} {D, F} {E, G} {K, L} {J, K} {J, I} {J, G} {A, B}
70 {A, D} 22T2 {E, F}
We try adding {D, F}, but it creates a cycle
{C, E} {H, I} {G, I} {F, G} {B, E} {E, H} {B, C} {H, K} {H, L} {D, E} {G, H} {I, K} {B, D} {D, F} {E, G} {K, L} {J, K} {J, I} {J, G} {A, B}
71 {A, D} 22T2 {E, F}
We try adding {E, G}, but it creates a cycle
{C, E} {H, I} {G, I} {F, G} {B, E} {E, H} {B, C} {H, K} {H, L} {D, E} {G, H} {I, K} {B, D} {D, F} {E, G} {K, L} {J, K} {J, I} {J, G} {A, B}
72 {A, D} 22T2 {E, F}
By observation, we can still add edges {J, K} and {A, B}
{C, E} {H, I} {G, I} {F, G} {B, E} {E, H} {B, C} {H, K} {H, L} {D, E} {G, H} {I, K} {B, D} {D, F} {E, G} {K, L} {J, K} {J, I} {J, G} {A, B}
73 {A, D} 22T2 {E, F}
Having added {A, B}, we now have 11 edges • We terminate the loop
• We have our minimum spanning tree
{C, E} {H, I} {G, I} {F, G} {B, E} {E, H} {B, C} {H, K} {H, L} {D, E} {G, H} {I, K} {B, D} {D, F} {E, G} {K, L} {J, K} {J, I} {J, G} {A, B}
74 {A, D} 22T2 {E, F}
Implementation
• We would store the edges and their weights in an array
• We would sort the edges using either quicksort or some distribution sort
• To determine if a cycle is created, we could perform a BFS traversal
• Arun-timeofO(|V|)
• Consequently, the run-time would be O(|E| log(|E|) + |E|·|V|)
• However, |E| = O(|V|2), so log(E) = O(log(|V|2)) = O(2 log(|V|)) = O(log(|V|)) • Consequently, the run-time would be O(|E| log(|E|) + |E||V|) = O(|E|·|V|)
The critical operation is determining if two vertices are connected
Instead, we could use disjoint sets
• Consider edges in the same connected sub-graph as forming a set
• If the vertices of the next edge are in different sets, take the union of the two sets • Do not add an edge if both vertices are in the same set
Add edge (E, H)?
{B, C, E}, {F, G, H, I}
{B, C, E, F, G, H, I}
The disjoint set data structure has the following average run-times: • Checking if two vertices are in the same set is almost linear
• Taking the union of two disjoint sets is almost linear
Thus, checking and building the minimum spanning tree is now O(|E|) The dominant time is now the time required to sort the edges:
• Using quicksort, the run-time is O(|E| log(|E|))
Going through the example again with disjoint sets. We start with twelve singletons
{A}, {B}, {C}, {D}, {E}, {F}, {G}, {H}, {I}, {J}, {K}, {L}
Initialization:
For each vertex 𝑢! ∈ [𝐴, 𝐿], each vertex direct to themselves.
{C, E} {H, I} {G, I} {F, G} {B, E} {E, H} {B, C} {H, K} {H, L} {D, E} {G, H} {I, K} {B, D} {D, F} {E, G} {K, L} {J, K} {J, I} {J, G} {A, B} {A, D}
{E, F} 22T2
We start by adding edge {C, E}
{A}, {B}, {C, E}, {D}, {F}, {G}, {H}, {I}, {J}, {K}, {L}
{G, I} {F, G}
{B, E} {E, H} {B, C} {H, K} {H, L} {D, E} {G, H} {I, K} {B, D} {D, F} {E, G} {K, L} {J, K} {J, I} {J, G} {A, B}
79 {A, D} 22T2 {E, F}
We add edge {H, I}
{A}, {B}, {C, E}, {D}, {F}, {G}, {H, I}, {J}, {K}, {L}
{C, E} {H, I} {G, I} {F, G} {B, E} {E, H} {B, C} {H, K} {H, L} {D, E} {G, H} {I, K} {B, D} {D, F} {E, G} {K, L} {J, K} {J, I} {J, G} {A, B}
{A, D} 22T2 {E, F}
Similarly, we add {G, I}, {F, G}, {B, E}
Add {G,I}: According to the rule of Union by Size, make smaller tree point to bigger one’s root.
{C, E} {H, I} {G, I} {F, G} {B, E} {E, H} {B, C} {H, K} {H, L} {D, E} {G, H} {I, K} {B, D} {D, F} {E, G} {K, L} {J, K} {J, I} {J, G} {A, B}
{A, D} 22T2 {E, F
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com