检查有向图是否强连通的算法
我需要检查一个有向图是否强连通，也就是说，任何一个节点都可以通过其他节点到达（不一定是通过直接边缘）。 一种方法是在每个节点上运行DFS和BFS，并查看所有其他节点是否仍然可达。 是否有更好的方法来做到这一点？
Tarjan算法在Python中寻找强连通分量无法正常运行
我实现了Tarjan强连通分量算法，根据维基百科的伪代码，用Python编写，但是它没有工作。该算法非常简短，我找不到任何区别，因此无法确定为什么它不起作用。我试图检查原始论文，但未能找到。 以下是代码： def strongConnect(v): global E, idx, CCs...
如果存在循环，拓扑排序的算法
一些编程语言（如haskell）允许模块之间存在循环依赖。由于编译器需要在编译一个模块时知道所有导入的模块的定义，如果某些模块相互导入或出现任何其他类型的循环，则通常需要进行一些额外的工作。在这种情况下，编译器可能无法像没有导入循环的模块那样优化代码，因为导入的函数可能尚未被分析。通常只需编译...
免费的C++库用于绘制流程图或有向图？
我希望在我的程序中嵌入一个流程图画布。 用户可以绘制“节点”（矩形节点就足够了）和“边缘”（最好是直角边）以连接“节点”； 使用鼠标拖动节点以进行布局并调整矩形大小； 通过鼠标选择一个或多个节点以删除、复制、粘贴等操作； 通过鼠标选择一个或多个节点以编辑它们的预定义属性（体积、温度、压力等...
如何移除无权有向图中的回路，以便使边数最大化？
假设G是一个包含环的无权有向图。我正在寻找一种算法，它可以找到/创建所有无环图G'，由G中的所有顶点和G的子集组成，使G'足够小以使其成为无环图。 更正式地说：所需算法使用G并创建一组无环图S，其中每个图G'都满足以下属性： G'包含G的所有顶点。 G'包含G的边缘子集，使得G'是无环图...
什么是判断有向图是否单连通的最有效方法？
我正在完成一项任务，其中一个问题要求推导出一种算法来检查有向图G=(V,E)是否为单连通（对于所有不同的顶点u,v，从u到v最多只有一条简单路径）。 当然，您可以采用暴力方式进行检查，这也是我目前正在做的事情，但我想知道是否有更有效的方法。有谁能指点我一下吗？
有向概率图 - 降低循环的算法？
考虑一个有向图，从第一个节点1遍历到一些没有出边的最终节点。图中每条边都有一个与之关联的概率。将沿着所有可能的路径朝着所有可能的最终节点行进时的概率相加，结果为1。（这意味着我们最终肯定能到达其中一个最终节点。） 如果图中不存在循环，那么问题就很简单了。不幸的是，图中可能会出现非常复杂的循环...
在有向图的广度优先搜索中进行边分类
我在进行有向图的广度优先搜索时，遇到了正确分类边的困难。 在进行广度优先或深度优先搜索期间，您可以将遇到的边分为4类： TREE（树边） BACK（返祖边） CROSS（横叉边） FORWARD（前向边） Skiena [1] 给出了实现方法。如果您沿着从v1到v2的边移动，在Java中有...
如何在有向无环图中找到一组给定节点之间的所有路径？
我有一个项目列表（如下图中的蓝色节点），由我的应用程序用户分类。这些类别本身可以进行分组和分类。 生成的结构可以表示为有向无环图（DAG），其中项目是图拓扑结构底部的汇点，而顶层类别是源头。请注意，尽管其中一些类别可能定义得很好，但很多都是用户定义的，可能非常混乱。 示例： （来源：t...
最佳的存储/访问有向图的方法
我有大约3500个防洪设施，我想将它们表示为一个网络以确定流动路径（本质上是一个有向图）。我目前正在使用SqlServer和一个CTE来递归地检查所有节点及其上游组件，这在上游路径不分叉的情况下可以正常工作。然而，一些查询比其他查询需要的时间要指数级增加，即使它们在物理上沿路径向下只有两到三个...