How to solve the BFS algorithm with two different lists-CodePudding

This is a BFS algorithm. The folowing code of BFS algorithm is given but the list of vertexes is a dictionary while I have two different lists, one for the vertexes and one for the matrice (the 1 number in the matrice represent the edges that bound two vertexes at given position, if a 0 is present it means that these two vertexes are not bound or simply it's the same vertex so it can't be bound to itself)

I don't know how to apply the first algorithm in a smart way with my example, it doesn't remove the elements in the Q list (And yet I used Q.pop(0)) for removing the first Q element at every iteration.

First algorithm (not from me)

 graph = {
  'A' : ['B','C'],
  'B' : ['D', 'E'],
  'C' : ['F'],
  'D' : [],
  'E' : ['F'],
  'F' : []
}

visited = [] # List to keep track of visited nodes.
queue = []     #Initialize a queue

def bfs(visited, graph, node):
  visited.append(node)
  queue.append(node)

  while queue:
    s = queue.pop(0) 
    print (s, end = " ") 

    for neighbour in graph[s]:
      if neighbour not in visited:
        visited.append(neighbour)
        queue.append(neighbour)

# Driver Code
bfs(visited, graph, 'A')

My algorithm with my example of two separated lists (one for the vertexes, one for the matrice) :

V = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
M = [0,1,0,0,0,0,0],[1,0,1,1,0,0,0],[0,1,0,1,0,0,0],[0,1,1,0,1,0,0],[0,0,0,1,0,1,0],[0,0,0,0,1,0,1],[0,0,0,0,0,1,0]
Q = []
visited = []
E = []

def BFS(V,M): 

    Q.append('A')
    visited.append('A')

    while Q: 
        s = Q.pop(0) 
        

    for a,b in enumerate(M): 
        for i,j in enumerate(b): 
            if j == 1 and V[i] not in visited: 
            
                Q.append(V[i]) 
                visited.append(V[i])
                
            if b.count(1) > 2 and V[i] != V[i]: 
                E.append(V[i])
                Q.extend(E)
        print(Q) 
         
            
                 
                        
  
print(BFS(V,M))

CodePudding user response：

Try this: There are inline comments that explain the changes I made.

def BFS(V,M):
    Q.append('A')
    visited.append('A')
    while Q:
        s = Q.pop(0)  
        print(s, end=" ")
        chosen = M[V.index(s)]  # select the correct row according 
                                # to the index of `s` in `V`

        for a,b in enumerate(chosen):  # remove inner loop
            if b == 1 and V[a] not in visited and V[a] != s: # check visited
                Q.append(V[a])           # extend Q 
                visited.append(V[a])     # extend visited

BFS(V,M)