阜宁做网站的公司电话,ppt模板免费下载网站哪个好,手机网站改版了,网页制作软件山水什么是最小生成树(Minimum Spanning Tree) 每两个端点之间的边都有一个权重值#xff0c;最小生成树是这些边的一个子集。这些边可以将所有端点连到一起#xff0c;且总的权重最小 下图所示的例子#xff0c;最小生成树是{cf, fa, ab} 3条边 Kruskal算法 用到上一篇中介绍的…什么是最小生成树(Minimum Spanning Tree) 每两个端点之间的边都有一个权重值最小生成树是这些边的一个子集。这些边可以将所有端点连到一起且总的权重最小 下图所示的例子最小生成树是{cf, fa, ab} 3条边 Kruskal算法 用到上一篇中介绍的不相交集合(并查集) 首先定义V是端点的集合E是边的集合A为要求的最小生成树集合 初始A为空集合每个端点都作为单独的不相交集合将所有边根据其权重进行排序对每条边(v1, v2)如果其两个端点数据不同的不相交集则将该边加到集合A中同时将v1和v2合并最终得到的A即为最小生成树 生成过程的示例图 C代码示例 struct Edge {char vertex1;char vertex2;int weight;Edge(char v1, char v2, int w):vertex1(v1), vertex2(v2), weight(w) {}
};struct Graph {vectorchar vertice;vectorEdge edges;
};unordered_mapchar, char PARENT;
unordered_mapchar, int RANK;char find(char vertex) {if (PARENT[vertex] vertex) return PARENT[vertex];elsereturn find(PARENT[vertex]);
}void MST(Graph g) {vectorEdge res;for (auto c : g.vertice) {PARENT[c] c;RANK[c] 0;}sort(g.edges.begin(), g.edges.end(), [](Edge x, Edge y) {return x.weight y.weight;}); // O(E*log(E))for (Edge e : g.edges) { // O(E)char root1 find(e.vertex1); // 最差O(E)因为有记录深度Find可以认为很快char root2 find(e.vertex2);if (root1 ! root2) {res.push_back(e);if (RANK[root1] RANK[root2]) {PARENT[root2] root1;RANK[root1];} else {PARENT[root1] root2;RANK[root2];}}}for (Edge e : res) {cout e.vertex1 -- e.vertex2 e.weight endl;}
}void Union( char vertex_1, char vertex_2 ) {
}int main() {char t[] {a, b, c, d, e, f};Graph g;g.vertice vectorchar(t, t sizeof(t)/sizeof(t[0]));g.edges.push_back(Edge(a, b, 4)); // 稀疏图用链来表示(E O(V)) g.edges.push_back(Edge(a, f, 2)); // 如果是密集图(E O(V*V)), 用矩阵来表示g.edges.push_back(Edge(f, b, 5)); // 大部分感兴趣的图是稀疏的g.edges.push_back(Edge(c, b, 6));g.edges.push_back(Edge(c, f, 1));g.edges.push_back(Edge(f, e, 4));g.edges.push_back(Edge(d, e, 2));g.edges.push_back(Edge(d, c, 3));MST(g);return 0;
} 转载于:https://www.cnblogs.com/logchen/p/10274863.html
