재귀 역 추적을 사용하여 방향 그래프에서주기를 찾는 중입니다. 이것에 대한 제안 의사가 여기 , 여기있는이 :
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)
이 알고리즘은와 비교할 때 가장 효율적인 알고리즘은 아니지만 Tarjans algorithm이해하기에는 충분히 간단합니다. 현재이 코드에는 감지 된 횟수주기 수가 없습니다.
나는 이것을 자바로 구현했다.
//this is the main method that calls the helper DFS which runs on each node
public int allCyclesDirectedmain(){
//this initializes all vertices
clearAll();
int[] count = new int[1];
for (Vertex v: vertexMap.values()){
//System.out.println(v.name);
//clearAll();
dfs(v,v,count);
}
return count[0];
}
//start and v are same when the method first fires.
public void dfs(Vertex start, Vertex v,int[] count){
if (v.isVisited){
if (start==v){
//found a path
count[0]++;
}
return ;
}
v.setVisited(true);
for (Edge e : v.adj){
Vertex next = e.target;
dfs(start,next,count);
}
v.setVisited(false);
}
다음 모서리가있는 그래프의 경우 :
(1 2),(2 3),(3 1),(2 5),(5 6),(6 2)-출력으로 6주기를 얻습니다.
(1 2),(2 3),(3 4),(4,1),(2 5),(5 6),(6 2) -출력으로 7주기를 얻습니다.
내 현재 코드가 이미 이전에 감지 된주기의 일부인 각 정점에 대해주기 감지를 수행하는 것을 볼 수 있습니다 (예 : 3 개의 노드가있는주기는 각 개별 노드에 대해 3 개의주기를 제공하지만 이것이 하나 여야 함). 여기에 무엇이 잘못되고 몇 가지 수정 사항에 대한 몇 가지 팁이 필요합니다.
의 경우 (1 2),(2 3),(3 1)다음을 호출합니다.
dfs(vertex1, vertex1, count), 당신에게주기를 제공합니다 1 -> 2 -> 3 -> 1.dfs(vertex2, vertex2, count), 당신에게주기를 제공합니다 2 -> 3 -> 1 -> 2.dfs(vertex3, vertex3, count), 당신에게주기를 제공합니다 3 -> 1 -> 2 -> 3.그래서 당신은 같은주기를 여러 번 세고 있습니다.
내가 생각할 수있는 가장 간단한 수정은 단순히 dfs호출 후 방문 플래그를 설정하는 것입니다 .
public int allCyclesDirectedmain(){
clearAll();
int[] count = new int[1];
for (Vertex v: vertexMap.values()){
dfs(v,v,count);
v.setVisited(true); // <---
}
return count[0];
}
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다