贪心算法和最小生成树

又可称偏心算法：先将要求高的满足，再满足要求低的。

图论回顾

Digragh(有向图，Direct Gragh)
Undirected Gragh : G = (V, E), the edge set E consists of unordered pairs of vertices.
In either case, we have |E| = O(V^2). Moreover, if G is connected(连通图), then |E| ≥ |V| – 1, which implies that lg |E| = Θ(lgV).

Adjacency-matrix representation（邻接矩阵表示法）

The adjacency matrix of a graph G = (V, E), where V = {1, 2, …, n}, is the matrix A[1 . . n, 1 . . n] given by：


该表示方法需要的存储空间为：

Adjacency-list representation（邻接表表示法）

An adjacency list of a vertex v ∈ V is the list Adj[v] of vertices adjacent to v.

For undirected graphs, |Adj[v]| = degree(v).
For digraphs, |Adj[v]| = out-degree(v).
Handshaking Lemma:
for undirected graphs ⇒ adjacency lists use Θ(V + E) storage — a sparse representation (for either type of graph).

Minimum Spanning Trees（最小生成树）

Input: A connected, undirected graph G = (V, E) with weight function w : E → R.

• For simplicity, assume that all edge weights are distinct. (CLRS covers the general case.)

Output: A spanning tree T — a tree that connects all vertices — of minimum weight:


An Example of MST**

Optimal substructure（最优子结构）

Remove any edge Remove any edge (u, v) ∈ T. Then, . T is partitioned into two subtrees T1 and T2.
Theotem：
The subtree T1 is an MST of G1 = (V1, E1), the subgraph of G induced by the vertices of T1:
V1 = vertices of T1,
E1 = { (x, y) ∈ E : x, y ∈ V1 }
Similarly for T2.
Proof：
Cut and paste: If T1′ were a lower-weight spanning tree than T1 for G1,

then T′ = {(u, v)} ∪ T1′ ∪ T2 would be a lower-weight spanning tree than T for G. Wrong

overlapping subproblems

hava overlapping subproblems too.
dynamic programming may work
but MST exhibits another powerful property which leads to an even more efficient algorithm.

Hallmark for “greedy” algorithms

Greedy-choice property A locally optimal choice is globally optimal.
局部最优解即为全局最优解
Theorem.
Let T be the MST of G = (V, E), and let A ⊆ V. Suppose that (u, v) ∈ E is the least-weight edge connecting A to V – A. Then, (u, v) ∈ T.
Proof：

Consider the unique simple path from u to v in T. Swap (u, v) with the first edge on this path that connects a vertex in A to a vertex in V – A.

Prim’s algorithm

IDEA: Maintain V – A as a priority queue Q. Key each vertex in Q with the weight of the leastweight edge connecting it to a vertex in A.

Q<-V(all)
key[v] <- 无穷 for all v ∈ V
key[s] <- 0 for some arbitrary s ∈ V
while Q!=null
    do u <- EXTRACT-MIN(Q)
  for each v∈Adj[u]
      do if v∈Q and w(u, v) < key[v]
            then key[v] ← w(u, v)
            π[v] ← u
At the end, {(v, π[v])} forms the MST

Analysis: