Graphs(review) CLRS, App B
Digraph(Directed graph) G = (V, E)
·Set V of vertices(singular vertex)
·Set E ⊆ V * V of edges
Undirected graph: E contains unordered pairs.
|E| = O(V^2). G connected => |E| > |V| - 1
log|E| = Θ(log V)
Graph representations
Adjacency matrix of G = (V, E), where V = {1, 2, 3, ..., n}, is the n * n matrix A given by A[i, j] = {1 if (i, j) ∈E
{0 if (i, j) ∉ E
Θ(V^2) storage => dense representation
Adjacency list of V∈ A is the list Adj[V] of vertices adjacent to V.
Adj[1] = {2, 3}
Adj[2] = {3}
Adj[3] = {}
Adj[4] = {3}
|Adj[V]|
= {degree(v) (undirected graph)
{outdegree (directed graph)
Handshaking Lemma (undirected graph)
Σdegree(v) = 2|E| [v ∈ V]
for undirected grqaphs => adj-list representation uses Θ(E + V) storage same thing asymptotically for digraphs.
sparse representation: often better than adj matrix.b
Minimum spanning trees
Input: Connected, undirected graph G = (V, E) with weight function w: E -> R.
·for simplicity, assume all edges are distinct.
Output: A spanning tree T (connects all the vertices) of minimum weight.
w(T) = ∑w(u, v) [(u, v) ∈ T]
Ex.
Optimal substructure
MST T:
(other edges not shown)
remove (u, v)∈ T, then T is partitioned into two subtrees T1 and T2.
theorem: T1 is MST for G1 = (V1, E1), the subgraph of G induced by vertices in T1.
V1 = vertices in T1
E1 = {(x, y) ∈ E: x, y ∈ V1}
Proof. Cut & Paste
w(T) = w(u, v) + w(T1) + w(T2)
If T1‘ better than T1 for G1, then T‘ = {(u, v) } U T1‘ U T2, would be better than T for F.
Overlapping subproblems? YES
Dynamic programing? Yes, but MST exhibits an even more powerful proberty.
Hallmark for greedy algorithms
Greedy choice proberty: A locally optimal choice is globally optimal.
Theorem: Let T be MST of G = (V, E), let A ⊆ V, suppose (u, v)∈E is the least-weight edge connecting A to V-A. Then (u, v)∈T.
Consider unique simple path from u to v in T. Swap (u, v) with the first edge on this path that connects a vertex V in A to a vertex in V - A. A lower weight spanning tree than T results. Contradiction.
Prim‘s algorithm
Idea: Maintain V-A as a priority queue Q, Key each vertex in Q with weight of least-weight edge connecting it to a vertex in A.
1 Q ← V 2 key[v] ← ∞ for all v ∈ V 3 key[s] ← 0 for some arbitrary s ∈ V 4 while Q ≠ ∅ 5 do u ← EXTRACT-MIN(Q) 6 for each v ∈ Adj[u] 7 do if v ∈ Q and w(u, v) < key[v] 8 then key[v] ← w(u, v) ? DECREASE-KEY 9 π[v] ← u
At end, {(V, π[v])} forms MST.
Q TEXTRACT-MIN TDECREASE-KEY Total
array O(V) O(1) O(V2)
binary heap O(lg V) O(lg V) O(E lg V)
Fibonacci heap O(lg V) O(1) O(E + V lg V)
amortized amortized worst case
[Introduction to Algorithms - Lecture Notes] 16.Greedy Algorithms and Minimum Spanning Tree
原文：http://www.cnblogs.com/rafacheng/p/5008429.html