标签: graph-theory

我需要使用DFS在有向图中找到最长的周期.

我曾经看过这篇维基百科的文章描述了这样做的方式,我认为它解决了这个问题,例如用以下三种状态之一标记节点:节点尚未访问,完成搜索节点,节点访问,但尚未完成访问.

如果有人能与我分享链接,我将不胜感激.顺便说一句,它不是Tarjan的算法.

下面的问题是我想要解决的问题,如果你想知道的话.

在第一行中给出的两个数字是N和M,每个数字表示节点的数量和有向边的数量.

从第二行给出M组两个数字A和B,这意味着节点A和B连接但您只能遍历从A到B的节点.

input.txt中:

7 9  
1 2  
2 3  
3 1  
3 4  
4 5  
5 1  
5 6  
6 7  
7 2  

在这种情况下,答案是6,因为2> 3> 4> 5> 6> 7> 2.

使用不相交集数据结构可以轻松获得Graph的连通组件.而且,它只支持增量连接组件.

但是,在我的情况下,删除边缘非常常见,因此我正在寻找算法或新结构可以完全动态地维护连接组件(包括添加和删除边缘)

谢谢

我有一个无向平面图,每个节点都有一个权重.我希望将图形分成尽可能多的连接不相交的子图(编辑:或者达到子图的最小平均权重),条件是每个子图必须达到固定的最小权重(这是一个权重之和)其节点).只包含单个节点的子图也可以(如果节点的权重大于固定的最小值).

到目前为止我发现的是一种启发式:

create a subgraph out of every node
while there is an underweight subgraph:
  select the subgraph S with the lowest weight
  find a subgraph N that has the lowest weight among the neighbouring subgraphs of S
  merge S to N

显然这不是最佳的.有没有人有更好的解决方案？(也许我只是无知,这不是一个复杂的问题,但我从未研究过图论......)

编辑(更多背景详细信息):此图中的节点是要为其提供统计数据的低规模管理单位.但是,这些单位需要有一定的最小人口规模,以避免与个人数据立法发生冲突.我的目标是创建聚合,以便在途中丢失尽可能少的信息.邻域关系充当图边,因为结果单元必须是连续的.

集合中的大多数单元(节点)远高于最小阈值.如示例所示(最小尺寸50),其中约5-10%低于阈值且尺寸不同:

我有一个DAG存储我的应用程序中的某些对象之间的关系.当通过在现有顶点下面添加新顶点(即,隐式地在新顶点中创建新边)并且然后(在任何稍后时间)从那里到其他顶点的新边缘来更新此结构时,我想确保图形保持DAG,即我的代码不会创建周期.

我是否必须为每个插入和连接操作添加一个循环检测,或者是否有我可以遵循的规则,这将保证我不会产生循环？

我能想到的一种方法是存储每个节点的拓扑级别,并且只允许指向更高级别(远离源节点)的新边缘.然而,看起来这实际上会让我失去很多我希望通过使用DAG而不是一组普通树来实现的灵活性.

我正试图找到一种方法来找到通过杂货店的最短路径,访问一个位置列表(购物清单).路径应该从指定的起始位置开始,并且可以在多个结束位置结束(有多个结账计数器).此外,我在路径上有一些预定义的约束,例如"购物清单上的项目x需要是路径上的最后一个,倒数第二个或第三个最后一个项目".有一个函数将返回给定路径的true或false.最后,这需要使用有限的CPU功率(在智能手机上)和大约一秒左右来计算.如果这是不可能的,那么最佳路径的近似值也是可以的.

这可能吗？到目前为止,我认为我需要首先使用像A*或Dijkstra这样的东西来计算列表中每个项目之间的距离.在那之后,我应该像旅行推销员那样对待它吗？因为在我的问题中有一个指定的起始节点,指定的终端节点和一些约束,这些约束不在旅行商问题中.

我试图理解图论的主要概念及其中的算法.大多数算法似乎包含"放松条件"我不确定这是什么.

请有人向我解释一下.

