无向图：尽可能少红边的最小生成树
我不确定如何处理这个问题。
给定一个无向图，每条边的颜色要么是红色，要么是蓝色。如何在时间复杂度（O（m+n）log n）中找到包含尽可能少的红边的最小生成树。其中m个顶点和n个边。
任何帮助都将不胜感激。
共有1个答案
就我所见，我想你已经回答了你自己的问题。通过给边赋权，红权为1，蓝权为0，使问题成为经典的寻找最小生成树的问题，其时间复杂度为O((m+n)logn)。
-
我们有一个图G并且希望在每个顶点对之间添加边，这些边尽可能轻，而不影响最小生成树。给定最小生成树和一对顶点，在不影响MST的情况下，如何计算它们之间添加的最轻边的权重？ 我认为添加一条比两个顶点的每一条边缘都重的边缘会起作用，但在我所做的实验中，这似乎是错误的。
-
考虑一个有n个顶点和m条边的无向图。假设边有两种类型:m1红色边和m2绿色边。因此m=m1+m2。红色边缘的权重为1，绿色边缘的权重为2。设计并分析了一种计算这种图的最小生成树的有效算法
-
无向图最小生成树的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被分类为前沿。 如果
-
给定一个带正权的无向图，有2种边：锁定边和未锁定边。确定给定边沿是锁定边沿还是未锁定边沿需要O(1)。 > 对于给定的两个顶点s，t和一个正数k=O(1)，我如何找到s和t之间最多包含k条锁定边的最短路径？ 对于给定的两个顶点s，t和一个正数k=O(1),我如何找到s和t之间恰好包含k条锁定边的最短路径？ 我不知道如何在这个图上运行Dijkstra算法来找到给定顶点之间的最短路径，以及如何将无向图