Lecture 7: Minimum Spanning Trees
CSC 226: Algorithms and Data Structures II Quinton Yong
quintonyong@ uvic.ca
Copyright By PowCoder代写 加微信 powcoder
Weighted Graphs
• A weighted graph is a graph model where we associate weights (or costs) with each edge
• That is, each edge 𝒆 has a numeric label associated with it, denoted 𝒘(𝒆)
• We will look at algorithms for solving three general problems of weighted graphs • Minimumspanningtrees
• Shortestpaths • Networkflow
Weighted Edge API (Java Implementation)
public class Edge implements Comparable
Edge(int u, int v, double weight) // create a weighted edge v-w int either() // either endpoint of edge
int other(int u) // the endpoint that’s not u
int compareTo(Edge that) // compare this edge to that edge double weight() // the weight
String toString() // the endpoint that’s not u
𝒖 weight 𝒗
Weighted Graph Representation: Adjacency List
Maintain an array indexed by vertices which points to a list of adjacent vertices and weight of corresponding edge
𝟎 𝟏𝟕𝟑𝟓𝟐𝟏 𝟏𝟎𝟓𝟑𝟑 𝟐𝟎𝟏
𝟑 𝟎𝟓𝟏𝟑𝟒𝟏 𝟒𝟑𝟏 𝟓𝟔𝟑 𝟔𝟓𝟑
Minimum Spanning Tree Definition
Input: A weighted connected graph 𝑮 = (𝑽, 𝑬) consisting of vertices 𝑽 and edges 𝑬 with weights Output: A minimum spanning tree (MST) 𝑻 = (𝑽, 𝑬𝑻) of 𝑮. That is, 𝑻 is a connecting spanning
subgraph of 𝑮 where 𝑬𝑻 ⊆ 𝑬 such that 𝑻 is acyclic, and the total weight of 𝑻 𝒘𝑻=𝒘𝒆
is minimized.
Determining MST by Brute Force
• Create all spanning trees
• Pick the one with the smallest weight
• This is not feasible
• Acompletegraphon𝒏has𝒏𝒏−𝟐manyspanningtrees
Algorithm Design Technique: Greedy
• Applied to optimization problems, where the objective function is maximized or minimized
• Characterized by the greedy-choice property
• A globally optimal configuration can be reached by a series of locally optimal choices
• Optimal choices are choices that are the best among the possibilities available at the time
Prim’s Algorithm
• Initializetreewithsinglechosenvertex
• Grow tree by finding the lightest incident edge to all nodes in the spanning tree that’s not yet in
the tree and connect it to the tree
• Repeat until all vertices are in the tree
• Exampleofagreedyalgorithm
Kruskal’s Algorithm
• Initialize forest consisting of all nodes
• Pick a (non-selected) minimum weight edge and if it connects two different trees of the
forest, select it. Otherwise, discard it.
• Repeat until all components are connect it
• Exampleofagreedyalgorithm
• Why do these simple greedy algorithms work? (and produce correct minimum spanning trees)
• How do we implement these algorithms efficiently?
• What are good data structures to use?
Two basic facts about Trees
Let 𝑻 be a connected graph with no cycles, that is, a tree
• What happens if we add a new edge to 𝑻, without adding a new vertex?
• What happens if we remove an edge from 𝑻, without removing any vertices?
Two Fundamental Properties of MSTs
Cycle Property:
Let 𝑪 be any cycle in a weighted graph 𝑮 with distinct edge weights. Let 𝒆 be the “heaviest” edge in the cycle. Then the minimum spanning tree for 𝑮 does not contain 𝒆.
Cut Property:
Let 𝑿 be any proper subset (strictly less elements) of vertices in a weighted graph 𝑮 = (𝑽, 𝑬) with distinct edge weights, and let 𝒆 be the “lightest” edge that has exactly one endpoint in 𝑿. Then the minimum spanning tree 𝑻 for 𝑮 must contain 𝒆.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com