Мне дается сеть, определенная узлами и ссылками. Я должен искать все петли в сети. Координаты для узлов отсутствуют.Алгоритм - поиск всех петель в топологии сети
Существует ли какой-либо существующий алгоритм или библиотека, которые могут это сделать. Или вы можете дать мне некоторое представление о том, как я могу подойти к этой проблеме? Я программирую в .NET.
я нарисовать диаграмму, чтобы проиллюстрировать то, что мне нужно here
Distance vector Routing. Попытка
Этот алгоритм находит кратчайший путь ко всем другим узлам в сети от узла.
В предположении, что ваши ребра не направлены и что между узлами имеется максимум одно ребро, тогда базовое связующее дерево шириной http://en.wikipedia.org/wiki/Spanning_tree будет охватывать все узлы и указывать, где циклы (что, как я думаю, вы подразумеваете под петли). Мы используем этот алгоритм для нахождения «колец» в химических структурах. Есть множество реализаций на многих языках - вот учебник с апплетом (http://oneweb.utc.edu/~Christopher-Mawata/petersen2/lesson20.htm)
петли называется cycles и this answer имеет много информаций для вас.
Это ориентированный граф? – elhoim
Не направленный граф. –