무딘 그래프 만들기 및 QuickGraph에서 BFS를 사용하여 트래버스하기

Question

QuickGraph for C#을 사용하여 무 방향성 가중 그래프의 새 인스턴스를 만드는 방법을 알아 내려고하고 있습니다. 내 목표는 무작위 수의 노드로 채워진 무향 그래프를 만들고 무작위로 생성 된 시작 및 끝 노드를 사용하여 가장 짧은 경로가 폭 - 우선 검색 알고리즘을 사용하여 찾을 수 있도록하는 것입니다. 문서에는 그다지 많은 부분이 없기 때문에 누군가가 도움을 줄 수 있다면 감사 할 것입니다.

Answer 1

이 알고리즘에 대한 문서는 아직 없습니다. 하지만 다음으로 가장 좋은 것 (또는 더 좋은 것)이 있습니다 : 단위 테스트!

QuickGraph 소스를 다운로드하고 BreadthFirstAlgorithmSearchTest.BreadthFirstSearchAll()을 찾으면 테스트 프로젝트의 모든 방향 그래프에서 BFS를 실행하는 알고리즘의 사용 예가 표시됩니다.

Answer 2

리차드, QuickGraph는이 작업을 수행하지 않으며 구독 할 수있는 이벤트 만 제공합니다. 이러한 이벤트에 가입하면 그에 따라 대응할 수 있습니다.

1. InitializeVertex, 각 정점에 호출 : 깊이 우선 검색에 틀림없이 부족 QuickGraph 문서 (예, 난 당신이 DFS을 BFS를하고하지 않을 실현하지만, 이벤트에 가입하는 방법의 개념은 동일)에서 연산,
2. DiscoverVertex를 시작하기 전에, 정점이 처음
3. ExamineEdge 발생을 호출 할 때 호출 된 모든 아웃 에지 각각의 에지로 호출이 발견 된 후 각 정점의
4. TreeEdge, 검색 트리를 구성하는 모서리의 구성원이됩니다.
5. FinishVertex. 모든 바깥 쪽 가장자리가 검색 트리에 추가되고 인접한 모든 정점이 모두 발견 된 후에 (그러나 바깥 쪽 가장자리를 검사하기 전에) 정점에서 호출됩니다.

그런데 Reflector를 열고 QuickGraph.Algorithms.Observers를 살펴보십시오. 그리고 가장 짧은 경로 요구 사항은 BFS와는 다른 방법으로 더 쉬울 것입니다.