-
1594 votesanswersviews
家谱软件中的循环
我是一些家庭树软件的开发者(用C和Qt编写) . 在我的一位客户向我邮寄错误报告之前,我没有遇到任何问题 . 问题是顾客有两个孩子和自己的女儿,因此,他因错误而无法使用我的软件 . 这些错误是我处理家族图的各种断言和不变量的结果(例如,在走一个循环之后,程序声明X不能同时是Y的父亲和祖父) . 如何在不删除所有数据断言的情况下解决这些错误? -
4 votesanswersviews
给定具有自循环的有向加权图,找到与给定节点x完全相距k dist的节点列表?
图中的每个边都具有1的权重,图可以具有周期,如果节点具有自循环,则它可以是从0到无穷大的任何距离,具体取决于编号 . 我们采取自我循环的时间 . 我已经使用bfs解决了这个问题,但是对距离的约束是10 ^ 9的顺序,因此bfs很慢 . 我们将在形式(距离,源)的给定图形上询问多个查询,并且o / p是从源顶点开始精确地在给定距离处的节点列表 . Constraints 1<=Nodes<... -
1 votesanswersviews
查找长度<= k的有向图中的所有循环
有没有办法修改算法 Finding all cycles in undirected graphs 将边缘视为指示,只考虑长度<= k的周期? -
3 votesanswersviews
在无向图中查找所有非重叠循环
我需要在无向图上找到所有简单的非重叠循环 . 为了找到所有现有周期,我在这里找到了算法的Objective-C版本: Finding all cycles in undirected graphs @interface HSValue : NSObject @property (nonatomic, assign) CGPoint point; @end @implementation HSVal... -
11 votesanswersviews
为什么Oracle与nocycle连接遵循root循环
有没有人知道为什么当循环发生在顶级节点(根节点连接到根节点)时,Oracle继续遵循循环循环之外的路径?更重要的是,如何预防呢? 我有Oracle 11g第2版(11.2),我一直在探索分层查询 . 我将围绕Oracle数据库SQL语言参考第9-4页的图9-1中的树结构构建我的问题 我使用供应商和客户的概念为这棵树创建了一个表格结构: create table t ( vendor ... -
48 votesanswersviews
查找无向图中的所有循环
我需要一个工作算法来查找无向图中的所有简单循环 . 我知道成本可能是指数级的,问题是NP完全的,但我将在一个小图(最多20-30个顶点)中使用它,并且循环数量很少 . 经过长时间的研究(主要是在这里),我仍然没有工作方法 . 以下是我的搜索摘要: Finding all cycles in an undirected graph Cycles in an Undirected Graph - &... -
3 votesanswersviews
有向无环图中更快的周期检测?
我在Ruby 1.9.3中有一个构建RubyTree的程序 . 我的数据最好被描述为Directed Acyclic Graph(DAG);请注意,它是 not 一个polytree . 好吧,至少数据应该是DAG,尽管用户尽最大努力用糟糕的数据来阻止我的程序 . 我通过解析XML文档动态构建DAG . XML文档未明确指定树结构,但确实提供了整数ID的交叉引用,这些整数ID用于在文档中的元素之... -
2 votesanswersviews
用于检测图中循环的最快算法
给定一个无向图,检测它是否包含循环的最佳算法是什么? 在跟踪被访问节点的同时进行广度优先或深度优先搜索是一种方法,但它是O(n ^ 2) . 有什么更快的吗? -
34 votesanswersviews
使用DFS在图表中检测周期:2种不同的方法和区别
请注意,图表表示为邻接列表 . 我听说有两种方法可以在图表中找到一个循环: 保留一个布尔值数组,以跟踪您之前是否访问过某个节点 . 如果你的新节点用完了(没有点击你已经存在的节点),那么只需回溯并尝试不同的分支 . 来自Cormen的CLRS或Skiena的那个:对于无向图中的深度优先搜索,有两种类型的边,树和背面 . 当且仅当存在后沿时,图形具有循环 . 有人可以解释图形的后边缘是什... -
0 votesanswersviews
如何使用BFS在无向二分图中找到最短周期?
如何使用广度优先搜索在简单(非定向)二分图中找到最短周期? -
2 votesanswersviews
使用快速图检测无向图中的循环
无论如何都要检测用快速图生成的无向图中的所有周期并打印周期列表 . 我用Google搜索了一下,我发现可以使用“深度优先搜索算法”检测图形中的周期 . 然后我尝试了这样的事情: var g = new UndirectedGraph<int, TaggedUndirectedEdge<int, int>>(); var e1 = new TaggedUndirectedE... -
2 votesanswersviews
R中无向图中的循环
我有一个无向图,我想做的是检测其中有三个或更多节点的周期 . R中有一个库可以做到吗?如果没有,我可以实现一个简单的算法 . test <- data.frame(start=c(1,2,3,4), stop=c(2,3,1,5)) 我希望它能以1,2,3以及它找到的任何其他周期返回 . -
0 votesanswersviews
使用不相交集在无向图中进行循环检测?
我正在使用不相交集的查找/联合方法实现无向图中的循环检测代码 . 这是实施: public boolean isCyclicundirected(){ int k; ArrayDisjointSet set = new ArrayDisjointSet(5); //Set<Vertex> parents = new HashSet<Vertex>()... -
1 votesanswersviews
Scala - 使用DFS检测周期?我的代码是错误的,我似乎无法弄清楚为什么
我正在尝试编写一个函数,如果图形有一个循环,则返回true,但我非常挣扎 . 我在Scala中表示如下所示的图,其中每个子列表的索引表示节点0,1,2以后,并且该子列表的组件指示从子列表的索引到节点 2 的边缘,例如成本 1 . 请注意,这是一个无向图表示 . 下面是一个具有循环的无向图的示例 . ListBuffer( ListBuffer((1, 1), (2, 1), (3, 1)),... -
1 votesanswersviews
初学者编码器检查输入是否是循环的一部分?
public Graph (int nb){ this.nbNodes = nb; this.adjacency = new boolean [nb][nb]; for (int i = 0; i < nb; i++){ for (int j = 0; j < nb; j++){ this.adjacency[i][j] ... -
0 votesanswersviews
在有向图中查找循环
我必须在图中检测一个循环 . 矩阵的大小是m×n,其中m是进程总数,n是资源总数 . 0:进程Pi和资源Rj之间没有边缘 . 1:从进程Pi到资源Rj存在传出边缘 . 2:从资源Rj到进程Pi存在传出边缘 . TestCase01.txt的示例是2,10,01,2 输出应该是检测到死锁程序找到此循环:P0 - > R1 - > P2 - > R0 - &g... -
1 votesanswersviews
一般图形周期检测(请确认我的答案)[关闭]
问题: 如果无向图只包含一个周期,则它是单向的 . 描述用于确定给定图G是否是单圈的O(| V | | E |)算法 . 我的解决方案 int i = 0 在G上运行修改后的DFS,每当我们决定不访问顶点时我们就会增加i,因为它已经被访问过了 . DFS完成后,如果i == 1,则图形是单圈形的 . 我认为这个解决方案可行,但我想知道是否有一个反例可以证明它是错误的 . 如果有人能澄清那将是伟大的... -
2 votesanswersviews
在循环有向图中检测多个循环
我有一个有多个循环的有向循环图,我需要一种方法来检测(和列出)有向图中的每个循环 . 图表可以在这里看到:http://img412.imageshack.us/img412/3327/schematic.gif 这是为了调试我的python脚本而放在一起的虚拟图 . 它包含周期: [n13, n14], [n6, n8, n15, n16, n7], [n6, n8, n9, n7] 该算法必须... -
2 votesanswersviews
确定邻接矩阵是否具有循环,然后输出该循环
所以我有2个功能: UPDATED unordered_map<int, bool> visited2; vector<vector<int>> elements2D; bool DFSDetectCycle(int vertex){ s.push(vertex); while(!s.empty()){ int np_vert... -
0 votesanswersviews
用于BGL图的简单循环移除算法
我的问题应该很简单,给定一个图(BGL adjacency_list)是否有一个简单的算法去除周期?我的第一次尝试是使用DFS访问者检测关闭循环的边缘然后将其删除但我无法正确实现它 . 有什么建议?代码示例最好 .