Как обойти граф?

Question

[beduin01]

У меня есть граф вида https://jsfiddle.net/0gf3mj6L/
Мне нужно удалить все узлы и оставить только связь между Company 0 и Company 6. Чтобы получилось вот так:



Как это сделать? Может есть какие-то готовые библиотеки чтобы решение не писать самостоятельно?

Answer 1

[alexalexes]

Найдите путь по алгоритму Дейкстры между двумя интересуемыми вершинами.
Все вершины и дуги, которые не входят в этот путь - зачистить.

Answer 2

[Сергей П]

Если у вас граф ацикличный (ну то есть без циклов совсем), то вам подойдёт следующий алгоритм (назовём его "метод эррозии"):
1. Удаляем из графа все узлы (кроме заданных в условии), у которых только одна связь.
2. Повторяем П.1. пока есть что удалять.
3. PROFIT!!! У вас в графе остался только искомый путь.

Можно как предложили выше:
1. Начинаем от стартового узла А. Окрашиваем его цветом i=0.
2. Окрашиваем всех неокрашенных соседей узлов цвета i цветом i + 1, пока не покрасим целевой узел B (это теперь текущий узел x=B), тогда останавливаем раскраску.
3. От текущего узла x (покрашенного цветом i) переходим к его соседу с цветом i-1 запоминая значения x в списке L пока i>0.
4. PROFIT!!! У нас в L все узлы пути от B к A. Остальные узлы можно удалить из графа.