最小生成树

introduction

加权图：是一种为每条边关联一个权值或是成本的图模型

最小生成树：给定一幅加权无向图，找到它的一棵最小生成树

定义： 图的生成树是它的一棵含有其所有顶点的无环联通子图。一幅加权图的最小生成树（MST）是它的一棵权值（树中所有边的权值之和）最小的生成树。

Given. Undirected graph G with positive edge weights (connected).
Def. A spanning tree of G is a subgraph T that is both a tree (connected and acyclic) and spanning (includes all of the vertices).
Goal. Find a min weight spanning tree.

greedy algorithm

Greedy MST algorithm demo

Start with all edges colored gray.
Find cut with no black crossing edges; color its min-weight edge black.
Repeat until V - 1 edges are colored black.

edge-weighted graph API

Weighted edge API

Edge abstraction needed for weighted edges.

Weighted edge: Java implementation

Edge-weighted graph API

Edge-weighted graph: adjacency-lists representation

Maintain vertex-indexed array of Edge lists.

Edge-weighted graph: adjacency-lists implementation

Minimum spanning tree API

Q. How to represent the MST?

Kruskal’s algorithm

Kruskal’s algorithm demo

Consider edges in ascending order of weight.

Add next edge to tree T unless doing so would create a cycle.

Kruskal’s algorithm: Java implementation

Prim’s algorithm

Prim’s algorithm demo

Start with vertex 0 and greedily grow tree T.
Add to T the min weight edge with exactly one endpoint in T.
Repeat until V - 1 edges.