그래프에서 닫힌 경로를 찾기위한 의사 코드

Question

해당 adjMat [i, j] = 1에 1을 가짐으로써 노드 간의 에지를 추적하는 그래프의 adjaceny 행렬을가집니다. 이 adjaceny 행렬을 통해 그래프에 존재하는 길이가 4 인 모든 닫힌 경로를 찾고 싶습니다. 누구든지 의사 코드를 제공 해줄 수 있습니까? 감사합니다

Answer 1

모든 노드에 깊이 제한 깊이 우선 탐색을 적용하고 DFS가 시작 노드를 찾은 노드를 기록합니다. 검색하려면 의사 코드 here : http://en.wikipedia.org/wiki/Depth-limited_search을 참조하십시오. 루프 시작 부분에

if(node' == node && node'.depth==4) memorize(node) 

과 같은 것을 추가하기 만하면됩니다.

Answer 2

이것은 숙제처럼 들리므로 모든 것을 포기하지 않을 것입니다. 하지만 여기에 힌트가 있습니다. 길이 4의 사이클을 찾는 데 관심이 있기 때문에 인접 행렬의 4 번째 힘을 취하여 대각선을 따라 스캔하십시오. 임의의 엔트리 M [i, i]가 0이 아니면, 정점 i를 포함하는 사이클이있다.

Answer 3

아마이 (가 O(n^4)있어)을 계산하기위한 최적의 방법은 아니지만, 아주 간단한 방법은 모든 정점

a, b, c, d such that b > a, c > b, d > c 

그런 다음 다음을 확인 사이클의 각을 확인할 수 있습니다를 스캔한다 :

 
1. ([a,b] && [b,c] && [c,d] && [d,a]) 
2. ([a,b] && [b,d] && [d,c] && [c,a]) 
3. ([a,d] && [d,b] && [b,c] && [c,a]) 

1:   2:  3: 
A---B  A---B  A B 
| |  \/ |\ /| 
| |  X  | X | 
| |  /\  |/ \| 
D---C  D---C  C D 

당신은 기본적으로 그들이 사이클을 형성 할 수있는 3 가지 방법에 대한 정점의 모든 명령 세트 (A, B, C, D)을 확인하고 있습니다.

그래서 의사 코드는 다음과 같습니다

for a = 0 to <lastVertex> 
for b = a + 1 to <lastVertex> 
    for c = b + 1 to <lastVertex> 
    for d = c + 1 to <lastVertex> 

    if(IsCycle(a,b,c,d)) AddToList([a,b,c,d]) 
    if(IsCycle(a,b,d,c)) AddToList([a,b,d,c]) 
    if(IsCycle(a,c,b,d)) AddToList([a,c,b,d]) 

    next d 
    next c 
next b  
next a