Может ли кто-нибудь предоставить шаг за шагом псевдокод с помощью BFS для поиска цикла в направленном/неориентированном графике?Обнаружение цикла BFS
Может ли он получить сложность O (| V | + | E |)?
Я видел только реализацию DFS до сих пор.
Вы можете взять нерекурсивный алгоритм DFS, где вы заменяете стек для узлов очередью, чтобы получить алгоритм BFS. Это просто:
q <- new queue // for DFS you use just a stack
append the start node of n in q
while q is not empty do
n <- remove first element of q
if n is visited
output 'Hurray, I found a cycle'
mark n as visited
for each edge (n, m) in E do
append m to q
Поскольку BFS посещает каждый узел и каждое ребро только один раз, у вас есть сложности O (| V | + | E |).
Что такое нерекурсивная DFS? Не могли бы вы предоставить псевдокод? Я попытался реализовать, но не смог заставить его работать. –
Я добавил алгоритм как псевдокод. – clemens
спасибо. Нужно ли нам использовать очередь? как вы печатаете? –
Я нахожу алгоритм BFS идеальным для этого. Сложность времени такая же.
Вы хотите что-то вроде этого (отредактированный из Википедии):
Cycle-With-Breadth-First-Search(Graph g, Vertex root):
create empty set S
create empty queue Q
root.parent = null
Q.enqueueEdges(root)
while Q is not empty:
current = Q.dequeue()
for each node n that is adjacent to current:
if n is not in S:
add n to S
n.parent = current
Q.enqueue(n)
else //We found a cycle
n.parent = current
return n and current
Я добавил только еще свой блок цикла обнаружения цикла и удалить оригинал, если достигли целевого блока для обнаружения цели. В общем, это тот же алгоритм.
Чтобы найти точный цикл, вам нужно будет найти общего предка для n и current. Самый низкий из них доступен в O (n) времени. Чем известен цикл. от предка до n и тока. ток и n связаны.
Для получения дополнительной информации о циклах и BFS читать эту ссылку https://stackoverflow.com/a/4464388/6782134
Почему вы хотите использовать BFS? Тебе обязательно ? Если нет, прочитайте это, вы можете использовать DFS: http://stackoverflow.com/questions/2869647/why-dfs-and-not-bfs-for-finding-cycle-in-graphs – kazu
@kazu Я хочу посмотрите, как это реализовано, потому что моя реализация запутана. –
Вам просто нужно знать, существует ли цикл или вам нужно извлечь конкретный круг? – Codor