欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

广度优先最短路径搜索

程序员文章站 2022-06-11 21:07:03
...

广度优先最短路径搜索

北航童咏昕教授算法设计与分析MOOC(慕课)广度优先学习记录
核心思想:处理某节点时,一次性发现其所有相邻节点,未处理节点加入队列等待
广度优先最短路径搜索
辅助dict:

  1. 使用color字典表示节点的状态
    White:白色节点表示尚未发现,发现后直接入队列
    Black:黑色节点表示已经被处理,无需再次入队列
    Gray:灰色节点表示已加入队列,无需再次入队列
  2. 使用pred字典存储某一节点的前驱节点(即由那个节点所发现)
  3. 使用dist字典记录某一节点到源点(起始搜索节点)的距离
    初始化结构:
    广度优先最短路径搜索
    使用networkx模块来绘制图结构
    networkx在2002年5月产生,是一个用Python语言开发的图论与复杂网络建模工具,内置了常用的图与复杂网络分析算法,可以方便的进行复杂网络数据分析、仿真建模等工作。
    networkx支持创建简单无向图、有向图和多重图;内置许多标准的图论算法,节点可为任意数据;支持任意的边值维度。
    广度优先最短路径搜索Python代码:
import networkx as nx
import matplotlib.pyplot as plt

class Breadth():
    
    def __init__(self,s):
        #构建图结构
        self.graph = {}
        self.graph["1"] = ["2","5"]
        self.graph["2"] = ["1","6"]
        self.graph["3"] = ["4","6","7"]
        self.graph["4"] = ["3","7","8"]
        self.graph["5"] = ["1"]
        self.graph["6"] = ["2","3","7"]
        self.graph["7"] = ["3","4","6","8"]
        self.graph["8"] = ["4","7"]
        #节点状态,未发现(白色)、加入队列待处理(灰色)、处理完出队列(黑色)
        self.color = {}
        #前驱节点
        self.pred = {}
        #节点距离源点s的距离
        self.dist = {}
        #初始化
        for i in range(len(self.graph)):
            self.color[str(i+1)] = "White"
            self.pred[str(i+1)] = "N"
            self.dist[str(i+1)] = "∞"
        #创建队列Q,用于处理节点
        self.Q = []
        #源点s
        self.s = s
        #发现源点,颜色变为灰色
        self.color[s] = "Gray"
        #距离源点为零
        self.dist[s] = 0
    
    def BFS(self):
        self.Q.append(self.s)
        #队列非空
        while self.Q:
            #首元素出队列
            u = self.Q.pop(0)
            #遍历此节点的相邻节点
            for v in self.graph[u]:
                #相邻节点的状态为白色则进行处理
                if self.color[v] == "White":
                    #将相邻节点状态由白色变为待处理的灰色
                    self.color[v] = "Gray"
                    #使用此节点到源点的距离加1作为相邻节点到源点的距离
                    self.dist[v] = self.dist[u] + 1
                    #保存此点为相邻节点的前驱节点
                    self.pred[v] = u
                    #将相邻节点作为待处理节点放入队列中
                    self.Q.append(v)
            #处理完成后将此节点的状态变为黑色
            self.color[u] = "Black"
    
    #展示图结构
    def showGraph(self):
        G = nx.Graph()
        nodes = ['1','2','3','4','5','6','7','8']
        G.add_nodes_from(nodes)
        ebunch = [('1','2'),('1','5'),('2','6'),('6','3'),('6','7'),
                  ('3','7'),('3','4'),('7','4'),('7','8'),('4','8')]
        G.add_edges_from(ebunch)
        nx.draw(G,pos=nx.spring_layout(G),with_labels=True,font_size=24,node_size=2640)
        plt.show()
    
    #从源点到指定节点的最短路径展示
    def showPath(self,appointNode):
        cur = appointNode
        #初始化路径为当前节点
        path = cur
        #循环遍历前驱节点
        while True:
            if cur == "N":
                break
            cur = bfsObj.pred[cur]
            if cur != "N":
                path = cur + "->" + path
        distValue = self.dist[appointNode]
        #返回最短路径和距离值
        return path,distValue

bfsObj = Breadth("2")
bfsObj.showGraph()
bfsObj.BFS()
print(bfsObj.showPath("7"))
相关标签: 算法