什么是生成樹(shù)？
連通無(wú)向圖中的所有頂點(diǎn)且任意兩個(gè)頂點(diǎn)間只有一條通路的子圖。生成樹(shù)中邊的數(shù)量 = 頂點(diǎn)數(shù) - 1。如下圖均為生成樹(shù)。
生成樹(shù)
什么是最小生成樹(shù)?
最小生成樹(shù)是指所有生成樹(shù)中邊的權(quán)重和最小的生成樹(shù)。
最小生成樹(shù)算法
最小生成樹(shù)算法主要有兩個(gè)：kruskal（克魯斯卡爾）算法和prim（普里姆）算法。下面就分別介紹下這兩類(lèi)算法。
1. kruskal 算法
其主要步驟如下：
- 首先獲取所有的邊，對(duì)這些邊進(jìn)行從小到大的排序
- 然后不斷往圖里添加邊，并且避免造成環(huán)
- 直到所有點(diǎn)都能互相訪問(wèn)后停止算法
偽代碼如下：
function kruskal(graph) {
// 對(duì)圖里的邊進(jìn)行排序
const sortedEdges = graph.edges.sort()
// 去掉圖里的邊
graph.removeAllEdges()
for (let i = 0; i < sortedEdges.length; i++) {
// 如果添加的邊未造成環(huán)，那么就進(jìn)行添加
if (!graph.hasCycle()) {
graph.addEdge(sortedEdges[i])
}
}
return graph
}
算法要點(diǎn)在于怎么判斷是否存在環(huán)。
在此之前，先說(shuō)明三個(gè)定義：
- 無(wú)向圖 G 的一個(gè)極大連通子圖稱(chēng)為 G 的一個(gè)連通分量（或連通分支）。連通圖只有一個(gè)連通分量，即其自身；非連通的無(wú)向圖有多個(gè)連通分量。連通分量與連通分量之間沒(méi)有任何邊相連。
- 在無(wú)向圖中，如果從頂點(diǎn)
到頂點(diǎn)
有路徑，則稱(chēng)
- 在有向圖中，如果對(duì)于每一對(duì)頂點(diǎn)
kruskal 就可以這樣理解：初始時(shí)，把圖中的個(gè)頂點(diǎn)看成是獨(dú)立的
個(gè)連通分量，從樹(shù)的角度看，也是
個(gè)根節(jié)點(diǎn)。選邊的標(biāo)準(zhǔn)是這樣的：若邊上的兩個(gè)頂點(diǎn)從屬于兩個(gè)不同的連通分量，則此邊可取，否則考察下一條權(quán)值最小的邊。
那么如何判斷兩個(gè)頂點(diǎn)是否屬于同一個(gè)連通分量呢？這個(gè)可以參照并查集的做法解決。它的思路是：如果兩個(gè)頂點(diǎn)的根節(jié)點(diǎn)是一樣的，則屬于同一個(gè)連通分量。這也同樣暗示著：在加入新邊時(shí)，要更新父節(jié)點(diǎn)。
先定義邊的數(shù)據(jù)結(jié)構(gòu)：
class Edge(object):
def __init__(self, start, end, weight):
"""
定義邊，頂點(diǎn)采用 0至頂點(diǎn)個(gè)數(shù)-1編號(hào)
:param start: 頂點(diǎn)start
:param end: 頂點(diǎn)end
:param weight: 頂點(diǎn)start 和頂點(diǎn)end 之間邊的權(quán)重
"""
self.start = start
self.end = end
self.weight = weight
下面是 Kruskal 算法實(shí)現(xiàn)：
class Kruskal(object):
def __init__(self, edges, node_count=0):
"""
Kruskal 算法
:param edges: list:[Edge]
"""
self.edges = edges
self.root = list(range(node_count))
self.path_length = 0
def is_same_root(self, i, j):
"""
判斷 i 和 j 的根節(jié)點(diǎn)是否相同
:param i:
:param j:
:return: bool
"""
while self.root[i] != i:
i = self.root[i]
while self.root[j] != j:
j = self.root[j]
return i == j
def update_root(self, i, j):
"""
將 j 的根節(jié)點(diǎn)更新為 i 的根節(jié)點(diǎn)
"""
if i > j:
i, j = j, i
while self.root[i] != i:
i = self.root[i]
self.root[j] = i
def kruskal(self):
# 先排序
edges = sorted(self.edges, key=lambda edge: edge.weight)
for edge in edges:
i = edge.start
j = edge.end
if not self.is_same_root(i, j):
print("%d 和 %d 是相連的" % (i, j))
self.update_root(i, j)
self.path_length += edge.weight
return self.path_length
其中判斷是否是相同根節(jié)點(diǎn)也可以利用查并集的方式：
def find(self, i):
if self.root[i] != i:
self.root[i] = self.find(self.root[i])
return self.root[i]
最后 Kruskal 算法可寫(xiě)為
def kruskal(self):
edges = sorted(self.edges, key=lambda edge: edge.weight)
for edge in edges:
i = edge.start
j = edge.end
w = edge.weight
root_i, root_j = self.find(i), self.find(j)
if root_i != root_j:
print("%d 和 %d 是相連的" % (i, j))
self.root[root_j] = root_i
self.path_length += w
return self.path_length
2. prim 算法
其主要步驟如下：
- 從一個(gè)節(jié)點(diǎn)（隨機(jī)選一個(gè)）開(kāi)始，去找與這個(gè)節(jié)點(diǎn)相鄰最短的邊
- 將找到的邊添加到這個(gè)節(jié)點(diǎn)上，形成一個(gè)組件
- 再?gòu)倪@個(gè)組件開(kāi)始去找相鄰權(quán)重最小的邊，再添加到這個(gè)組件上，不斷重復(fù)直到所有節(jié)點(diǎn)都能被訪問(wèn)
偽代碼如下
function prim(graph) {
const visited = []
// 從一個(gè)節(jié)點(diǎn)開(kāi)始
const sourceComponent = graph.randomVertex()
// 如果還有節(jié)點(diǎn)不能被訪問(wèn)就繼續(xù)找
while (visited.length < graph.vertices.length) {
// 將相鄰權(quán)重最小的邊作為組件的一部分，且不構(gòu)成環(huán)
const smallestEdge = sourceComponent.findSmallestEdge()
sourceComponent.addEdge(smallestEdge)
visited.push(smallestEdge.toVertex)
}
}
下面是 prim 算法實(shí)現(xiàn)：
class Prim(object):
def __init__(self, graph):
"""
:param graph: 鄰接表形式的圖，具體值表示邊的權(quán)重
"""
self.graph = graph
def prim(self, start=0):
length = len(self.graph)
distances = [float('inf')] * length
visited = [False] * length
visited[start] = True
index = start
path_length = 0
# 與 start 相連的點(diǎn) 進(jìn)行初始化
for i in range(length):
distances[i] = self.graph[start][i]
for i in range(length):
if i == start:
continue
minor = float('inf')
for j in range(length):
# 未訪問(wèn)的節(jié)點(diǎn)中 距離最近的節(jié)點(diǎn)
if not visited[j] and distances[j] < minor:
minor = distances[j]
index = j
visited[index] = True
# print(i, index, minor)
path_length += minor
# 更新最近的距離
for j in range(length):
if not visited[j] and distances[j] > self.graph[index][j]:
distances[j] = self.graph[index][j]
return path_length
其中尋找距離最近的節(jié)點(diǎn)也可以利用堆進(jìn)行優(yōu)化：
def prim(self, start=0):
length = len(self.graph)
distances = [float('inf')] * length
visited = [False] * length
path_length = 0
# 元素為 (距離, 下標(biāo))
heap = []
heapq.heappush(heap, (0, start))
while heap:
dist, index = heapq.heappop(heap)
if visited[index]:
continue
visited[index] = True
path_length += dist
# 將與index相連的節(jié)點(diǎn)加入
for j in range(length):
w = self.graph[index][j]
if not visited[j] and w < distances[j]:
distances[j] = w
heapq.heappush(heap, (w, j))
return path_length
3. leetcode 題目
3.1 1584. 連接所有點(diǎn)的最小費(fèi)用
給你一個(gè)points 數(shù)組，表示 2D 平面上的一些點(diǎn)，其中 points[i] = [xi, yi] 。
連接點(diǎn) [xi, yi] 和點(diǎn) [xj, yj] 的費(fèi)用為它們之間的 曼哈頓距離 ：|xi - xj| + |yi - yj| ，
其中 |val| 表示 val 的絕對(duì)值。 請(qǐng)你返回將所有點(diǎn)連接的最小總費(fèi)用。
只有任意兩點(diǎn)之間 有且僅有 一條簡(jiǎn)單路徑時(shí)，才認(rèn)為所有點(diǎn)都已連接。
示例 1：
輸入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
輸出：20
示例 2：
輸入：points = [[3,12],[-2,5],[-4,1]]
輸出：18
示例 3：
輸入：points = [[0,0],[1,1],[1,0],[-1,1]]
輸出：4
示例 4：
輸入：points = [[-1000000,-1000000],[1000000,1000000]]
輸出：4000000
示例 5：
輸入：points = [[0,0]]
輸出：0
提示：
1 <= points.length <= 1000
-106 <= xi, yi <= 106
所有點(diǎn) (xi, yi) 兩兩不同。
Related Topics 并查集
題目要求連接所有點(diǎn)，有且僅有一條路徑，即最終結(jié)果是生成樹(shù)。因?yàn)橐蟮氖亲钚〉目傎M(fèi)用，便是最小生成樹(shù)。我們可以采用前面總結(jié)的最小生成樹(shù)算法來(lái)實(shí)現(xiàn)。
首先定義曼哈頓距離的計(jì)算函數(shù)：
def manhattanDistance(points, index1, index2):
point1 = points[index1]
point2 = points[index2]
return abs(point1[0] - point2[0]) + abs(point1[1] - point2[1])
若采用 Kruskal 算法，我們需要將題目給定的一系列點(diǎn)轉(zhuǎn)換成類(lèi) Kruskal 初始化需要的格式，并進(jìn)行初始化，最后求的結(jié)果：
if __name__ == '__main__':
points = [[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]]
n = len(points)
edges = []
for i in range(n):
for j in range(i+1, n):
edges.append(Edge(i, j, manhattanDistance(points, i, j)))
s = Kruskal(edges, node_count=n)
print(s.kruskal())
若采用 Prim 算法，則需要將題目給定的一系列點(diǎn)轉(zhuǎn)換成鄰接表的形式，最終求的結(jié)果：
if __name__ == '__main__':
points = [[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]]
n = len(points)
graph = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(i+1, n):
weight = manhattanDistance(points, i, j)
graph[i][j] = weight
graph[j][i] = weight
s = Prim(graph)
print(s.prim(0))
