穿着西裤做的网站,wordpress 如何重启,如何看网站做没做推广,做网站一年了 做个小总结生成树
生成树#xff08;Spanning Tree#xff09;是一个连通图的生成树是图的极小连通子图#xff0c;它包含图中的所有顶点#xff0c;并且只含尽可能少的边。这意味着对于生成树来说#xff0c;若砍去它的一条边#xff0c;则会使生成树变成非连通图#xff1b;若给…生成树
生成树Spanning Tree是一个连通图的生成树是图的极小连通子图它包含图中的所有顶点并且只含尽可能少的边。这意味着对于生成树来说若砍去它的一条边则会使生成树变成非连通图若给它增加一条边则会形成图中的一条回路。
最小生成树
最小生成树Minimum Spanning Tree简称 MST是一个图的生成树中边的权重之和最小的那棵生成树。 对于一个带权连通无向图GVE生成树不同每棵树的权即树中所有边上的权值之和也可能不同。设X为G的所有生成树的集合若T为X中边的权值之和最小的那棵生成树则T称为G的最小生成树Minimum-Spanning-Tree(MST),在一个加权连通图中可能存在多个不同的生成树但是其中只有一个最小生成树。最小生成树通常用于解决网络设计、通信网络等问题。
不难看出最小生成树具有如下性质: 1最小生成树不是唯一的即最小生成树的树形不唯一X中可能有多个最小生成树。当图G中的各边权值互不相等时G的最小生成树是唯一的若无向连通图G的边数比顶点数少1即G本身是一棵树时则G的最小生成树就是它本身。 2最小生成树的边的权值之和总是唯一的虽然最小生成树不唯一但其对应的边的权值之和总是唯一的而且是最小的。 3最小生成树的边数为顶点数减1
构造最小生成树有多种算法但大多数算法都利用了最小生成树的下列性质假设GVE)是一个带权连通无向图U是顶点集V的一个非空子集。若(u,v)是一条具有最小叔值的边其中u∈U v∈V- U则必存在一棵包含边(u,V)的最小生成树基于该性质的最小生成树算法主要有Prim算法和Kruskal算法它们都基于贪心算法的策略。
常用的最小生成树算法
Prim算法Prim算法是一种贪心算法从一个顶点开始每次选择权重最小的边来扩展最小生成树直到所有顶点都加入到最小生成树中为止。
Kruskal算法Kruskal算法是一种基于并查集的贪心算法它首先将所有边按权重从小到大排序然后依次考虑每条边如果当前边连接的两个顶点不在同一个连通分量中则将这条边加入最小生成树中并将这两个顶点合并到同一个连通分量中直到最小生成树的边数达到n-1为止。
最小生成树算法的选择 如果图的边数量比较少那么Kruskal算法通常更加简洁高效。 如果图的顶点数量比较少那么Prim算法可能更容易实现和理解。 如果图是稠密图边数量接近于完全图那么Prim算法的时间复杂度可能更低因为Prim算法在每一步都只需要考虑与当前最小生成树相邻的边。
from heapq import heappop, heappush# Prim算法
def prim(graph):n len(graph)visited [False] * nmin_heap [(0, 0)] # (权重, 顶点)mst_weight 0while min_heap:weight, node heappop(min_heap)if visited[node]:continuevisited[node] Truemst_weight weightfor neighbor, weight in graph[node]:if not visited[neighbor]:heappush(min_heap, (weight, neighbor))return mst_weight# Kruskal算法
def kruskal(graph):n len(graph)parent list(range(n))edges []mst_weight 0for u in range(n):for v, weight in graph[u]:edges.append((weight, u, v))edges.sort()for weight, u, v in edges:if find(u, parent) ! find(v, parent):union(u, v, parent)mst_weight weightreturn mst_weightdef find(x, parent):if parent[x] ! x:parent[x] find(parent[x], parent)return parent[x]def union(x, y, parent):root_x find(x, parent)root_y find(y, parent)parent[root_x] root_y# 测试
graph [[(1, 1), (2, 2)],[(0, 1), (2, 4), (3, 5)],[(0, 2), (1, 4), (3, 3)],[(1, 5), (2, 3)]
]print(Prim算法最小生成树权重, prim(graph))
print(Kruskal算法最小生成树权重, kruskal(graph))
参考链接:https://zhuanlan.zhihu.com/p/136387766
