我如何才能找到(遍历)有向图中从/到给定节点的所有周期?
例如,我想要这样的东西:
A->B->A
A->B->C->A
而不是: B - > C > B
我如何才能找到(遍历)有向图中从/到给定节点的所有周期?
例如,我想要这样的东西:
A->B->A
A->B->C->A
而不是: B - > C > B
当前回答
澄清:
Strongly Connected Components will find all subgraphs that have at least one cycle in them, not all possible cycles in the graph. e.g. if you take all strongly connected components and collapse/group/merge each one of them into one node (i.e. a node per component), you'll get a tree with no cycles (a DAG actually). Each component (which is basically a subgraph with at least one cycle in it) can contain many more possible cycles internally, so SCC will NOT find all possible cycles, it will find all possible groups that have at least one cycle, and if you group them, then the graph will not have cycles. to find all simple cycles in a graph, as others mentioned, Johnson's algorithm is a candidate.
其他回答
深度优先搜索和回溯应该在这里工作。 保存一个布尔值数组,以跟踪您以前是否访问过某个节点。如果您没有新节点可访问(不涉及已经访问过的节点),那么只需返回并尝试不同的分支。
如果你有一个邻接表来表示图,DFS很容易实现。例如adj[A] = {B,C}表示B和C是A的子结点。
例如,下面的伪代码。“start”是开始的节点。
dfs(adj,node,visited):
if (visited[node]):
if (node == start):
"found a path"
return;
visited[node]=YES;
for child in adj[node]:
dfs(adj,child,visited)
visited[node]=NO;
用开始节点调用上面的函数:
visited = {}
dfs(adj,start,visited)
从节点X开始,检查所有子节点(如果无方向,父节点和子节点是等价的)。将这些子节点标记为X的子节点。对于任何这样的子节点A,标记它的子节点是A的子节点,X',其中X'标记为2步远。)如果您稍后点击X并将其标记为X的子节点”,这意味着X处于3节点周期中。回溯到它的父节点很容易(因为算法不支持这一点,所以你可以找到任何一个有X'的父节点)。
注意:如果图是无向的或者有任何双向边,这个算法会变得更复杂,假设你不想在一个周期内两次遍历同一条边。
我发现解决这个问题的最简单的选择是使用名为networkx的python库。
它实现了这个问题的最佳答案中提到的约翰逊算法,但它的执行非常简单。
简而言之,你需要以下几点:
import networkx as nx
import matplotlib.pyplot as plt
# Create Directed Graph
G=nx.DiGraph()
# Add a list of nodes:
G.add_nodes_from(["a","b","c","d","e"])
# Add a list of edges:
G.add_edges_from([("a","b"),("b","c"), ("c","a"), ("b","d"), ("d","e"), ("e","a")])
#Return a list of cycles described as a list o nodes
list(nx.simple_cycles(G))
答案:[['a', 'b', 'd', 'e'], ['a', 'b', 'c']]
DFS c++版本的伪代码在二楼的答案:
void findCircleUnit(int start, int v, bool* visited, vector<int>& path) {
if(visited[v]) {
if(v == start) {
for(auto c : path)
cout << c << " ";
cout << endl;
return;
}
else
return;
}
visited[v] = true;
path.push_back(v);
for(auto i : G[v])
findCircleUnit(start, i, visited, path);
visited[v] = false;
path.pop_back();
}
http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf