考虑具有n个顶点和m个边的无向图。假设边缘有两种类型：m1个红色边缘和m2个绿色边缘。因此m = m1 + m2。红色边缘具有权重1，绿色边缘具有权重2.设计和分析有效算法以计算这种图形的最小生成树
任意选择无向图中的节点开始。
使用图中每个节点的键创建哈希表。对于hastable中每个节点的值，将值初始化为-1，除了您开始的节点，在该节点中将其初始化为-100。这些值将表示到达该节点的成本。 “特殊数字”为-1表示到达该节点的成本当前未知，-100表示该节点已在MST中。
现在，对于您开始使用的节点的每个相邻节点，将哈希表中的那些节点更新为1或2（取决于它们之间的边缘是红色还是绿色）。
现在查看哈希表并确定哪个节点的最低值不是-1或-100。如果有多个具有相同的最低成本，只需随机选择其中一个。将该节点添加到MST并将该节点的值设置为-100。
使用树中包含的新包含节点更新哈希表。有可能节点最初成本为2，但现在增加节点的成本为1。在这种情况下，将这些节点的成本从2更新为1。
继续重复上述步骤，直到涵盖所有节点。你现在有了最小生成树！