【3】数据结构与算法（Python实现）之图相关算法（图的深度优先遍历，广度优先遍历，Dijkstra算法求最短路，Floyd算法求最短路）

from queue import Queue

# 邻接矩阵存储
class Graph:
    def __init__(self, mat, unconn=0):
        # mat = [[*, *, *, *], [*, *, *, *], [*, *, *, *], [*, *, *, *]]
        vnum = len(mat)
        for x in mat:
            if len(x) != vnum:
                # 检查是否为方阵
                raise ValueError("mat不是邻接矩阵的格式")
        self._mat = [mat[i][:] for i in range(vnum)]  # 矩阵的拷贝
        self._unconn = unconn
        self._vnum = vnum

    def vertex_num(self):
        # 计算顶点个数
        return self._vnum

    def add_edge(self, vi, vj, val=1):
        # 加边
        self._mat[vi][vj] = val

    def get_edge(self, vi, vj):
        # 获取某两个点之间的边
        if self._mat[vi][vj] == 0:
            return 100            #  如果不存在边, 存一个很大的数, 因为我底下求最短路的边长最长也就8
        return self._mat[vi][vj]

    # 一个点到其他点之间的边
    @staticmethod
    def _out_edges(row, unconn):
        edges = []
        for i in range(len(row)):
            if row[i] != unconn:
                edges.append((i, row[i]))
        return edges   # 返回当前一个点到其他点的边
    def out_edges(self, vi):
        return self._out_edges(self._mat[vi], self._unconn)

# 邻接表存储
class GraphAL(Graph):
    # 直接将邻接矩阵转换为邻接表
    def __init__(self, mat=[], unconn=0):
        vnum = len(mat)
        for x in mat:
            if len(x) != vnum:  # 检查矩阵是否为方阵
                raise ValueError("输错了")
        self._mat = [Graph._out_edges(mat[i], unconn)
                     for i in range(vnum)]   # 查每个定点到其他点的边,构成邻接表
        self._vnum = vnum
        self._unconn = unconn
        # [
        #     [(2, 1), (3, 1)]   # 代表0能直接到2长度1, 到3长度1
        #     [(0, 1)]      # 代表1能直接到0长度1
        #     [(1, 1), (3, 1)]   # 代表2能直接到1长度1, 到3长度1
        #     [(1, 1)]      # 代表3能直接到1长度1
        # ]

    def add_vertex(self):
        # 增加节点
        self._mat.append([])
        self._vnum += 1
        return self._vnum - 1

    def add_edge(self, vi, vj, val=1):

        row = self._mat[vi]
        i = 0
        while i < len(row):
            if row[i][0] == vj:   # 修改mat[vi][vj]值
                self._mat[vi][i] = (vj, val)
                return
            if row[i][0] > vj:   # 原来没有到vj的边, 退出循环加边
                break
            i += 1
        self._mat[vi].insert(i, (vj, val))

    def get_edge(self, vi, vj):
        for i, val in self._mat[vi]:
            if i == vj:
                return val
        return self._unconn

    def out_edges(self, vi):
        return self._mat[vi]


# 深度优先遍历   这个是数据结构与算法给出的实例代码  我没怎么懂,自己写了一个DFS(下一个函数)
# def DFS1(graph, v0):
#     vnum = graph.vertex_num()  # 获取节点数
#     visited = [0]*vnum   # visited=0 代表都没有被访问
#     visited[v0] = 1  # 代表初始节点已经被访问
#     dfs_list = [v0]   # 遍历的序列放这里面
#     stack = []
#     stack.append((0, graph.out_edges(v0)))  # 获取与v0点连接的
#     while stack:
#         i, edges = stack.pop()
#         if i < len(edges):
#             v, e = edges[i]
#             stack.append((i+1, edges))
#             if visited[v] == 0:
#                 dfs_list.append(v)
#                 visited[v] = 1
#                 stack.append((0, graph.out_edges(v)))
#     return dfs_list

def DFS(graph, v0):
    # 自己实现的深度优先遍历
    vnum = graph.vertex_num()   # 获取当前的节点数
    visited = [0]*vnum    # visited=0  代表都没有被访问
    visited[v0] = 1
    dfs_list = [v0]
    stack = []
    member1 = graph.out_edges(v0)
    member1.reverse()
    for i in member1:
        stack.append(i)
    while stack:
        v, e = stack.pop()
        if visited[v] == 0:
            dfs_list.append(v)
            visited[v] = 1
            member = graph.out_edges(v)
            member.reverse()
            for e in member:
                stack.append(e)
    return dfs_list

def BFS(graph, v0):
    # 广度优先遍历
    vnum = graph.vertex_num()  # 获取当前的节点数
    visited = [0] * vnum  # visited=0  代表都没有被访问
    bfs_list = []
    que = Queue()
    que.put(v0)
    visited[v0[0]] = 1  # 当前出队的那个元素标记为访问
    while que.empty() == False:
        temp, v = que.get(block=False)   # 非阻塞获取
        bfs_list.append(temp)   # 将当前元素放在咱们等会输出的那个队列
        member = graph.out_edges(temp)   # 获取与当前点直接相连的点
        member.reverse()      # 逆转一下,这一步自己手动分析一下
        for (i, v) in member:
            if visited[i] == 0:
                que.put((i, v))
                visited[i] = 1
    return bfs_list


