python算法分析与设计实验：宽度优先查找最短路径

python算法分析与设计实验：宽度优先查找最短路径

一、实验目的
1、熟悉图的两种常见表示方法，熟练掌握如何在计算机中存储图。了解图在计算机应用领域常见的应用场景。
2、熟练掌握图上宽度优先搜索算法及其算法复杂度分析，了解利用宽度优先搜索解决计算问题的建模过程。
3、熟练掌握图上深度优先搜索算法及其算法复杂度分析，了解深度优先算法的建模过程。

二、实验工具
Win10操作系统、python3.7编译环境、IDLE编译器

三、实验内容
给定无向图G=(V,E)，求从源点s到图中各个结点v∈V的最近距离。如图1所示，从源点s到结点d，c和z的最短距离均为2，而到结点f和v的最短距离则为3。

四、实验过程
图的存储依然采用邻接列表的方式存储，通过设计一个Graph类来表示图。Graph类中的成员变量为字典类型变量adj，用于存储图中每一个结点的邻边，成员函数add_edge(u,v)将两个结点u和v建立连接。设计一个BFSResult类来存储BFS的输出结果，一个字典类型的变量level来存储各层结点。level的key对应层的结点，level的value则是层的标号。使用一个字典变量parent来记录结点的父结点。
BFS的实现的函数bfs的输入参数为图G和初始结点s。bfs先初始化输出对象r。变量i索引参数，列表变量frontier存储当前层的结点，列表变量next存储frontier中的所有下一层的结点。
五、实验结果分析
按照BFS遍历该图的过程如下：首先，将初始结点s设置为第0层，然后找出结点s的所有邻居结点，其中还没有被遍历到的结点就将它们作为第1层的结点。再找出第1层的结点的邻居结点，所有未遍历的结点作为第2层的结点。依次遍历完图中所有结点，可得BFS的流程为：
·将源点置为第0层
·从源点s到该第i层每一个结点需要经过i条边
·第i层的每一个结点均来自前一层i-1。i为层数索引
BFS的实现函数bfs，对于frontier中每一个结点u，找出u的所有邻居节点v，如果邻居结点没有遍历，则该结点v是下一层的结点。处理完frontier中所有结点后，用next对它重置。通过判断frontier是否为空来作为循环是否继续的条件。用bfs对图1进行宽度优先搜索，frontier0的初始值等于{s}，下标0表示循环次数。第一次循环后，frontier1={a,x}。第二次循环后，frontier2={z,d,c}。第三次循环后，frontier3={f,v}。第四次循环时，frontier等于空，循环结束。

六、附：实验代码

class Graph:
    def __init__(self):
        self.adj={}
    def add_edge(self, u, v):
        if self.adj[u] is None:
            self.adj[u] = []
        self.adj[u].append(v)

class BFSResult:
    def __init__(self):
        self.level = {}
        self.parent = {}

def bfs(g,s):
    r = BFSResult()
    r.parent = {s:None}
    r.level = {s:0}
    i = 1
    frontier = [s]
    while frontier:
        next = []
        for u in frontier:
            for v in g.adj[u]:
                if v not in r.level:
                    r.level[v] = i
                    r.parent[v] = u
                    next.append(v)
        frontier = next
        i += 1
        
    return r


def find_shortest_path(result,v):
    source_vertex = [verterx for verterx, level in result.level.items() if level ==0]
    v_parent_list = []
    if v != source_vertex[0]:
        v_parent = result.parent[v]
        v_parent_list.append(v_parent)
        while v_parent != source_vertex[0] and v_parent != None:
            v_parent = result.parent[v_parent]
            v_parent_list.append(v_parent)
    return v_parent_list

if __name__ == "__main__":
    g = Graph()
    g.adj = { "s" : ["a","x"],
              "a" : ["z","s"],
              "d" : ["f","c","x"],
              "c" : ["x","d","f","v"],
              "v" : ["f","c"],
              "f" : ["c","d","v"],
              "x" : ["s","d","c"],
              "z" : []
              }
    bfs_result = bfs(g,'s')
    print(bfs_result.level)
    print(find_shortest_path(bfs_result,'f'))