问题标签 [cyclic-graph]

我想使用树形布局在 JUNG 中可视化一个图形（不是树）。我知道这可能看起来有点奇怪，但事情如下。该应用程序由 Neo4J 数据库支持。它们中有一堆节点，所有节点都通过几种类型的关系连接起来。换句话说，我有一个循环图。

如果我想象性地删除除了关系类型为 *IS_PARENT* 的关系之外的所有关系，我剩下的就是一棵完美的树。所以我的数据中有一个树形结构，JUNG 看不到它，因为其他关系使它循环。

我想这样做有两个主要原因。

1. 可读性。我的数据中有一个逻辑结构，我非常想将其可视化。
2. 我有理由相信这会提高我的应用程序的性能。由于大量的顶点和边，目前性能很差。我还研究了另一个名为 Prefuse 的可视化工具，在那里我发现树布局更容易处理，至少 Prefuse 是这样，我希望 JUNG 也是如此。

所以这对我来说有很多好处。我希望这里有人可以帮助我，因为我找不到东西。

我有一个具有 N 个节点和 2N-3 条边的连接的无向图。您可以将图视为构建在现有初始图的基础上，该图具有 3 个节点和 3 条边。添加到图中的每个节点都与图中的现有节点有 2 个连接。当所有节点都添加到图中（总共添加 N-3 个节点）时，构建最终图。

最初我被问到，这个图中可以访问一次的最大节点数是多少（初始节点除外），即给定图的最大哈密顿路径中包含的最大节点数是多少？（好吧，说最大哈密顿路径不是一个有效的短语，但考虑到问题的性质，我需要找到一次访问的最大节点数，并且行程在初始节点处结束。我认为它可以被视为子图是哈密顿量，由最大数量的节点组成，因此是最大可能的哈密顿路径）。

由于没有要求我找到路径，因此我应该首先检查给定数量的节点是否存在哈密顿路径。我知道平面图和循环图s (C _n ) 是哈密顿图（我也知道哈密顿图的 Ore 定理，但我将要处理的图不会是一个很有可能的密集图，因此使 Ore 的定理很漂亮在我的情况下没用）。因此，我需要找到一种算法来检查该图是否为循环图，即是否存在一个包含给定图的所有节点的循环。

由于 DFS 用于检测周期，我认为对 DFS 进行一些小的操作可以帮助我检测我正在寻找的内容，例如跟踪探索的节点，最后检查最后访问的节点是否与初始节点有连接。不幸的是，我无法通过这种方法取得成功。

我尝试的另一种方法是排除一个节点，然后尝试从另一个相邻节点开始到达其相邻节点。根据所选的相邻节点，该算法可能无法给出正确的结果。

我几乎被困在这里。你能帮我想出另一种算法来告诉我该图是否是循环图吗？

编辑

我在评论的帮助下意识到（谢谢你）：

循环图由一个循环组成，有 N 个边和 N 个顶点。如果存在一个包含给定图的所有节点的循环，那就是哈密顿循环。-纳米

我实际上是在寻找一条哈密顿路径，我并不打算这样做:) 再想一想，我认为在构建图的同时检查图的哈密顿属性会更有效，这也是我正在寻找的: 时间效率。

经过一番思考，我认为无论节点数量是多少，由于节点添加标准，该图似乎是哈密顿量。问题是我无法确定，也无法证明。以这种方式添加节点，即添加具有 2 条边的新节点，将添加的节点连接到现有节点，是否会改变图的哈密顿属性？如果它不改变哈密顿性质，那又如何呢？如果它确实改变了，又是怎么回事？谢谢。

编辑#2

我再次意识到，按照我描述的方式构建图形可能会改变哈密顿量。考虑如下给出的输入：

这些输入表示第 4 个节点连接到节点 1 和节点 3，第 5 个节点连接到节点 2 和节点 3。. .

第 4 和第 7 个节点连接到相同的节点，从而将可以仅访问一次的最大节点数降低 1。如果我检测到这些冲突（不包括诸如 3 3 之类的输入，这是您建议的示例由于问题表明新添加的边连接到其他 2 个节点）并降低最大节点数，从 N 开始，我相信我可以得到正确的结果。

看，我不选择连接，它们是给我的，我必须找到最大值。节点数。

我认为在构建图形时计算相同的连接数并从 N 中减去相同的连接数会得到正确的结果吗？你能证实这一点还是这个算法有缺陷？

