해당 adjMat [i, j] = 1에 1을 가짐으로써 노드 간의 에지를 추적하는 그래프의 adjaceny 행렬을가집니다. 이 adjaceny 행렬을 통해 그래프에 존재하는 길이가 4 인 모든 닫힌 경로를 찾고 싶습니다. 누구든지 의사 코드를 제공 해줄 수 있습니까? 감사합니다그래프에서 닫힌 경로를 찾기위한 의사 코드
-1
A
답변
0
모든 노드에 깊이 제한 깊이 우선 탐색을 적용하고 DFS가 시작 노드를 찾은 노드를 기록합니다. 검색하려면 의사 코드 here : http://en.wikipedia.org/wiki/Depth-limited_search을 참조하십시오. 루프 시작 부분에
if(node' == node && node'.depth==4) memorize(node)
과 같은 것을 추가하기 만하면됩니다.
2
이것은 숙제처럼 들리므로 모든 것을 포기하지 않을 것입니다. 하지만 여기에 힌트가 있습니다. 길이 4의 사이클을 찾는 데 관심이 있기 때문에 인접 행렬의 4 번째 힘을 취하여 대각선을 따라 스캔하십시오. 임의의 엔트리 M [i, i]가 0이 아니면, 정점 i를 포함하는 사이클이있다.
1
아마이 (가 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
관련 문제
- 1. 최단 경로를 찾기위한 의사 코드
- 2. 닫힌 HTML 요소를 찾기위한 Firefox 부가 기능
- 3. 가장 긴 경로를 찾기위한 프로그램 만들기
- 4. 이 알고리즘의 의사 코드
- 5. 명령어 설명을위한 의사 코드
- 6. 구현 루프 의사 코드
- 7. 프로그래밍 의사 코드
- 8. FOR가있는 의사 코드
- 9. Fortune의 알고리즘 의사 코드
- 10. Mysql에 의사 코드 구조?
- 11. 의사 코드 - 공식 규칙
- 12. 의사 코드 이해 도움말
- 13. 의사 코드 작성 - 모범 사례?
- 14. 일부 MIT 코스웨어의 의사 코드
- 15. 하노이 변형 타워 의사 코드
- 16. minmax 알고리즘에 대한 의사 코드
- 17. LaTeX의 준 의사 코드 표시
- 18. 그래프에서 제약 조건을 만족하는 최단 경로를 찾는 방법
- 19. 무 방향성 그래프에서 두 노드 사이의 가능한 모든 경로를 찾으십시오.
- 20. 그래프에서 경로가 아닌 최단 경로
- 21. 그래프에서 전임자입니까?
- 22. XNA와 같은 리스닝 쓰레드를위한 디자인/의사 코드?
- 23. 종속성을 기반으로 주문을 얻기위한 의사 코드
- 24. 의사 코드 (NTRUEncrypt)에서 재귀 구현
- 25. 이 코드 세그먼트는 어떻게 의사 코드로 보입니까?
- 26. 분석 Big Oh 표기법 의사 코드
- 27. 그래프에서 가장 긴 원
- 28. 사용자 정의 속성을 사용하여 그래프에서 정점을 얻거나 찾기위한 안전한 방법 -> 좋은 프로그래밍 습관?
- 29. 완벽한 그래프에서 최대 도수를 찾는 것
- 30. 알 수없는 의사 요소 또는 의사 클래스 :
방법은 C#을, 자바와 의사가 될 수 있습니까? –