최적 알고리즘

Question

이의 예를 들어이 그래프를 보자 :

을 지금 (이 전 정점 3에서 시작하여 정점 7 깊이 우선 탐색을 찾으려하고있어 가정 해 봅시다 구현에 따라) 먼저 어린이를 살펴볼 것입니다. 이제 예제에서, 인수를 위해서, 저는 꼭지점 2에서 시작하여 꼭지점 4와 꼭지점 2로 이동하여 꼭지점으로 돌아가서 꼭지점 7로 간다. 문제는 해결되었다.

내가 원하는 것 : 나는 x에서 y까지 (eg 3에서 7 : 3,1,4,7 - 3,5,7 - 3까지) 가능한 모든 경로를 얻고 싶습니다. 4,7-3,5,6,9,7). Depth first search에서 얻지 못하는 것.

제안하는 알고리즘은 무엇입니까?

감사합니다.

Answer 1

수정 된 BFS 알고리즘 (http://en.wikipedia.org/wiki/Breadth-first_search)을 사용해야합니다. 각 버텍스에서이 버텍스로 이웃하는 네이버 목록을 저장해야합니다 (이전 버젼).

이 모든 경로를 찾으려면 엔드 노드에서 시작하여 이전 정점이 1 개 이상인 모든 정점에서 경로를 분기하고 각 정점의 선행자가 만든 경로로 이동해야합니다. 가지고있는 모든 가지로 노드를 시작하십시오.

EDIT : BFS 대신 DSF 알고리즘을 사용하고 같은 방법으로 수정할 수 있습니다.