Алгоритм для нахождения избыточных краев в графике или дереве
Оператор запятой (,) возвращает правый боковой член. Здесь возвращаемое слагаемое является возвращаемым значением i=1, то есть 1. Затем это значение присваивается обратно i.
5 ответов
Вы хотите вычислить самый маленький график, который поддерживает достижимость вершины.
Это называют переходное сокращение из графика. Статья Википедии должна запустить Вас вниз правильная дорога.
Несколько способов напасть на это, но сначала Вы испытываете необходимость для определения проблемы немного более точно. Во-первых, график, который Вы имеете здесь, является нециклическим и направлен: это всегда будет верно?
Затем, необходимо определить то, что Вы подразумеваете под "избыточным краем". В этом случае Вы запускаете с графика, который имеет два пути a-> c: один через b и один прямой. От этого я вывожу, что "избыточным" Вы имеете в виду что-то вроде этого. Позвольте G =< V, E> быть графиком, с V набор вершины и E ⊆ V× V набор краев. Отчасти похоже на определение всех краев от v я к vj короче, чем самый длинный край как "избыточных". Таким образом, самая легкая вещь состояла бы в том, чтобы использовать поиск в глубину, перечислить пути, и когда Вы находите новый, это длиннее, сохраните его как лучшего кандидата.
я не могу вообразить то, что Вы хотите это для, все же. Можно ли сказать?
Подграф данного графика, который не содержит "избыточных краев", называют' связующее дерево ' того графика. Для любого данного графика несколько связующих деревьев возможны.
Так, для избавлений от избыточных краев, все, которое необходимо сделать, находка любое связующее дерево графика. Можно использовать любой поиск в глубину или поиск в ширину алгоритм и продолжить искать, пока Вы не посетили каждую вершину в графике.
Я думаю самый легкий способ сделать это, на самом деле вообразить, как это посмотрело бы в реальной работе, вообразить, есть ли у Вас соединения, Как
(A-> B) (B-> C) (A-> C), вообразите, ли расстояние между близкими графиками, равняется 1, таким образом
(A-> B) = 1, (B-> C) = 1, (A-> C) = 2.
, Таким образом, можно удалить соединение (A-> C).
, Другими словами, минимизировать.
Это - просто моя идея, как я думал бы об этом в запуске. Существуют различные статьи и источники в сети, можно посмотреть на них и пойти глубже.
Ресурсы, которые помогут Вам:
Алгоритм для Удаления Избыточных Краев в Двойном Графике Недвоичной структуры данных CSP
Графика и Основных Алгоритмов Графика
Google Books, При нахождении минимальных двух связанных Подграфов