Поиск обхвата с помощью BFS для орграфа

Question

Поэтому у меня возникли некоторые проблемы с поиском обхват для следующего Digraph.

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

Любая помощь в этом отношении будет принята с благодарностью.Спасибо.

Answer 1

Во-первых, на графике нет обхвата или круга.Во-вторых, BFS не может использоваться для поиска круга в графе.

Если вы хотите найти обхват, вот способ:

(в ориентированном графике) 1. Использование DFS для поиска окружностей.

Для каждого круга удалите одно ребро из одной вершины U в другую вершину V.

Вычислите кратчайший путь между U и V, используя dijkstra или floyd.

Добавление удаленного ребра в кратчайший путь.Таким образом, получим длину окружностей.

Найдите самую короткую.