-
0 votesanswersviews
有向图中的特征向量
我想用igraph包测量R中262000个节点和1M边缘的有向图的特征向量中心性 . 当我运行命令时，我收到此错误： > ev<-evcent(amazon,directed=TRUE) .Call中的错误（“R_igraph_eigenvector_centrality”，图形，定向，比例，：在arpack.c：1174：ARPACK错误，达到的最大迭代次数De plus：警告消... -
1 votesanswersviews
如何对深度优先搜索中未遍历的边进行分类？
我有一个任务，要求一个人在有向图上执行深度优先搜索，并对图的所有边进行分类 . 但是，我很困惑如何在深度优先搜索过程中对未遍历的边缘进行分类，看看这些边缘在搜索过程中是如何分类的 . 让我总结一下深度优先搜索上图 . 首先我们从1到2.然后我们从堆栈中弹出2，因为无处可去，所以我们回到1.然后我们从1到3.然后我们从3到4 . 好吧，假设我得到了那个部分，那么遍历的所有边都是树边正确吗？那么，如... -
3 votesanswersviews
使用递归回溯在有向图中查找所有周期
我正在使用递归回溯来查找有向图中的循环 . 这个here有一个建议的伪代码，它在这里： dfs(adj,node,visited): if (visited[node]): if (node == start): "found a path" return; visited[node]=YES; for child... -
4 votesanswersviews
有向图属性/深度优先搜索
据我所知，如果在某个任意有向图上存在从顶点“a”到顶点“b”的路径，则可能存在某种情况，即使用图形上的深度优先搜索，该顶点“b”可以在顶点“a”完成处理后的搜索中发现 . 但是，这对我来说似乎不可能（在绘制出许多图表之后） . 有任何想法吗？ -
3 votesanswersviews
如何在迭代DFS中检测有向图中的周期？
我当前的项目包含一组带输入和输出的节点 . 每个节点都可以获取其输入值并生成一些输出值 . 这些输出可以用作其他节点的输入 . 为了最小化所需的计算量，在应用程序启动时检查节点依赖性 . 更新节点时，它们以相互依赖的相反顺序更新 . 也就是说，节点类似于 directed graph . 我正在使用迭代DFS（没有递归来避免巨大的图形中的堆栈溢出）来计算依赖关系并创建更新节点的顺序 . 我还想避... -
12 votesanswersviews
在有向图上的广度优先搜索期间的边缘分类
在有向图上的广度优先搜索时，我很难找到正确分类边的方法 . 在广度优先或深度优先搜索期间，您可以对满足4个类的边进行分类： 树 返回 CROSS FORWARD Skiena [1]给出了一个实现 . 如果沿着从v1到v2的边缘移动，这里是一种在Java中的DFS期间返回类的方法，以供参考 . 父映射返回当前搜索的父顶点，以及 timeOf() 方法，即发现顶点的时间 . if... -
1 votesanswersviews
使用Python中的Networkx在DAG上查找最长路径
我有一个非常大的字符串DAG（~200k） . 我想找到此图中存在的最长路径 . 下面的代码是我如何设置图表（从字符串列表 new_list ） . #create new empty graph g = nx.DiGraph() #add all words to graph for word in new_list: g.add_node(word) #fill graph wit... -
1 votesanswersviews
高效的gremlin查询在图中查找循环
我有一个很大的TinkerGraph（~80.000顶点，~160.000边），我需要使用Apache TinkerPop/Gremlin查询语言检测其中是否存在循环 . 如果有的话，我想获得其中一个周期的顶点 . 有没有办法编写 O(|V| + |E|) gremlin查询来查找图中的循环路径？ 我尝试使用here和here中的查询，但它们太慢而且超时了 . 我怀疑它们不是 O(|V| + |... -
343 votesanswersviews
用于检测有向图中的循环的最佳算法
检测有向图中所有周期的最有效算法是什么？ 我有一个有向图表示需要执行的作业的计划，作为节点的作业和作为边缘的依赖 . 我需要检测此图中循环的错误情况，从而导致循环依赖 . -
1 votesanswersviews
查找长度<= k的有向图中的所有循环
有没有办法修改算法 Finding all cycles in undirected graphs 将边缘视为指示，只考虑长度<= k的周期？ -
355 votesanswersviews
用于检测有向图中的循环的最佳算法
检测有向图中所有周期的最有效算法是什么？ 我有一个有向图表示需要执行的作业计划，作业是节点，依赖是边缘 . 我需要检测此图中循环的错误情况，从而导致循环依赖 . -
4 votesanswersviews
走一个有向图
我在该图中有一个有向无环图和一个原点顶点 v .如何访问 v 可以访问的所有顶点，如果我访问 v1 我已经访问了所有具有边缘的顶点 v1 ？ 例： /-----V A->B->C 从 A 开始， C 必须在 B 之后访问 .我试着做一个BFS并检查每个顶点的父节点，如果它们没有被访问，请重新添加它以供日后使用，但事实证明它太慢了，我相信可以是 O(v^2) . 知道图形有点二进制... -
1 votesanswersviews
在可能未连接的有向图中找到循环的混淆
我很困惑这个answer . 为什么DFS在访问每个节点和每个边缘最多一次时无法确定有向图中是否存在循环？使用white, gray, black方法，如果存在后沿，则应该能够找到循环 . 对于未连接的有向图，为什么不能执行以下操作：从任意节点运行DFS v 并访问与 v 连接的节点数，然后在图中的另一个未访问的任意节点上运行DFS，如果有的话，直到所有访问节点？ 在我看来，DFS应该能够找到一... -
1 votesanswersviews
在深度优先的图搜索树中返回边
我已经完成了一项家庭作业，大约3分中有3分是针对以下问题的 . “假设你在有向图上构造了一个DFS树 . 之后你会注意到没有任何后边缘 . 这对图形有什么看法？” 我已经给出了一些想法，我可以理解的是，这意味着存在隐含的依赖性，这样只有一条特定的路径存在于拓扑中遍历图形 . 不幸的是，我无法在网络上的任何地方找到任何关于此的信息，所以我想我会在这里发布我的答案，看看是否有人可以权衡其（正确） ... -
2 votesanswersviews
有向图中循环识别的有效算法？ [重复]
可能重复：用于检测有向图中的循环的最佳算法 我正在寻找一种算法来在有向图中找到循环 . 我的图表只在节点中有标签，而不是在边缘，它可以变得非常大 . 算法的输出应该是作为一组列表的循环，每个列表应该包含循环中涉及的节点的标签，因此，列表中的第一个和最后一个元素应该是相同的 . 我正在使用的图表很可能只有一个连接组件，没有强连接组件 . 预计周期数会很少（我仍然需要检查） . 对于这个或类似的东... -
0 votesanswersviews
找到有向图的最短路径
对于 (u, v) ∈ E ，有一个有向图 G = [V ; E] ，边权重为 w(u, v) . 假设 {d[v], π[v]}; v ∈ V 和声明的值 这些是最短路径的长度和前一个节点的长度 它为 v ∈ V ，我怎么能验证这个语句是真还是假，不能从头开始解决整个最短路径问题？这是我遇到的一个问题，我头脑中的想法不多 . -
0 votesanswersviews
将无向图转换为具有特定条件的有向图
给出了无向图，其具有M个边和N个顶点，我们必须将每个边从u-v转换为u-> v或v-> u，使得每个顶点的不均匀是均匀的 . 这种方法或算法适合于最小时间复杂度 . -
2 votesanswersviews
在有向图中使用DFS进行循环检测绝对需要回溯吗？
我遇到了这个SO post，其中建议在有向图中使用DFS进行循环检测由于回溯而更快 . 在这里，我引用该链接： 深度优先搜索比广度优先搜索更有效，因为您可以更快地回溯 . 如果使用调用堆栈，它也更容易实现，但这依赖于不会溢出堆栈的最长路径 . 此外，如果您的图表是定向的，那么您不仅要记住您是否访问过某个节点，还要记得您是如何到达那里的 . 否则你可能会认为你已经找到了一个循环，但实际上你所拥有的... -
2 votesanswersviews
在Matlab中使用有向图的有向图
由Matlab中的函数digraph创建的有向图的默认值在节点之间的线中间具有箭头 . 有没有办法修改有向图的图形，所以箭头位于行尾？ 例如： A = ones(4) - diag([1 1 1 1]) G = digraph(A) plot(G) 得到： 可以看出，箭头位于线的中间，但我希望箭头位于末端或每条线 . -
136 votesanswersviews
GraphViz - 如何连接子图？
在 DOT 的 DOT 语言中，我试图表示一个依赖关系图 . 我需要能够在容器内部拥有节点，并且能够使节点和/或容器依赖于其他节点和/或容器 . 我正在使用 subgraph 来代表我的容器 . 节点链接工作正常，但我无法弄清楚如何连接子图 . 鉴于下面的程序，我需要能够用箭头连接 cluster_1 和 cluster_2 ，但我尝试的任何东西都会创建新节点而不是连接集群： digraph G ... -
2 votesanswersviews
在循环有向图中检测多个循环
我有一个有多个循环的有向循环图，我需要一种方法来检测（和列出）有向图中的每个循环 . 图表可以在这里看到：http://img412.imageshack.us/img412/3327/schematic.gif 这是为了调试我的python脚本而放在一起的虚拟图 . 它包含周期： [n13, n14], [n6, n8, n15, n16, n7], [n6, n8, n9, n7] 该算法必须... -
4 votesanswersviews
力导向图中可能出现双向箭头？
我创建了一个类似于这个力导向图的图形：http://bl.ocks.org/d3noob/5141278： 以链接为例：Sarah与James联系在一起，而James则与Sarah有关 . 而不是用两个箭头（每个方向一个）弄乱页面，有没有办法让它只有一个箭头，两端都有三角形？ -
1 votesanswersviews
如何用networkD3在R中绘制有向图？
当我使用NetworkD3绘制有向图时，边缘不是定向的，我该如何修复它？一个例子 ： library(networkD3) data(MisLinks) data(MisNodes) forceNetwork(Links = MisLinks, Nodes = MisNodes, Source = "source", Target = "target... -
2 votesanswersviews
在增强图库c的有向图中合并多个顶点
我是C语言中的Boost图形库（BGL）的新手 . 有没有一种简单的方法来合并使用BGL构建的有向图中的MULTIPLE顶点？我使用以下示例代码来构造我的有向图 - http://www.boost.org/doc/libs/1_60_0/libs/graph/example/quick_tour.cpp 谢谢 -
1 votesanswersviews
每个节点的DFS是否会在有向图中给出所有周期
我想在有向图中找到所有周期 . 从一个节点开始深度优先搜索将找到一些周期（找到后边缘） . 因此，我将dfs应用于图中的所有节点（即，每次根是不同的节点） . 我能够使用它来获得所有循环（通过消除重复的循环） . 但是，我不确定这是否适用于所有图表以及这是否是正确的方法 . 任何人都可以建议我这是否适用于所有情况 . 谢谢 -
14 votesanswersviews
循环有向图的遍历
我有一个循环有向图 . 从叶子开始，我希望将附加到每个节点下游的数据传播到可从该节点到达的所有节点 . 特别是，我需要在周期稳定的任何周期内继续推送数据 . 我完全相信这是一个股票图遍历问题 . 但是，我在寻找合适的算法时遇到了一些困难 - 我想我缺少一些关键的搜索关键字 . 在我尝试编写自己的半O（n ^ 3）算法之前，有人能指出我一个合适的解决方案吗？这个特殊问题叫什么？ -
1 votesanswersviews
单个算法在定向和无向图上工作以检测周期？
我一直在尝试实现一种算法来检测 directed and undirected graph 中的周期（可能是多少周期） . 这就是代码应该适用于有向图和无向图 . 在各种帖子中大多推荐使用 DFS or topological sort . 但在很大程度上，一切都针对无向图 . This link描述了一种循环检测方法 . 根据我的理解，这适用于有向图 . This link具有无向图中循环检测... -
6 votesanswersviews
有向概率图 - 减少周期的算法？
考虑一个有向图，该图从第一个节点 1 遍历到某个最终节点（没有更多的外边缘） . 图中的每条边都有与之相关的概率 . 总结将每条可能路径转向所有可能的最终节点的概率返回 1 . （这意味着，我们保证最终到达最终节点之一 . ） 如果图中的循环不存在，问题将很简单 . 不幸的是，在图中可能出现相当复杂的循环，其可以遍历无限次（概率随着每次循环遍历而成倍增加，显然） . 是否有通用算法来找到到达每... -
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... -
4 votesanswersviews
递归lambda表达式通过有向图找到路径？
我需要在复杂的图形结构中找到一条或多条路径 . 该图使用类似于此的内容构建： class Node { public string Value { get; set;} public List<Node> Nodes { get; set;} public Node() { Nodes = new List<Node>();...