Skip to content

[pull] main from itcharge:main #195

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 2 commits into from
May 28, 2025
Merged
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Original file line number Diff line number Diff line change
Expand Up @@ -2,7 +2,7 @@

在了解「最小生成树」之前,我们需要要先理解 「生成树」的概念。

> **图的生成树(Spanning Tree)**:如果无向连通图 G 的一个子图是一棵包含图 G 所有顶点的树,则称该子图为 G 的生成树。生成树是连通图的包含图中的所有顶点的极小连通子图。图的生成树不惟一。从不同的顶点出发进行遍历,可以得到不同的生成树。
> **生成树(Spanning Tree)**:如果无向连通图 G 的一个子图是一棵包含图 G 所有顶点的树,则称该子图为 G 的生成树。生成树是连通图的包含图中的所有顶点的极小连通子图。图的生成树不惟一。从不同的顶点出发进行遍历,可以得到不同的生成树。

换句话说,生成树是原图 G 的一个子图,它包含了原图 G 的所有顶点,并且通过选择图中一部分边连接这些顶点,使得子图中没有环。

Expand Down Expand Up @@ -51,12 +51,73 @@
### 2.3 Prim 算法的实现代码

```python

class Solution:
# graph 为图的邻接矩阵,start 为起始顶点
def Prim(self, graph, start):
size = len(graph)
vis = set()
dist = [float('inf') for _ in range(size)]

ans = 0 # 最小生成树的边权和
dist[start] = 0 # 初始化起始顶点到起始顶点的边权值为 0

for i in range(1, size): # 初始化起始顶点到其他顶点的边权值
dist[i] = graph[start][i]
vis.add(start) # 将 start 顶点标记为已访问

for _ in range(size - 1):
min_dis = float('inf')
min_dis_pos = -1
for i in range(size):
if i not in vis and dist[i] < min_dis:
min_dis = dist[i]
min_dis_pos = i
if min_dis_pos == -1: # 没有顶点可以加入 MST,图 G 不连通
return -1
ans += min_dis # 将顶点加入 MST,并将边权值加入到答案中
vis.add(min_dis_pos)
for i in range(size):
if i not in vis and dist[i] > graph[min_dis_pos][i]:
dist[i] = graph[min_dis_pos][i]
return ans

points = [[0,0]]
graph = dict()
size = len(points)
for i in range(size):
x1, y1 = points[i]
for j in range(size):
x2, y2 = points[j]
dist = abs(x2 - x1) + abs(y2 - y1)
if i not in graph:
graph[i] = dict()
if j not in graph:
graph[j] = dict()
graph[i][j] = dist
graph[j][i] = dist


print(Solution().Prim(graph))
```

### 2.3 Prim 算法
### 2.4 Prim 算法复杂度分析

Prim 算法的时间复杂度主要取决于以下几个因素:

1. **初始化阶段**:
- 初始化距离数组和访问数组的时间复杂度为 $O(V)$,其中 $V$ 是图中的顶点数。

## 03. Kruskal 算法
2. **主循环阶段**:
- 外层循环需要执行 $V-1$ 次,用于选择 $V-1$ 条边。
- 每次循环中需要:
- 找到未访问顶点中距离最小的顶点,时间复杂度为 $O(V)$。
- 更新相邻顶点的距离,时间复杂度为 $O(V)$。

因此,Prim 算法的总体复杂度为:
- 时间复杂度:$O(V^2)$,其中 $V$ 是图中的顶点数。
- 空间复杂度:$O(V)$,主要用于存储距离数组和访问数组。

## 3. Kruskal 算法

### 3.1 Kruskal 算法的算法思想

Expand All @@ -70,12 +131,81 @@
2. 将每个顶点看做是一个单独集合,即初始时每个顶点自成一个集合。
3. 按照排好序的边顺序,按照权重从小到大,依次遍历每一条边。
4. 对于每条边,检查其连接的两个顶点所属的集合:
1. 如果两个顶点属于同一个集合,则跳过这条边,以免形成环路。
2. 如果两个顶点不属于同一个集合,则将这条边加入到最小生成树中,同时合并这两个顶点所属的集合。
1. 如果两个顶点属于同一个集合,则跳过这条边,以免形成环路。
2. 如果两个顶点不属于同一个集合,则将这条边加入到最小生成树中,同时合并这两个顶点所属的集合。
5. 重复第 $3 \sim 4$ 步,直到最小生成树中的变数等于所有节点数减 $1$ 为止。

### 3.3 Kruskal 算法的实现代码

```python
class UnionFind:

def __init__(self, n):
self.parent = [i for i in range(n)]
self.count = n

def find(self, x):
while x != self.parent[x]:
self.parent[x] = self.parent[self.parent[x]]
x = self.parent[x]
return x

def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return

self.parent[root_x] = root_y
self.count -= 1

def is_connected(self, x, y):
return self.find(x) == self.find(y)


class Solution:
def Kruskal(self, edges, size):
union_find = UnionFind(size)

edges.sort(key=lambda x: x[2])

res, cnt = 0, 1
for x, y, dist in edges:
if union_find.is_connected(x, y):
continue
ans += dist
cnt += 1
union_find.union(x, y)
if cnt == size - 1:
return ans
return ans

def minCostConnectPoints(self, points: List[List[int]]) -> int:
size = len(points)
edges = []
for i in range(size):
xi, yi = points[i]
for j in range(i + 1, size):
xj, yj = points[j]
dist = abs(xi - xj) + abs(yi - yj)
edges.append([i, j, dist])

ans = Solution().Kruskal(edges, size)
return ans
```

### 3.4 Kruskal 算法复杂度分析

Kruskal 算法的时间复杂度主要取决于以下几个因素:

1. **边的排序**:对 $E$ 条边进行排序的时间复杂度为 $O(E \log E)$。

2. **并查集操作**:
- 查找操作(find)的时间复杂度为 $O(\alpha(n))$,其中 $\alpha(n)$ 是阿克曼函数的反函数,增长极其缓慢,可以近似认为是常数时间。
- 合并操作(union)的时间复杂度也是 $O(\alpha(n))$。

3. **遍历边的过程**:需要遍历所有边,时间复杂度为 $O(E)$。

```
因此,Kruskal 算法的总体时间复杂度为:
- 时间复杂度:$O(E \log E)$,其中 $E$ 是图中的边数。
- 空间复杂度:$O(V)$,其中 $V$ 是图中的顶点数,主要用于存储并查集数据结构。