Breadth First search with adjacency matrix

Question

So I've created a bfs traversal which consumes a graph and a starting point. It consumes a graph represented in a adjacent list but how would I change it to consume a adjacency matrix. I just need somewhere to start

Adjacency List:

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

Adjacency Matrix:

[ [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

Answer 1

I had a similar problem once, and I think it is simplest to just convert your matrix to the adjacency list i.e.:

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

You can then use your canonical (and debugged) Breadth First Search algorithm with the returned list of nodes. I hope that helps

Answer 2

I am offering this submission in case it helps anyone who comes across this question. While the algorithm for BFS is well-known, I have found it surprisingly difficult to find a Python implementation of either BFS or DFS on an adjacency matrix (NOT list) as you asked in your question.

The below implementation works with your matrix as shown. It runs iteratively, and since it visits every cell in your matrix once, it runs in time O(n*m), where n = matrix.length and m = matrix[0].length. On a square matrix, it would be time 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

It returns the following (which is a list of tuples containing the row and column co-ordinates of the cells in your matrix labeled 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)]

You can easily adjust this approach to perform depth-first search as well by modifying nodes.pop(0) to nodes.pop().