从文本文件中检测有向图中的周期 [英] Detect Cycle In Directed Graph from text file

问题描述

我试图读取文本文件中的值，然后确定它所表示的图是否是DAG。我想知道在时间效率方面最快的方法是什么。

以下是文本文件

  3 
 2 
 1,2，
 2,3 
  

我正在考虑制作和邻接列表与给定的信息，然后从那里移动。任何帮助都不胜感激

解决方案

有一种方法，虽然可能不是最快的方法，但拓扑排序图表。当且仅当算法失败时，图形才有循环（请参见卡恩算法） 。

运行时间是 O（| V | + | E |），其中 | V | 是顶点的数量， | E | 是边的数量。

有一篇Bender等人的论文。 （Robert Tarjan是其中一位作者），一种新的方法增量循环检测和相关问题，您可能需要查看一下。

另一个相关论文是增量循环检测，拓扑排序和强大组件维护 bu Haeupler et al。 （Tarjan又是作者之一）。

I am trying to read in the values from a text file then determine if the graph it represents is a DAG or not. I am wondering what the quickest way to approach this is in terms of time efficiency.

Here is the text file

3
2
1,2,
2,3

I was thinking of making and adjacency list with the given information and then move from there. Any help is greatly appreciated

解决方案

One way, though probably not the fastest one, is to topologically sort the graph. The graph has a cycle if and only if the algorithm fails (see Kahn's algorithm).

The running time is O(|V| + |E|), where |V| is the number of vertices and |E| is the number of edges.

There's a paper by Bender et al. (Robert Tarjan is one of the authors), A NEW APPROACH TO INCREMENTAL CYCLE DETECTION AND RELATED PROBLEMS, which you might want to take a look at.

Another relevant paper is Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance bu Haeupler et al. (Tarjan is again one of the authors).

这篇关于从文本文件中检测有向图中的周期的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！