输入是一个无向的循环平面图，每个顶点最多有 8 条边。

以从最短到最长的顺序枚举两个顶点 v_0、v_1 之间的所有路径的方法是什么？什么是计算复杂度？

如果以上是不可能的，那么有什么方法可以生成长度不超过 K 的所有路径。

我目前正在使用这个 Jackson插件

哪个序列化了我的循环图。然后在客户端上，我使用JSOG来解码 {@ref} 对象，如下所示：

当我尝试将 json 发送回服务器时，问题就来了。如果我不对数据做任何事情，我会得到“超出最大调用堆栈大小”，显然是因为我的 js 对象是循环的。我尝试使用：

但随后杰克逊对所有@id 和@refs 感到窒息：

有没有人知道如何做到这一点？

我编写了用于计算有向图中的循环数的代码DFS。检查循环是否存在的方法工作正常。我现在遍历所有顶点（我在 HashMap 中）并检查是否有一个顶点未被访问，然后检查是否存在循环，如果存在则将计数器加 1。现在代码中断，它没有给出正确的数字循环例如：对于具有以下边的图：

这是我的代码；

我遇到了等待图，我想知道，是否有任何有效的算法来检测向有向图添加边是否会导致循环？

有问题的图是可变的（它们可以添加或删除节点和边）。而且我们对实际知道一个违规循环并不感兴趣，只知道有一个就足够了（以防止添加违规边缘）。

当然，可以使用一种算法来计算强连接组件（例如 Tarjan 的）来检查新图是否是非循环的，但是每次添加边时再次运行它似乎效率很低。

我一直在编写代码以在有向图中获取所有可能的循环。这是一个跟踪后沿的实现，只要找到一个后沿，它就会返回真，即检测到一个周期。我将其扩展到以下内容：计算树中所有可能的后边缘，后边缘的数量应该给出周期数。不确定这是否正确。使用它，我实现了以下内容： 下面的count变量没有用。最初我有它来计算每个周期的计数。但这并没有给出正确的答案。但是edgeMap存储所有后边缘的大小似乎在某些图中给出了正确的循环数，但不是全部。

该代码适用于图片中的 G2 和 G3，但不适用于 G1。（G1 只有两个周期，但我得到三个后沿）。任何关于我可能出错的建议都会有所帮助

我遇到了这篇SO 帖子，其中建议在有向图中使用 DFS 进行循环检测由于回溯而更快。在这里，我引用该链接：

深度优先搜索比广度优先搜索更节省内存，因为您可以更快地回溯。如果您使用调用堆栈也更容易实现，但这依赖于最长的路径不会溢出堆栈。

此外，如果您的图表是定向的，那么您不仅要记住您是否访问过某个节点，还要记住您是如何到达那里的。否则你可能会认为你找到了一个循环，但实际上你只有两条独立的路径 A->B，但这并不意味着有一条路径 B->A。通过深度优先搜索，您可以在下降时将节点标记为已访问，并在回溯时取消标记它们。

为什么回溯很重要？

有人可以用示例图解释给定A->B示例中的含义吗？

最后，我有一个DFS用于在有向图中进行循环检测的代码，它不使用回溯，但仍然在O(E+V).

我正在使用递归回溯在有向图中寻找循环。这里有一个建议的伪代码，这里是：

使用起始节点调用上述函数：

虽然与 相比Tarjans algorithm，这不是最有效的算法，但这对我来说很简单，我可以理解。目前，此代码没有检测到的循环次数计数。

我用Java实现了这个：

对于具有以下边的图形：
(1 2),(2 3),(3 1),(2 5),(5 6),(6 2)-- 我得到 6 个周期作为输出。

(1 2),(2 3),(3 4),(4,1),(2 5),(5 6),(6 2)-- 我得到 7 个周期作为输出。

我可以看到我当前的代码对已经是先前检测到的循环的一部分的每个顶点进行循环检测（例如：具有三个节点的循环为每个单独的节点提供了三个循环，而这必须是一个）。我需要一些提示，说明出了什么问题并进行了一些修复。

如何检测循环中的

1. 有向图
2. 无向图。

对于无向图..我想到的一种算法是使用不相交集。

• 对于 G 中的每个顶点 v
  • 套装(v)
• 对于 G 中的每个边 e(u,v) 一个接一个
  • 如果查找集(u) == 查找集(v)
    • return true // 循环存在
• 返回假