图的生成树算法

代码来自《数据结构与算法Python语言实现》裘宗燕著

# 图的生成树#----------图的邻接矩阵实现--------------------class Graph:    def __init__(self,mat,unconn = 0):        # 顶点个数        vnum = len(mat)        # 检查是否为方阵        for x in mat:            if len(x) != vnum:                raise ValueError("Argument for 'Graph'.")                # 拷贝        self._mat = [mat[i][:] for i in range(vnum)]        self._unconn = unconn        self._vnum = vnum    # 返回顶点个数    def vertex_num(self):        return self._vnum    # 验证序号v是否有效    def _invalid(self,v):        return 0>v or v>=self._vnum                        # 添加顶点    def add_vertex(self):        raise ValueError("Adj-Matrix does not support 'add_vertex'.")    # 添加边，即添加两个点之间的关联线段    def add_edge(self,vi,vj,val=1):        # 先检查vi和vj是否有效        if self._invalid(vi) or self._invalid(vj):            raise ValueError(str(vi) + 'or' + str(vj) + 'is not a valid vertex.')        # 为线段附加权重        self._mat[vi][vj] = val    # 获取边的权重    def get_edge(self,vi,vj):        if self._invalid(vi) or self._invalid(vj):            raise ValueError(str(vi) + 'or' + str(vj) + 'is not valid vertex.')        return self._mat[vi][vj]    # 获取指定结点的所有相连边    def out_edges(self,vi):        if self._invalid(vi):            raise ValueError(str(vi) + 'is not a valid vertex.')        return self._out_edges(self._mat[vi],self._unconn)        @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 __str__(self):        return "[\n" + ".\n".join(map(str,self._mat)) + "\n]" + "\nUnconnected:" + str(self._unconn)#----------图的邻接矩阵实现--------------------#----------图的压缩邻接矩阵实现-----------------class GraphAL(Graph):    # GraphAL继承自Graph            def __init__(self,mat = [],unconn = 0):        vnum = len(mat)        # 检查是否为方阵        for x in mat:            if len(x) != vnum:                raise ValueError("Argument for 'Graph'.")        # 只复制带有权重的边        self._mat = [Graph._out_edges(mat[i],unconn) for i in range(vnum)]        self._vnum = vnum        self._unconn = unconn    # 添加一个顶点    def add_vertex(self):        self._mat.append([])        self._vnum += 1        return self._vnum - 1    # 添加一个边    def add_edge(self,vi,vj,val=1):        if self._vnum == 0:            raise ValueError("Cannot add edge to an empty Graph!")        if self._invalid(vi) or self._invalid(vj):            raise ValueError(str(vi) + 'or' + str(vj) + 'is not valid vertex!')        row = self._mat[vi]        i = 0        while i < len(row):            # 寻找vj对应的权重            if row[i][0] == vj:                self._mat[vi][i] = [vj,val]                return None             # 如果没有找到vj对应的值，说明vi和vj不相连            # 则退出循环，添加vi与vj的关联边            if row[i][0] > vj:                break            i += 1        # 添加vi与vj的关联边        self._mat[vi].insert(i,(vj,val))    def get_edge(self,vi,vj):        if self._invalid(vi) or self._invalid(vj):            raise ValueError(str(vi) + 'or' + str(vj) + 'is not valid vertex!')                # 寻找对应vi和vj的边的权重        if i,val in self._mat[vi]:            if i == vj:                return val                # 如果没有匹配到，则返回0        return self._unconn#----------图的压缩邻接矩阵实现-----------------#----------栈的实现---------------------------class Node:    def __init__(self):        self.val = val        self.next = Noneclass SStack:    def __init__(self):        self.top = None    # 获取栈顶的元素    def peek(self):        if self.top != None:            return self.top.val        else:            return None    # 将新元素压入到栈中    def push(self,n):        n = Node(n)        n.next = self.top        self.top = n        return n.val    # 退出栈    def pop(self):        if self.top == None:            return None        else:            tmp = self.top.val            self.top = self.top.next            return tmp#----------栈的实现---------------------------#----------1. 非递归DFS遍历--------------------def DFS_graph(graph,v0):    # 顶点个数    vnum = graph.vertex_num()    # 为每个顶点打上未访问的标记    visited = [0] * vnum    # 遍历序列    DFS_seq = [v0]    # 栈、用于存储每个顶点的边信息    st = SStack()    st.push((0,graph.out_edges(v0))) # 压入与起始结点相连的边中的第一条    while not st.is_empty():        # 取出顶点序号i与边列表        i,edges = st.pop()        if i < len(edges):            # v是顶点，e是边            v,e = edges[i]                        # 压入与该顶点相连的下一个边            # 待前一个边下面的所有结点都访问完了之后再访问            st.push((i+1,edges))                        # 如果没有访问过这个顶点            if not visited[v]:                # 将顶点加入列表中                DFS_seq.append(v)                # 访问过之后将标记置为1                visited[v] = 1                # 将与搜索到的顶点相连的顶点压入栈中，以备下次访问，这个比163行的更先访问到                st.push((0,graph.out_edges(v)))    return DFS_seq#----------1. 非递归DFS遍历--------------------#---------2. DFS生成树-------------------------def DFS_span_forest(graph):    # 顶点个数    vnum = graph.vertex_num()    # 记录路径信息    span_forest = [None] * vnum    def dfs(graph,v):        # 需要修改非局部变量，所以将之声明为nonlocal        nonlocal span_forest        # 遍历顶点v连接的所有路径，u是顶点，w是权重        for u,w in graph.out_edges(v):            # 如果这个顶点尚未加入span_forest            if span_forest[u] is None:                # 将结点u的上一结点和连接权重记录下来                span_forest[u] = (v,w)                dfs(graph,u)        # 避免还有不连通的点，所以要遍历到每个顶点    for v in range(vnum):        if span_forest[v] is None:            span_forest[v] = [v,0]            dfs(graph,v)    return span_forest            #---------2. DFS生成树-------------------------#---------3. Kruskal最小生成树-----------------def Kruskal(graph):    # 基本思路：设G = (V,E) 是一个网络，其中|V|（顶点数量）为n，则Kruskal的基本思路为：    # （1）取包含G的所有n个顶点但是没有任何边的孤立点子图T = (V,{})    #     T中的每个顶点自称一个连通分量，下面将通过不断扩充T的方式构造G的最小生成树；    # （2）将边集E按照权值递增的顺序排序，在构造中的每一步按顺序地检查这个边序列    #     找到最短的且两端位于T的两个不同的连通分量的边e，将e加入T，这样两个连通分量    #     就在e的作用下连接成了一个连通分量；    # （3）每次操作使T减少一个连通分量。不断重复这个动作，往T中加入新边，直到T中所有顶点    #     都包含在一个连通分量为止，这个连通分量就是G的一棵最小生成树。    # 获取顶点个数    vnum = graph.vertex_num()    # 将各顶点的代表元初始化，代表元代表了顶点所属的连通分量    reps = [i for i in range(vnum)]    # mst记录最小生成树的边，edges记录graph所有的边    mst,edges = [],[]    # 将所有的边加入edges    for vi in range(vnum):        for v,w in graph.out_edges(vi):            edges.append((w,vi,v))    # 按权重排列    edges.sort()    for w,vi,vj in edges:        # 如果vi和vj属于两个不同的连通分量        if reps[vi] != reps[vj]:            mst.append(((vi,vj),w))                        # 如果有n-1条边代表已经构造完成            if len(mst) == vnum - 1:                break            # 修改代表元，将所有与vj在同一连通分量的顶点归入vi所在的连通分量中                        rep,orep = reps[vi],reps[vj]            for i in range(vnum):                if reps[i] == orep:                    reps[i] = rep    return mst#---------3. Kruskal最小生成树-----------------