标签: cyclic-graph

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

有问题的图是可变的(它们可以添加或删除节点和边).而且我们对实际知道一个有问题的周期并不感兴趣,只知道有一个是足够的(以防止添加一个有问题的边缘).

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

我搜索并找到了有关此主题的一些信息,但答案要么令人困惑,要么不适用.

我有这样的事情:

class Thing (val name:String, val refs:IndexedSeq[Ref])
class Ref (val name:String, val thing:Thing)

现在,我想说,加载一个文件,解析它并从中填充这个数据结构.它是不可变的和循环的,怎么会这样做？

另外,假设我确实填充了这个数据结构,现在我想修改它,比如更改rootThing.refs(3).name,怎么可能这样做呢？

感谢此处发布的想法.在这一点上,我在想如果一个人真的想要这样的东西的持久性数据结构,那就跳出框框思考并考虑客户端代码需要问什么问题.因此,不要考虑对象和字段,而应考虑查询,索引等.首先,我在想: 是否存在双向多图持久数据结构？

我有一个连接的,非定向的图,有N个节点和2N-3边.您可以考虑将图形构建到现有的初始图形上,该图形具有3个节点和3个边缘.每个节点都添加到图表上,并与图中的现有节点有2个连接.当所有节点都添加到图形中时(总共添加N-3个节点),构建最终图形.

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

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

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

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

我几乎被困在这里.你能帮我想一下另一个算法来告诉我图是一个循环图吗？

编辑

我在评论的帮助下意识到了(感谢你nm):

循环图由单个循环组成,具有N个边和N个顶点.如果存在包含给定图的所有节点的循环,那就是哈密顿循环. - nm

我实际上正在寻找哈密尔顿路径,我不打算这样做:)在第二个想法,我认为在构建它时检查图的哈密尔顿性质将更有效,这也是我也在寻找:时间效率.

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

编辑#2

我再次意识到,按照我描述的方式构建图形可能会改变哈密顿特性.考虑如下输入:

1 3
2 3
1 5
1 3

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

第4和第7个节点连接到相同的节点,从而将可以访问的最大节点数减少一次,如果我检测到这些冲突(不包括输入,例如3 3,这是您建议的示例)因为问题表明新添加的边连接到其他2个节点)并且从N开始降低最大节点数,我相信我可以得到正确的结果.

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

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

假设我有这个简单的类:

public class Pair {
    public readonly object first;
    public readonly object second;

    public Pair(object first, object second) {
        this.first = first;
        this.second = second;
    }
}

生成对的循环图是不可能的.

你将如何创建一个类似的类,它仍然是不可变的,但可以某种方式用于生成循环图？

我需要在Prolog中使用循环构建有向图(在运行时),我不知道如何表示它.我的要求是我需要在一个恒定的时间内从一个顶点到达他的邻居.

是否可以将其表示为树,例如:

t(left_son,V,right_son)

但如何解决周期？

我可以列出边缘列表:

graph([a,b,c,d],[e(a,b),e(b,c),e(c,a),e(c,d)])

要不就