Как узнать, есть ли связь между двумя произвольными вершинами в графе направлений?

Question

Я хотел бы знать, какие классы и функции в библиотеке Quickgraph (C#) мне следует использовать, чтобы выяснить, существует ли связь между двумя произвольными вершинами в графе направленности?

Я новичок в программировании, особенно в программировании алгоритмов, поэтому я прошу вас, можете ли вы предоставить мне пример кода для упомянутой проблемы, в основном потому, что в библиотеке Quickgraph нет много учебных пособий для начинающих.

График спецификации:

• направленный
• Не взвешенный (расстояние не важно, просто связь между вершинами / ребрами)
• График является динамическим, поэтому вершины / ребра можно добавлять / удалять или редактировать.

Answer 1

Хм, я не проверял это, но основные DFS/BFS должны сделать так:

var tryGetPaths = _graph.TreeBreadthFirstSearch(__source__);
IEnumerable<Edge<YourItemType>> path;
if (tryGetPaths(__target__, out path))
{
    // we have connectivity!
}

Тот проверяет, есть ли какая-либо связь от источника до цели. Вы можете запустить эту проверку и наоборот.