你能找出我BFS代码中的错误吗

Question

you can see image to check nodes问题：通过使用BFS，通过使用共同的朋友找到从Sara向Uzma发送消息的路径
这段代码给出了错误，没有显示路径。你能找出错误吗？
注意：邻居是给定节点的朋友

import collections

class Node():
    #dictionary is use to make graph
    graph={} 
    def add_edge(self,node,neighbour):
        if node not in self.graph.keys():
            self.graph[node]=[neighbour]
        else:
            self.graph[node].append(neighbour)

    def show_graph(self):
        print(self.graph)

    def show_neigh(self,node):
        print(self.graph[node])

    def BFS(self,initial,final):
        visited,queue=set(), collections.deque([initial])
        visited.add(initial)
        while queue:
            vertex=queue.popleft()
            for adj in self.graph[vertex]:
                if adj == final:
                    visited.add(adj)
                    print("Message sent Successfully !",visited)
                    break
                if adj not in visited:
                    visited.add(adj)
                    queue.append(adj)

g=Node()
g.add_edge("Amina","Sara")
g.add_edge("Amina","Riaz")
g.add_edge("Riaz","Ali")
g.add_edge("Riaz","Ahmed")
g.add_edge("Ahmed","Ahsan")
g.add_edge("Ahmed","Amina")
g.add_edge("Rida","Taha")
g.add_edge("Rida","Hassan")
g.add_edge("Uzma","Taha")
g.add_edge("Uzma","Ahsan")

g.show_graph()
g.BFS("Sara","Uzma")

Answer 1

Sara永远不会添加到图的节点：它只添加到Anima的邻居。没有从Sara到Uzma的路径，因为Sara不在图的节点中。add_edge不会为neighbour创建节点Sara永远不是node，它总是（曾经）是neighbour

tl；dr：我建议您对图形的顶点和顶点的相邻节点使用字典

• 基于字典的无向图要求将两个节点都添加到图的节点和相应的邻接字典中：

  # undirected graph
  class Graph():
      def __init__(self):
          self.nodes = {}
  
      def add_edge(self, u, v, weight=1):
          if not u in self.nodes:
              self.nodes[u] = {}
          if not v in self.nodes:
              self.nodes[v] = {}
          self.nodes[u][v] = weight
          self.nodes[v][u] = weight # missing in the directed graph
  
      ...
  

• 基于字典的有向图要求将两个节点都添加到图的节点，并且头部仅添加到尾部的邻接字典（尾部不添加到头部的邻接字典）：

  # directed graph
  class Graph():
      def __init__(self):
          self.nodes = {}
  
      def add_arrow(self, u, v, weight=1):
          if not u in self.nodes:
              self.nodes[u] = {}
          if not v in self.nodes:
              self.nodes[v] = {}
          self.nodes[u][v] = weight
  
      ...
  

最后，阅读作业的文本（？），我们会看到单词mutual，它明确了您需要的图形类型：无向图