Поиск в ширину с матрицей смежности

Итак, я создал обход BFS, который использует график и начальную точку. Он использует граф, представленный в соседнем списке, но как бы я изменил его, чтобы использовать матрицу смежности. Мне просто нужно с чего-то начать

Список смежности:

{0:[1,2,3],1:[0,2,3],2:[0,1,4],3:[0,1],4:[2]}

Матрица смежности:

[ [0,1,1,1,0], 
  [1,0,1,1,0], 
  [1,1,0,0,1], 
  [1,1,0,0,0], 
  [0,0,1,0,0] ]

def bfs(graph, v):
  all = []
  Q = []
  Q.append(v)
  while Q != []:
    v = Q.pop(0)
    all.append(v)
    for n in graph[v]:
      if n not in Q and\
      n not in all:
      Q.append(n)
  return all

python adjacency-list breadth-first-search adjacency-matrix
person Noah Trotman    schedule 12.04.2017    source источник
comment
Посмотрите на часть, где вы используете представление списка смежности. Вы перебираете соседей узла. Выясните, как перебирать соседей узла с помощью матрицы смежности.   -  person user2357112 supports Monica    schedule 12.04.2017

Ответы (2)


arrow_upward
2
arrow_downward

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

def matrix_to_list(matrix):
    graph = {}
    for i, node in enumerate(matrix):
        adj = []
        for j, connected in enumerate(node):
            if connected:
                adj.append(j)
        graph[i] = adj
    return graph

Затем вы можете использовать свой канонический (и отлаженный) алгоритм поиска в ширину с возвращенным списком узлов. Надеюсь, это поможет

person c-wilson    schedule 12.04.2017

arrow_upward
0
arrow_downward

Я предлагаю это представление на случай, если оно поможет любому, кто сталкивается с этим вопросом. Хотя алгоритм для BFS хорошо известен, мне было удивительно сложно найти реализацию Python для BFS или DFS в матрице смежности (НЕ список), как вы задали в своем вопросе.

Приведенная ниже реализация работает с вашей матрицей, как показано. Он выполняется итеративно, и поскольку он посещает каждую ячейку в вашей матрице один раз, он выполняется за время O(n*m), где n = matrix.length и m = matrix[0].length. В квадратной матрице это будет время O (n ^ 2).

def bfs(matrix, row, col, visited):
    nodes = [(row, col)]
    while nodes:
        row, col = nodes.pop(0)
        # the below conditional ensures that our algorithm 
        #stays within the bounds of our matrix.
        if row >= len(matrix) or col >= len(matrix[0]) or row < 0 or col < 0:
            continue
        if (row, col) not in visited:
            if matrix[row][col] == 1:
                visited.append((row, col))
                nodes.append((row+1, col))
                nodes.append((row, col+1))
                nodes.append((row-1, col))
                nodes.append((row, col-1))

def bfs_wrapper(matrix):
    visited = []
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if (i,j) not in visited:
                bfs(matrix, i, j, visited)
            
    return visited

Он возвращает следующее (это список кортежей, содержащих координаты строк и столбцов ячеек в вашей матрице с пометкой 1):

[(0, 1), (0, 2), (1, 2), (0, 3), (1, 3), (1, 0), (2, 0), (3, 0), (2, 1), (3, 1), (2, 4), (4, 2)]

Вы можете легко настроить этот подход для выполнения поиска в глубину, изменив nodes.pop(0) на nodes.pop().

person Daniel    schedule 11.12.2020