这方面的一个例子是dijkstras算法,这里是伪代码.

 1  function Dijkstra(Graph, source):
 2      for each vertex v in Graph:           // Initializations
 3          dist[v] := infinity               // Unknown distance function from source to v
 4          previous[v] := undefined          // Previous node in optimal path from source
 5      dist[source] := 0                     // Distance from source to source
 6      Q := the set of all nodes in Graph
    // All nodes in the graph are unoptimized - thus are in Q
 7      while Q is not empty:                 // …

我有一个加权图,没有负权重,我想找到从一个节点到另一个节点的路径,试图最小化单步的成本.我不需要最小化旅行的总成本(例如Dijkstra),而是平均步骤成本.但是,我有一个约束:K,路径中的最大节点数.

所以例如从A到J可能Dijkstra会找到这条路径(括号之间的重量)

A (4) D (6) J -> total cost: 10

我需要的算法,设置K = 10,会找到类似的东西

A (1) B (2) C (2) D (1) E (3) F (2) G (1) H (3) J -> total cost: 15

这个问题有没有众所周知的算法？

提前致谢.

欧亨尼奥

编辑为templatetypedef的答案.一些问题:

1)事实上它可能多次采取一个周期来降低平均值对我的问题不利:也许我应该提到它但我不想多次访问同一个节点

2)是否有可能利用我没有负权重的事实？

3)当你说O(kE)时,你是指整个算法还是只是附加部分？

让我们在C中采用这个简单的实现,其中n =节点数e =边数,d是具有距离的向量,具有前驱的pa向量和结构边(u,v,w)记忆图中的边

for (i = 0; i < n; ++i)
    d[i] = INFINITY;

    d[s] = 0;

    for (i = 0; i < n - 1; ++i)
        for (j = 0; j < e; ++j)
            if (d[edges[j].u] + …

我有一个由Java中的邻接矩阵表示的随机图,我如何在该图中找到连接的组件(子图)？

我找到了BFS和DFS,但不确定它们是否合适,我也不知道如何为邻接矩阵实现它们.

有任何想法吗？

几乎完全相同的问题.但是我仍然不明白,这种启发式工作原理是什么以及顶点通过的顺序是什么.书中还有一张图片:

这显示了最近neghbor启发式和我认为是最近对启发式的比较.从图片中我可以假设在顶部图片上,首先选择了0点,但是在底部图片上选择了最左边或最右边的一个.因为没有任何关于第一点选择的说法(也是最近对启发式没有做任何动作),我可以假设任何算法结果都不错,如果没有,它将不会给你底部图片考虑一下,从什么开始.

现在我只想知道,最近对启发式的步骤是什么.将理解类似于底部的图片,其具有与每次迭代相关联的数字以及解释.

这是从该帖子中获取的书的链接.

我试图在一个可能有循环但没有自循环的有向加权图中找到权重小于N 的两个顶点之间的所有路径。到目前为止，我只能通过使用AllDirectedPaths然后过滤掉权重大于 N 的路径来做到这一点：

SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> g = new SimpleDirectedWeightedGraph<>(DefaultWeightedEdge.class);
AllDirectedPaths<String, DefaultWeightedEdge> allPaths = new AllDirectedPaths<>(g);
int maxWeight = 30;
List<GraphPath<String, DefaultWeightedEdge>> pathsLimitedByWeight = allPaths.getAllPaths(startVertex, endVertex, false, maxWeight / minGraphLatency)
    .filter(graphPath -> graphPath.getWeight() < maxWeight)
    .collect(Collectors.toList());

这种方法显然是次优的，因为对于较大的图形它很慢。为了限制输出并使其更快，我提供maxPathLength了AllDirectedPaths#getAllPaths，我将其设置为路径可以除以图中边的最小权重的最大权重，因为在我的情况下，边权重是一个整数并且总是大于1.

我考虑过使用KShortestSimplePathscustom PathValidator，但它只支持简单的路径，即不允许循环。

如果有的话，我在 jgrapht 中还有什么其他选项可以用来解决查找所有路径而不必自己遍历图形。