问题标签 [directed-graph]

我需要在 google appengine 中存储一个大型动态无向图，最好的方法是什么？图表示必须能够支持快速拉出一组顶点（用于在页面上呈现）和来自特定顶点的所有链接，以及跨图的寻路（尽管实际上并不需要最佳路径，只是一个相当好一个）

我对这个主题的想法：最明显的方法是拥有一个顶点模型和一个引用两个顶点的边模型，但是听起来它最终会为每个操作使用大量查询，我想知道是否有更好的方法（也许以某种方式将链接信息构建到每个顶点中）

Erlang digraphs 模块通过改变状态让我感到惊讶。

在处理 Erlang 中的其他数据结构模块时，例如 sets 模块，传入的数据结构的实例是未修改的。该函数返回一个新的更改版本，例如

这不是处理 digraph 模块时的行为。

首先，为什么有向图库在这方面有所不同？

其次，更重要的是，有向图模块如何针对现有绑定添加新状态？

我假设状态被存储在另一个进程中，digraph 模块正在使用现有且未更改的绑定 G 进行标识。是这种情况吗？或者还有其他修改与绑定相关的状态的方法吗？

我需要检查有向图是否是强连接的，或者换句话说，是否所有节点都可以被任何其他节点（不一定通过直接边）到达。

一种方法是在每个节点上运行 DFS 和 BFS，并查看所有其他节点仍然可以访问。

有没有更好的方法来做到这一点？

我有一个图形结构，在满足某些条件之前，我将逐个删除边。我的大脑已经完全停止工作，我找不到有效的方法来检测删除一条边是否会导致我的图分裂为两个或多个图。

蛮力解决方案是执行 bfs，直到可以从随机节点到达所有节点，但是对于大型图，这将花费太多时间......

有任何想法吗？

编辑：经过一番搜索，我想做的似乎与弗勒里的算法非常相似，我需要在其中查找边缘是否是“桥”。

我有一个有向图，我的问题是枚举该图的所有最小（不能构造为其他循环的联合的循环）有向循环。这与 Tarjan 算法的输出不同。例如，对于这个维基百科页面上的有向图，我想将 c <-> d 和 d <-> h 作为两个独立的有向循环。

我不知道这个问题是否是多项式的。我浏览了一篇论文“枚举最小 Dicuts 和强连通子图”，似乎得出的结论是这个问题是增量多项式（我不知道它是什么意思），但我无法为这篇文章提取算法。我也不确定最小强连接组件是否等同于我定义的最小循环。

有人知道这个问题的答案吗？

提前致谢！！！

在 for 的DOT语言中GraphViz，我试图表示一个依赖关系图。我需要能够在容器内拥有节点，并且能够使节点和/或容器依赖于其他节点和/或容器。

我subgraph用来代表我的容器。节点链接工作得很好，但我不知道如何连接子图。

鉴于下面的程序，我需要能够使用箭头进行连接cluster_1，cluster_2但是我尝试过的任何操作都会创建新节点而不是连接集群：

这是一棵树：

1. 将有一个根。

2. 每个树节点都有零个或多个子节点。

3. 允许两个节点指向同一个子节点。假设节点 A 和节点 B 都有子节点 C。

但是，禁止这样做，

节点 A 是节点 B 的后代，节点 B 是节点 A 的后代。

一种被禁止的情况是

节点 A 有一个子节点 C 和节点 D，

节点 C 和 D 都有一个子节点 E，

节点 E 有一个 A 的子节点。

问题是，如何以最快的方式确定这个圈子？

更新：我意识到这是在有向图中找到任何循环。刚才我设法想出了一个类似于 Tarjan 算法的解决方案。

感谢您的评论。

我很好奇是否有一个特定的图算法通过选择一个起始节点然后通过 DFS 来遍历一个未加权的无环有向图。如果遇到具有未搜索前任的节点，则它应该回溯传入路径，直到已经探索了所有要开始的路径。

我找到了一个用于图形算法的维基百科类别，但这里有一小部分算法，我对其中的大多数都不熟悉。

编辑：示例：给定图 {AB, EB, BC, BD}，遍历为：{A,B,E,B,C,D} 或唯一顺序为 {A,B,E,C,D}。请注意，与 BFS 或 DFS 不同，此算法不需要在第一个起始节点的所有路径都用尽的情况下从新的起始节点重新开始。

我正在做一项任务，其中一个问题要求派生一种算法来检查有向图 G=(V,E) 是否是单连接的（对于所有不同的顶点 u，从 u 到 v 最多有一个简单的路径， v 的 v。

当然你可以蛮力检查它，这是我现在正在做的，但我想知道是否有更有效的方法。谁能指出我正确的方向？

我们如何检测有向图是否是循环的？我想使用广度优先搜索，但我不确定。有任何想法吗？