Minimum spanning trees

Question 1

What are the assumptions for MSTs?

Answer 1

• Connected
• Edge weights arent distances
• Edge weights may be zero or negative
• Edge weights are all different

Question 2

What is the cut property?

Answer 2

Cut of graph is a partition of its vertices into two nonempty disjoint sets

Question 3

What is a crossing edge of a cut?

Answer 3

Edge that connects vertex in one set with vertex in another

Question 4

What does the cut property allow us to find and why?

Answer 4

Given any cut in WG, corissing edge of minimum weight is in MST.
Let e = CE of min weight and T be the MST

Suppose T d.n contain e:
* Graph formed by addign e to MST has a cycle that contains e which contains one other crossing edge f which has heigher weight than e (Because of tree property)
* We can get a MST of lower weight by deleting f and adding e, contradicting assumed minimality of T.

If there is a road with min weight that acts as crossing edge, then that edge must be in the MST, otherwise there exists a tree with less weight.

Question 5

How can we use the cut property to create a greedy algorithm for building an MST?

Answer 5

Apply cut property to accept an edge as MST edge, continuing until all MST edges found.
* Find cut with no already marked MST edges
* Mark minimum-weight edge
* Continue until V - 1 edges marked

Question 6

What are the data structures used for Prim’s Algorithm?

Answer 6

• Vertices on tree stored on vertex-indexed Boolean array marked[], where true if on tree
• Edges on Queue mst to collect MST edges or edgeTo[] of Edge objects where edgeTo[v] is edge that connects v to tree
• Crossing edges on MinPQ<Edge> priority queue that compares edges by weight.

Question 7

How is the set of crossing edges maintained?

Answer 7

Adding edge and vertex, adding to PQ all edges from that vertex to any non-tree vertex (using marked[] to identify)
Any edge connecting the veretx just added, to a tree veretx already on the PQ, becomes ineligible because it connects two tree vertices.

Question 8

What is the space and time usage of Prim’s lazy?

Answer 8

Space: E
Time: E log E

Question 9

What is the idea behind the eager version of Prim’s algorithm?

Answer 9

Delete ineligible edges from PQ so that it contains only crossing edges between tree vertices and non-tree vertices.
Maintain on queue just one edge for each non-tree vertex w: the shortest edge that connects it to the tree.

Question 10

What is the time and space complexity of Prim’s eager algorithm?

Answer 10

Space: V
Time: E log V

Question 11

What are the edgeTo[] and distTo[] in the eager implementation?

Answer 11

Replaces marked[] and mst[]
- If v not on tree but one edge connecting to tree, then edgeTo[v] is shortest edge connecting v to tree and distTo[v] is weight.
- All vertices are maintained on index PQ, as index v = weight of edgeTo[v].

Minimum key on PQ = weight of minimal-weight crossing edge, and its associated vertex v is next to add.

Question 12

How does Prim’s eager algorithm maintain data structures?

Answer 12

• Take edge v from PQ
• Check if v-w is on Adjacencyt-list DS
• If w marked, ineligible
• If not on PQ or weight < current best known edgeTo[w], update v-w as best known way.