Princeton Alogorithm COS226 Week

given a undirected graph G with psotive edge weights (connected). a spanning tree of G is a subgraph T that is both tree( connected and acyclic) and spanning（includes all of the vertices）.
so minimum spanning tree is to find a min weight spanning tree.

image.png

MST application

image.png

if MST exists and is unique, we need cut property
A cut in a graph is a partition of its vertices into two nonempty sets.
a crossing edge connects a vertex in one set with a vertex in the other.

so cur property is given any cut, the crossing edge of min weight is in the MST.

image.png

so the greedy algorithm is

1. start with all edges colored gray
2. find cut with no black crossing edge; color its min-weight edge black
3. repeat until V - 1 edges are colored black

remove two simplifying assumption

image.png

weighted edge api

image.png image.png

minimum spanning tree api

image.png

Kruskal algorithm

consider edges in ascneding order of weight. add next edge to tree T unless doing so would create a cycle.

image.png
image.png

if edges are already sorted, the order of growth is E log*V, if not sorted, is E log E

Prim algorithm

start with vertex 0 and greedily grow tree T and add to T the min weight edge with exactly one endpoint in T. repeat until V - 1 edges

image.png
image.png

the time complexity of this algorithm is E log E

if we use indexed priority queue, we can get better performance.

image.png
then the basic plan is
delete min vertex v and add its associated edge e = v - w to T.
Update PQ by considering all edges e = v - x incident to v
ignore if x is already in T
add x to PQ if not already on it
decrease priority of x if v - x becomes shortest edge connecting x to T
now the time complexity will become E log V
add extra credit for this algorithm implementation

MST Application

image.png
image.png

QUIZ

Q1

image.png

the solution example is in https://en.wikipedia.org/wiki/Minimum_bottleneck_spanning_tree

i want to give a basic plan for O(n) algorithm

1. first check if the edge size is 1, just return the edge
2. find the median edge, and cut the graph with two edge set, one is less equal to median edge, another is larger than median edge.
3. if all the edge in small set could connected all the vertices. so we can run msbt(small set)
4. if not, we can keep all the edge in small set as part of result, then build a new graph to mark the connected component in small set as one vertex and use edge from big set. return msbt(new graph) and add the return result add to origin result.

Q2

image.png

we can consider all of the edge which weight is strictly less than that of e, if these graph can connect all of the vertex. then if we add this e, it must have a cycle.
so if it can not connect all of the vertex, this edge is in mst or not depend on if it could connect two point which not connect before.

so achieve above, we have two solution.

1. use union find to simulate the situation above.
2. use dfs, start from one vertex from this edge, then dfs, only choose the edge which weight smaller than this edge, check dfs can achieve another vertex from this edge. if can achieve, this edge should not in mst,or it will create a circle, and this edge is the largest weight.

Q3

image.png

first, we need to consider, this graph may not connected directly, so we need run completely PRIM to handle mst forest. then we need to use IndexMaxPQ to produce max spanning tree, because we need feedback edge set with minimum weight.
after get max spanning tree, all of the edges which not in it should be in the result.

course quiz and project : https://github.com/yixuaz/algorithm4-princeton-cos226