Как бороться с параллельными ребрами между двумя вершинами при обнаружении цикла, используя BFS в неориентированном графе? - PullRequest
Новая
       78

Как бороться с параллельными ребрами между двумя вершинами при обнаружении цикла, используя BFS в неориентированном графе?

0 голосов
/ 14 октября 2019

Я новичок в программировании и изучении алгоритмов и изучал BFS, когда прочитал, что BFS можно использовать для обнаружения цикла. Я попытался реализовать то же самое на неориентированном графе G с представлением списка смежности. Я сделал следующее:

• Выполните простой обход BFS с использованием очереди, сохраняя при этом родительский узел узлов, поставленных в очередь в очереди.

• Если я сталкиваюсь с узломu, у которого есть сосед v, такой, что v уже посещен, но v не является родителем u, тогда это означает, что в графе есть цикл.

Псевдокод : 

#adjList is the adjacency list given as a dictionary
#myQueue is a double-sided queue containing node and its parent node ([Node, parNode])
#visited is a set containing visited nodes

while(myQueue):
    currNode, parNode = myQueue.pop() #dequeue operation
    visited.add(currNode) #Marking currNode as visited
    for childNode in adjList[currNode]: #Traversing through all children of currNode
        if currNode not in visited:
            myQueue.appendleft([childNode, currNode]) #Enqueue operation
        else:
            if childNode!=parNode: #Main logic for cycle detection
                print('CYCLE DETECTED')
                break

Вышеупомянутый подход работает, за исключением случаев, когда у меня есть более 1 ребра между 2 вершинами, например, в следующем случае у нас есть 2 ребра между вершинами 0 и 1:

Graph containing cycle

Список смежности на приведенном выше графике: adjList = {0:[1, 1, 2], 1:[0, 0], 2:[0]}. Здесь мы можем ясно видеть, что граф содержит цикл (в представлении списка смежности это подтверждается тем фактом, что 1 дважды появляется в списке смежности 0 и 0 дважды появляется в списке смежности 1) но алгоритм выше не может обнаружить то же самое, потому что, когда BFS достигнет вершины 1, вершина 0 уже посещена, но вершина 0 также является родителем вершины 1, поэтому этот цикл останется незамеченным.

У меня вопрос, как я могу изменить приведенный выше алгоритм для обнаружения таких случаев?

Редактировать : Я пробовал ту же логику и на ориентированных графах, и я столкнулся с аналогичной проблемойто есть, когда у меня есть направленный край от вершины 0 до вершины 1 и другой направленный край от вершины 1 до вершины 0

1 Ответ

0 голосов
/ 15 октября 2019

Я получил ответ на свой вопрос на форуме по информатике Stack Exchange. Вот ссылка на ответ, и я копирую то же самое оттуда, как отправлено @ Саймон Вебер

Если дело поступает туда, где вы видите делоесли узел уже посещен, но он является родителем вашего текущего узла, вам просто нужно проверить, есть ли между ними двойное ребро. Как это сделать, зависит от вашей структуры данных, но если ваш список смежности отсортирован, это будет равносильно поиску границы и проверке того, как часто он там присутствует.

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

Для ориентированных графов вы можете просто полностью избавиться от «родительской проверки», поскольку единственный случай, когда приходит случай, когда у вас есть два ребраот u до v и наоборот.

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

...