Создание неориентированного графа и его обход с помощью BFS в QuickGraph

Question

Я пытаюсь выяснить, как создать новый экземпляр неориентированного взвешенного графа, используя QuickGraph для C #. Моя цель - создать неориентированный взвешенный граф, заполненный случайным числом узлов и случайно сгенерированными начальными и конечными узлами, кратчайший путь которых можно найти с помощью алгоритма поиска в ширину. В документации немногое, так что если кто-нибудь сможет оказать любую помощь, которая будет признательна.

Answer 1

Ричард, QuickGraph не делает ничего для вас, он только делает доступными события, на которые вы можете подписаться. Подписавшись на эти события, вы можете ответить соответствующим образом. Из общепризнанного отсутствия документации QuickGraph по поиску в глубину (да, я понимаю, что вы делаете BFS, а не DFS, но концепция подписки на события одинакова):

1. InitializeVertex, вызываемый в каждой вершине перед началом вычисления,
2. DiscoverVertex, вызывается при первом обнаружении вершины,
3. ExamineEdge, вызывается на каждом выходе каждой вершины после ее обнаружения,
4. TreeEdge, вызывается для каждого ребра, когда он становится членом ребер, образующих дерево поиска.
5. FinishVertex, вызываемый в вершине после того, как все ее внешние ребра были добавлены в дерево поиска и были обнаружены все смежные вершины (но до того, как были проверены их внешние ребра).

Кстати, откройте Reflector и взгляните на QuickGraph.Algorithms.Observers. И ваше требование кратчайшего пути будет проще с другим методом, чем BFS.

Answer 2

Для этого алгоритма еще нет документации; но есть следующая лучшая вещь (или, возможно, даже лучшая вещь): юнит тест!

Если вы загрузите источники QuickGraph и найдете BreadthFirstAlgorithmSearchTest.BreadthFirstSearchAll (), вы увидите пример использования алгоритма, который запускает BFS на всех ориентированных графах в тестовом проекте.