подключенные компоненты, используя первый поиск по ширине

Мне нужно найти связанные компоненты графа. У меня есть список соседей узлов:подключенные компоненты, используя первый поиск по ширине

neighbour_list = [[4], [2, 5], [1, 3, 8], [2, 14], [0, 9], [1], [10, 12], [13], [2, 14], [4, 10, 15], [6, 9], [17], [6], [7, 19, 20], [3, 8], [9, 21], [22], [11, 18], [17, 19], [13, 18, 26], [13, 26], [15, 27], [16, 23], [22, 24, 28], [23, 25, 29], [24], [19, 20, 30, 31], [21], [23, 29], [24, 28], [26, 31], [26, 30]]

Для примера узла 0 имеет соседа 4, узел 1 имеет соседей 2 и 5 и т.д ... То, что я хочу, чтобы найти список подключенных компонентов. Указать узел 0 имеет сосед 4, но сосед 4 также является соседом узла 9. Узел 9 также имеет номер 10 и 15 соседей. Таким образом, в списке будет что-то вроде

[4,10,15....] etc including following neihbours.

Метод, который я пытаюсь использовать, - это поиск по ширине. Я написал следующий алгоритм:

def bfs(neighbour_list, node): 

    label_list =[] 
    for sub_neighbour_list in neighbour_list: 

     label_list.append(node) 

     queue = [node] 

    while queue: 
     u = queue[0] 
     for sub_neighbour in neighbour_list[u]: 
      if sub_neighbour not in queue: 
      label_list[sub_neighbour] = 0 
      queue.append(sub_neighbour) 
      queue.pop(0) 

    print(label_list) 
    return (label_list)

ничего не происходит, когда я запускаю его. Что не так?

благодаря

источник

2014-10-01 Hannah

Отметьте три строки, следующие за оператором if, и все строки после первого «за» до, но не включая инструкцию «печать». – Marichyasana

@Marichyasana все еще ничего не делает – Hannah

Где определяется 'sub_neighbour_list'? – jedwards

насчет:

neighbour_list = [[4], [2, 5], [1, 3, 8], [2, 14], [0, 9], [1], [10, 12], [13], 
       [2, 14], [4, 10, 15], [6, 9], [17], [6], [7, 19, 20], [3, 8], 
       [9, 21], [22], [11, 18], [17, 19], [13, 18, 26], [13, 26], 
       [15, 27], [16, 23], [22, 24, 28], [23, 25, 29], [24], 
       [19, 20, 30, 31], [21], [23, 29], [24, 28], [26, 31], [26, 30]] 

def bfs(neighbour_list, root): 
    queue = [] 
    seen = set() 

    queue.append(root) 
    seen.add(root) 

    while queue: 
     cn = queue.pop(0) 
     print("Current node: %d" % cn) 
     for nn in neighbour_list[cn]: 
      if nn not in seen: 
       queue.append(nn) 
       seen.add(nn) 
       print(" Found %d" % nn) 

    return seen 

print bfs(neighbour_list, 0)

который выводит:

 
Current node: 0 
    Found 4 
Current node: 4 
    Found 9 
Current node: 9 
    Found 10 
    Found 15 
Current node: 10 
    Found 6 
Current node: 15 
    Found 21 
Current node: 6 
    Found 12 
Current node: 21 
    Found 27 
Current node: 12 
Current node: 27 
set([0, 4, 6, 9, 10, 12, 15, 21, 27])

Обратите внимание, что set не упорядочена. Таким образом, результат этой функции вернет все узлы, достижимые на root, но не в каком-либо порядке, когда алгоритм достиг этого. Если вы этого хотите, вы можете легко изменить seen как список.

источник

2014-10-02 00:10:21 jedwards

, что такое defference betwwen .append и .add? @jedwards вы добавляете список, но добавляете в dictionnary? – Hannah

Вы '.append()' в список и '.add()' в набор. Набор представляет собой неупорядоченную коллекцию, тогда как список упорядочен. –

и в чем разница между queue.pop (0) и queue [0], не имеют ли они того же результата? @Tom Dalton – Hannah

В дополнение к ответу на jedwards я бы предложил использовать структуру данных deque from collections import deque, а затем queue = deque() и queue.popleft(). Это должно ускорить работу.

источник

2017-05-04 09:09:05 Ale

подключенные компоненты, используя первый поиск по ширине

ответ

Смежные вопросы