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

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

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

Спецификация графика:

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

c# graphing quickgraph
person Green Baron    schedule 16.12.2014    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

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

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

person Erti-Chris Eelmaa    schedule 16.12.2014