minimum-spanning-tree

    4热度

    1回答

    使用Kruskal算法寻找图中的最小切点？

    我们已经看到，生成树和切割是密切相关的。这是另一个连接。让我们删除克鲁斯卡尔算法添加到生成树的最后一条边;这将树分成两个部分，从而在图中定义一个切割（S，S）。我们可以说这个削减？假设我们正在使用的图是未加权的，并且它的边是随机排列的，以便Kruskal算法处理它们。这是一个值得注意的事实：在概率至少为1/n^2的情况下，（S，S）是图中的最小切割，其中切割的大小（S，S）是S和S之间的边的数量。
    algorithm math minimum-spanning-tree minimum-cut kruskals-algorithm 2012-07-06

    1热度

    4回答

    使用最小生成树查找从A到B的路径 - C/C++

    假设我们找到最小生成树。现在，我们只需要在MST中从A到Z的路径。我们如何在O（n^2）时间内做到这一点？ 我们从根A开始，然后我们查看Ax形式的树（其中x是任何顶点）中的所有边。 然后，说我们找到：AB，AC，AD等...... 然后对于每一个，我们寻找形式的边：Bx，Cx，Dx ...这显然不是O（n^2 ）。 那么什么是更好/有效的方式来找到路径A - > Z给定MST？ 由于
    c++ algorithm tree graph-algorithm minimum-spanning-tree 2012-07-09

    0热度

    2回答

    Prim和Kruskal的算法复杂度

    给定一个带有权重的无向连通图。 w：E - > {1,2,3,4,5,6,7} - 意思是只有7个砝码可能。 我需要使用O（n + m）中的Prim算法和O（m * a（m，n））中的Kruskal算法找到生成树。 我不知道如何做到这一点，真的需要一些关于如何权重可以帮助我在这里的指导。
    algorithm minimum-spanning-tree prims-algorithm kruskals-algorithm 2012-05-28

    1热度

    2回答

    更改为图中非MST边缘以更改MST

    设计一个算法，该算法采用加权图G，并找到非MST边缘的成本中的最小变化，这将导致生成最小生成树的最小生成树G. 我的解决方案至今（需要建议）： 若要更改为MST，我们需要改变非MST边缘ST的重量它比MST中其起始顶点和结束顶点的路径中的最大边缘小1。因此，我们可以先步行MST的边缘，并为每个顶点检查是否存在非MST边缘。如果有，可以完成一个bfs到达边缘的终点（在MST中）。非MST边权重必须更
    algorithm graph minimum-spanning-tree 2012-05-28

    2热度

    3回答

    找到一个最小瓶颈生成树

    嗨，我正在做一些测试准备，我需要找出部分B和C.我知道a部分是真的，我可以证明这一点，但找到部分b和c的算法目前正在逃避我。 为最小瓶颈树求解以下问题，其中成本最大的边被称为瓶颈。 （a）G的最小生成树的每个最小瓶颈是哪个最小生成树G？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？证明你的主张。 （b）对于给定的代价c，给出一个O（n + m）时间算
    algorithm tree graph-theory minimum-spanning-tree 2012-10-29

    7热度

    1回答

    查找所选顶点的最小生成树的算法

    可以使用Prim算法或Kruskal算法来查找顶点/节点和边/链接集合的最小生成树/图。我想要的是找到这个集合的最小生成图的算法，但是生成的图只需要包含任意选择的节点，而不是所有的节点。如果结果图包含的节点数多于所需数量，那么这样做没问题。 这样的算法是否存在？也许可以在修改图形后仅使用Prim（或Kruskal's）算法来仅包含所需的节点？但是，我不确定如何在保持连通性的同时修改图形。 例如，假
    algorithm graph minimum-spanning-tree 2012-10-30

    1热度

    1回答

    以邻接矩阵为参数的Prim MST

    我正在C中使用Prim MST，并且该功能需要一个邻接矩阵。鉴于当然在A[i][j]的重量。 假设我有一个前驱数组，跟踪我迄今为止发现的最小边。 predecessor[u]=v {这也是最终MST} 现在我想修改当前A[i][j]矩阵和更改为1 的权重即当边缘（索引）的前身阵列中也存在。 否则我将其更改为零。 我该怎么做？这是我的解决方案： for (x....) for (y...)
    c algorithm minimum-spanning-tree prims-algorithm 2012-07-24

    0热度

    3回答

    如何以快速方式查找边缘序列中的所有路径？

    设E是给定的有向边集。假设已知E中的边可以形成有向树T，其中所有节点（根节点除外）只有1个入度。问题是如何有效地遍历边集E，以找到T中的所有路径？例如，给定有向边集E = {（1,2），（1,5），（5,6），（1,4），（2,3）}。我们知道这样一个集合E可以生成一个只有1个入度的有向树T（除了根节点）。有没有遍历边集E，为了找到所有的路径如下任何快速的方法： Path1 = {(1,2),(2
    algorithm graph graph-algorithm minimum-spanning-tree 2012-06-16

    1热度

    1回答

    请详细说明优先级队列中的减少密钥和提取最小值操作之间的关系

    EXTRACT-MIN操作和DECREASE-KEY优先级队列中的操作之间的关系是什么？我在使用Prim算法的最小生成问题讲座中遇到了这个问题。 麻省理工学院教授refers to it at point 01:07:16 seconds in the video但我没有得到它。有人可以帮我解决这个问题吗？ P.S：对于我对优先队列的理解，我感觉很舒服。
    algorithm data-structures priority-queue minimum-spanning-tree prims-algorithm 2012-09-27

    0热度

    1回答

    在最小生成树的Prims算法中π[v]←u是什么意思？

    在这MIT video regarding Prims algorithm for minimum spanniing tree教授在时间71:16秒解释π[v] ←u。但我不明白为什么我们需要这一步。 π[v] ←u是什么意思？算法中最后一行的含义是什么？ 在源给出的整个算法如下： Q←V key[v] ←∞for all v∈V key[s] ←0for some arbitrary s∈
    algorithm data-structures graph-algorithm minimum-spanning-tree 2012-10-01
最新问题