我如何才能找到(遍历)有向图中从/到给定节点的所有周期?
例如,我想要这样的东西:
A->B->A
A->B->C->A
而不是: B - > C > B
我如何才能找到(遍历)有向图中从/到给定节点的所有周期?
例如,我想要这样的东西:
A->B->A
A->B->C->A
而不是: B - > C > B
当前回答
我无意中发现了下面的算法,它似乎比Johnson的算法更有效(至少对于更大的图)。然而,与Tarjan的算法相比,我不确定它的性能如何。 此外,到目前为止,我只检查了三角形。如果感兴趣,请参阅千叶Norishige和西泽木高雄(http://dx.doi.org/10.1137/0214017)的“树状性和子图列表算法”
其他回答
我发现解决这个问题的最简单的选择是使用名为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']]
关于你关于排列周期的问题,请在这里阅读更多: https://www.codechef.com/problems/PCYCLE
您可以尝试以下代码(输入大小和数字number):
# include<cstdio>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
int num[1000];
int visited[1000]={0};
int vindex[2000];
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);
int t_visited=0;
int cycles=0;
int start=0, index;
while(t_visited < n)
{
for(int i=1;i<=n;i++)
{
if(visited[i]==0)
{
vindex[start]=i;
visited[i]=1;
t_visited++;
index=start;
break;
}
}
while(true)
{
index++;
vindex[index]=num[vindex[index-1]];
if(vindex[index]==vindex[start])
break;
visited[vindex[index]]=1;
t_visited++;
}
vindex[++index]=0;
start=index+1;
cycles++;
}
printf("%d\n",cycles,vindex[0]);
for(int i=0;i<(n+2*cycles);i++)
{
if(vindex[i]==0)
printf("\n");
else
printf("%d ",vindex[i]);
}
}
从节点X开始,检查所有子节点(如果无方向,父节点和子节点是等价的)。将这些子节点标记为X的子节点。对于任何这样的子节点A,标记它的子节点是A的子节点,X',其中X'标记为2步远。)如果您稍后点击X并将其标记为X的子节点”,这意味着X处于3节点周期中。回溯到它的父节点很容易(因为算法不支持这一点,所以你可以找到任何一个有X'的父节点)。
注意:如果图是无向的或者有任何双向边,这个算法会变得更复杂,假设你不想在一个周期内两次遍历同一条边。
http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf
我无意中发现了下面的算法,它似乎比Johnson的算法更有效(至少对于更大的图)。然而,与Tarjan的算法相比,我不确定它的性能如何。 此外,到目前为止,我只检查了三角形。如果感兴趣,请参阅千叶Norishige和西泽木高雄(http://dx.doi.org/10.1137/0214017)的“树状性和子图列表算法”