时间戳

首页 > 解决方案 > 你能找出我的 BFS 代码中的错误吗

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

问题描述

您可以查看图像以检查节点问题：通过使用 BFS 查找从 Sara 发送到 Uzma 的消息的路径，使用共同的朋友
此代码给出错误并且不显示路径。你能找出错误吗？
注意：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")

标签： pythonbreadth-first-search

解决方案

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

    ...

最后，阅读您的作业文本（？），我们看到了“相互”这个词，它明确了您需要的图类型：无向图。

推荐阅读