# dijkstra求最短路的算法
path = [0, 0, 0, 0, 0, 0, 0]  # 存每个节点当前路径的前驱
dist = [0, 0, 0, 0, 0, 0, 0]  # 存走到当前每个点的最短路径
visited = [0, 0, 0, 0, 0, 0, 0]  # 标志当前点是否被访问
def dijkstra(graph1, v0):
    vnum = graph1.vertex_num()
    # print(vnum)
    for i in range(vnum):
        dist[i] = graph1.get_edge(v0, i)
        visited[i] = 0  # 代表未被访问
        if graph1.get_edge(v0, i) < inf:
            path[i] = v0
        else:
            path[i] = -1
    visited[v0] = 1
    path[v0] = -1

    for i in range(vnum-1):
        min = inf
        # 这个循环每次从剩余顶点中选出一个顶点,通过这个顶点的路径是通往所有剩余顶点的路径中长度最短的
        for j in range(vnum):
            if visited[j] == 0 and dist[j] < min:
                u = j
                min = dist[j]
        visited[u] = 1  # 将选取的顶点加入到已确定的集合里

        for j in range(vnum):
            if visited[j] == 0 and dist[u] + graph1.get_edge(u, j) < dist[j]:
                dist[j] = dist[u] + graph1.get_edge(u, j)
                path[j] = u
    # dist[]数组存放着v点到其余顶点的最短路径, path[]数组存放v点到其余顶点的最短路径
def print_path(path, a):
    # 想看一下0 到 a 的最短路径   打印路径
    short_path = []
    while path[a] != -1:
        short_path.append(a)
        a = path[a]
    short_path.append(a)
    short_path.reverse()
    return short_path


# Floyd算法
def floyd(graph1, path):
    vnum = graph1.vertex_num()
    A = [[0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 0]]    # 等会存任意两点之间的最短的路径
    for i in range(vnum):
        for j in range(vnum):
            A[i][j] = graph1.get_edge(i, j)
            path[i][j] = -1      #  双重for循环是为了初始化
    for k in range(vnum):
        for i in range(vnum):
            for j in range(vnum):
                if A[i][j] > A[i][k] + A[k][j]:
                    A[i][j] = A[i][k] + A[k][j]
                    path[i][j] = k
    # A[0][4] 代表的是0到4的最短路径    A[i][j]代表i到j的最短路径
    return A, path
short_floyd_path = []
def print_floyd_path(u, v, path):

    if path[u][v] == -1:
        return
    short_floyd_path.append(path[u][v])
    # 这个路径打印出来不包括u, v,  我们最后输出的时候把u v记得***来
    mid = path[u][v]
    print_floyd_path(mid, v, path)  # 处理mid的后半段
    print_floyd_path(u, mid, path)  # 处理mid的前半段


if __name__ == '__main__':

    # 输入的邻接矩阵  无向图
    a = [[0, 1, 0, 0, 1, 0],
         [0, 0, 0, 0, 0, 0],
         [0, 0, 0, 1, 0, 1],
         [1, 1, 0, 0, 1, 0],
         [0, 0, 0, 0, 0, 1],
         [0, 0, 0, 0, 0, 0]]


    g = [[0, 0, 6, 3, 0, 0, 0],
         [11, 0, 4, 0, 0, 7, 0],
         [0, 3, 0, 0, 5, 0, 0],
         [0, 0, 0, 0, 5, 0, 0],
         [0, 0, 0, 0, 0, 0, 9],
         [0, 0, 0, 0, 0, 0, 10],
         [0, 0, 0, 0, 0, 0, 0]]


    # c邻接矩阵是等会求最短路径的图
    inf = float('inf')   # inf表示最大，代表没有边
    c = [[0, 4, 6, 6, inf, inf, inf],
         [inf, 0, 1, inf, 7, inf, inf],
         [inf, inf, 0, inf, 6, 4, inf],
         [inf, inf, 2, 0, inf, 5, inf],
         [inf, inf, inf, inf, 0, inf, 6],
         [inf, inf, inf, inf, 1, 0, 8],
         [inf, inf, inf, inf, inf, inf, 0]]


    # 建立大家执行代码之前，先根据邻接矩阵画出对应的图.
    graph = GraphAL(g)

    # dfs_list = DFS1(graph, 2)
    # print("深度优先遍历:", dfs_list)

    dfs_list1 = DFS(graph, 2)
    print("深度优先遍历:", dfs_list1)

    bfs_list1 = BFS(graph, (2, 0))
    print("广度优先遍历:", bfs_list1)

    graph1 = Graph(c)

    # dijkstra算法求最短路算法
    dijkstra(graph1, 0)    # 调用dijkstra算法   算出0到任意点的最短路径
    short_path = print_path(path, 4)    # 从0点开始,到6终结
    print("Dijlstra算法求得最短路径:", short_path)

    # floyd算法求最短路
    path = [[0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0]]
    u = 0; v = 4
    A, path = floyd(graph1, path)
    print_floyd_path(u, v, path)
    short_floyd_path.reverse()
    short_floyd_path.append(v)
    short_floyd_path.insert(u, 0)
    print("Floyd算法求得最短路径:", short_floyd_path)


# 输出结果:
# 深度优先遍历: [2, 1, 0, 3, 4, 6, 5]
# 广度优先遍历: [2, 1, 4, 0, 5, 6, 3]
# Dijlstra算法求得最短路径: [0, 1, 2, 5, 4]
# Floyd算法求得最短路径: [0, 1, 2, 5, 4]