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

Question

you can see image to check nodes问题：通过使用 BFS 找到通过共同好友从 Sara 发送消息给 Uzma 的路径
此代码给出错误并且未显示路径。你能找出错误吗？
Note:neighbour 是给定节点

的好友

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

    ...

基于字典的有向图需要将两个节点都添加到图的节点中，并且仅将头添加到尾的邻接字典中（ tail 没有加入head 的邻接字典):

# 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 这个词，它明确了你需要的图的类型：一个 无向图.

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

can you please figure out error in my BFS code

python

breadth-first-search