计算无向图的最小生成树
考虑一个有n个顶点和m条边的无向图。假设边有两种类型:m1红色边和m2绿色边。因此m=m1+m2。红色边缘的权重为1，绿色边缘的权重为2。设计并分析了一种计算这种图的最小生成树的有效算法
共有1个答案
在无向图中任意选取一个节点开始。
为图中的每个节点创建一个带有键的哈希表。对于hastable中每个节点的值，将该值初始化为-1，但以其开头的节点除外，在该节点中，您将其初始化为-100。这些值将表示到达该节点的成本。“特殊数字”是-1和-100，前者表示到达该节点的成本当前未知，后者表示该节点已经在MST中。
现在，对于与您开始使用的节点相邻的每个节点，将哈希表中的节点更新为1或2（取决于它们之间的边是红色还是绿色）。
现在查看哈希表，并确定哪个节点具有不是-1或-100的最低值。如果有多个相同最低成本的，随便挑其中一个就可以了。将该节点添加到MST并将该节点的值设置为-100。
使用树中包含的新包含的节点更新哈希表。有可能一个节点最初的成本是2,但现在添加的节点的成本是1。在这种情况下，将这些节点的开销从2更新为1。
不断重复上述步骤，直到覆盖了所有节点。您现在有了最小生成树！
-
无向图最小生成树的Prim算法 思路说明 假设点A,B,C,D,E,F，两点之间有连线的，以及它们的距离分别是：(A-B:7);(A-D:5);(B-C:8);(B-D:9);(B-E:7);(C-E:5);(D-E:15);(D-F:6);(E-F:8);(E-G:9);(F-G:11) 关于Prim算法的计算过程，参与维基百科的词条：普里姆算法 将上述点与点关系以及两点之间距离（边长，有的文献
-
最小生成树的Kruskal算法 描述：有A、B、C、D四个点，每两个点之间的距离（无方向）是(第一个数字是两点之间距离，后面两个字母代表两个点）：(1,’A’,’B’),(5,’A’,’C’),(3,’A’,’D’),(4,’B’,’C’),(2,’B’,’D’),(1,’C’,’D’) 生成边长和最小的树，也就是找出一种连接方法，将各点连接起来，并且各点之间的距离和最小。 思路说明： Krusk
-
我有一个问题需要我在Boost图库中找到一个有向图的最小生成树。 我的第一个尝试是使用深度优先搜索和dfs-visitor。我的计划是忽略除树边回调之外的所有边。这不起作用，我给出了下面的例子来说明原因。 我的问题是我是否可以让我的dfs-visitor在BGL中创建一个有向图的最小生成树。 下面是失败的例子。如果我有以下有向图 在深度优先搜索dfs-visitor中，1->0被分类为前沿。 如果
-
我不确定如何处理这个问题。 给定一个无向图，每条边的颜色要么是红色，要么是蓝色。如何在时间复杂度（O（m+n）log n）中找到包含尽可能少的红边的最小生成树。其中m个顶点和n个边。 任何帮助都将不胜感激。
-
假设我选择V(H)={a,e,f}和e(H)={ae,af,fe} 现在，对于每条边e∈e(H)，我们用e'记下了（来自原始图G的） 达到这个最小值的边。所以E'={bc,df,eg},因为bc=4,df=9,eg=8,是连接我的元件的最小边。我在H中有一个相对于代价函数C′的最小生成树，而a′是这棵树的边集。 但是我的A'的边和E'的没有一条是一样的。
-
我需要一些关于Prim的算法问题的帮助： 设T是图G的一个由Prim算法得到的最小生成树。设Gnew是在G上增加一个新的顶点和一些带权的边，将新的顶点连接到G上的一些顶点而得到的图，我们能把其中一条新的边加到T上构造Gnew的最小生成树吗？如果你回答是，请解释是怎样做的；如果没有，请解释原因。 提前谢谢！！