含圈有向图中简单路数的计算
共有1个答案
这个问题没有有效的算法。
从顶点s到t的简单路径数的计数问题是#p-完备的。因此，您不能期望一个多项式时间算法将在一般情况下工作。例如见https://cstheory.stackexchange.com/q/20246/5038、https://stackoverflow.com/a/5570751/781723、https://cs.stackexchange.com/q/423/755。
是时候尝试找到某种方法来避免解决这个问题，或者用近似算法或其他东西来凑合了。
-
我有一个有圈的有向图。所有边都是加权的，权重可以是负值。可能会有负循环。
-
我正在寻找一种算法，它可以<编码>不同两个有向无环图（DAG）。也就是说，我想要一个算法，它在第一个DAG上产生删除和插入序列，以产生第二个DAG。 我不是百分之百确定，但我认为一个最长的公共子序列可以应用于DAG。我不太关心结果编辑序列的长度（只要它足够短），更关心算法的运行时间。 一个复杂的问题是，除了一个根节点之外，没有一个顶点被标记。根节点也是唯一一个内边为零的节点。图的边被标记，图中的“
-
自定义地图上两点，绘制出两点直接的路径。使用MKPolyline绘制路径，支持长按（long press）地图自定义两点坐标。 作者说：参照http://code.google.com/p/ashiphone/downloads/detail?name=MapWithRoutes.zip
-
假设图G是一个有向无圈图，其顶点数为'n'no。如果我从图中移除所有边并使其完全断开，这会是一个DAG吗？
-
在一个已执行DFS的无向图中（为了生成一个DFS树，从而将每条边分类为树边或后边），图中是否存在仅由后边组成的循环，即没有树边？
-
请告诉我为什么这段代码不能分析无向图中是否有循环？代码如下。这是Spoj上的PT07Y问题。我正在做的是取一个节点并执行dfs。当执行dfs时，如果我访问同一个节点，那么我说有一个循环。从一个节点执行dfs后，我使访问的数组为假，并为下一个节点执行，直到我得到一个周期或所有节点都被访问。