指示无向图

2018-06-18 13:50:59

我有一个无向的完整图，并希望将其转换为每个节点之间具有（单向）路径的有向无环图。首先，我想添加随机边，并在所有节点连接后停止。看什么算法（使用Python，但任何语言都可以）。

因此，例如这张图，不会再有任何关联：

A  ---- B            A ---> B
      /      =>           /
     /                   v
    C                    C

，但在这种情况下，所有无向边都变成有向边

A  ---- B            A ---> B
      /      =>      ^     ^
     /                   /
    C                    C

更新

请注意，目标是根据上述约束将无向图转换为有向图。就像一棵生成树一样，这个转换过程有多个解决方案（如上例所示）。

你需要一个定向生成树。

很容易在无向图中找到有向生成树。只要进行深度优先搜索，忽略背面和交叉边缘。实际上遍历的边形成一个有向树，触及每个连接组件中的每个节点。

但是，您已经添加了您希望边选择为随机的限制。

因此，为此，您可以使用最小生成树算法，如具有随机边权重的Kruskal算法。

请注意，没有理由实际存储和计算随机边权重。该算法的第一步是按重量分类。因此，通过边缘的随机排列来替换这种排序，并且你在商业中。

链接地址: http://www.djcxy.com/p/52379.html