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

图的数据结构及深度优先、广度优先、最短路径算法python实现

程序员文章站 2022-05-23 10:50:28
...
|-图的表示
    邻接矩阵:适合表示稠密图(完全图)
    邻接表:适合表示稀疏图
|-图的遍历
    深度优先遍历
        可以用于计算图的连通分量个数
        寻路: 定义一个from数组指向该点的前一个节点
        复杂度:
            邻接表-O(n+e)
            邻接矩阵-O(n^2)
    广度优先遍历
        最短路径
        复杂度:
            邻接表-O(n+e)

            邻接矩阵-O(n^2)

源代码:
https://github.com/lzneu/Algrithm_python

# 邻接矩阵实现稠密图
class DenseGraph:
    def __init__(self, n, directed):
        self.__m = 0  # 边数
        self.__n = n  # 顶点个数
        self.__directed = directed  # 是否有向图
        self.g = []
        for i in range(n):
            self.g.append(list(False for vec in range(n)))

    def V(self):
        return self.__n

    def E(self):
        return self.__m

    def addEdge(self, v, w):
        assert 0 <= v < self.__n
        assert 0 <= w < self.__n

        # 若已经存在边
        if self.hasEdge(v, w):
            return

        self.g[v][w] = True
        if (not self.__directed):
            # 非有向图
            self.g[w][v] = True
        self.__m += 1

    def hasEdge(self, v, w):
        assert (v >= 0 and v < self.__n)
        assert (w >= 0 and w < self.__n)
        return self.g[v][w]

    # 打印邻接矩阵
    def show(self):
        for v in range(self.__n):
            print(('vertex%d: %s') % (v, str(self.g[v])))

    # 返回v节点的邻接节点
    def getAdj(self, v):
        retList = []
        adj_list = self.g[v]
        for i in range(len(adj_list)):
            if adj_list[i] == True:
                retList.append(i)
        return retList




# 稀疏图
class SparseGraph:
    def __init__(self, n, directed):
        self.__n = n
        self.__m = 0
        self.__directed = directed
        self.g = []
        for i in range(n):
            self.g.append([])

    def V(self):
        return self.__n

    def E(self):
        return self.__m

    def addEdge(self, v ,w):
        assert (v >= 0 and v < self.__n)
        assert (w >= 0 and w < self.__n)

        self.g[v].append(w)
        if (v != w and not self.__directed):
            self.g[w].append(v)
        self.__m += 1

    def hasEdge(self, v, w):
        assert (v >= 0 and v < self.__n)
        assert (w >= 0 and w < self.__n)

        # # 不包平行边处理 复杂度 O(N) 一般单独处理 此处注释
        # if self.hasEdge(v, w):
        #     return
        for i in range(self.__n):
            if w == self.g[v][i]:
                return True
            else:
                return False

    # 打印邻接表
    def show(self):
        for v in range(self.__n):
            print(('vertex%d: %s')% (v, str(self.g[v])))

    # 返回v节点的邻接节点
    def getAdj(self, v):
        return self.g[v]


# 读取文件生成图数据结构的类
class ReadgRraph:
    # 从文件filename中读取图的信息, 存储进图graph中
    def __init__(self, graph, filename):
        with open(filename, 'r') as f:
            lines = f.readlines()
        f.close()
        assert len(lines) >= 1, '文件格式错误'
        self.V = int(lines[0].split(' ')[0])
        self.E = int(lines[0].split(' ')[1])
        edges = []
        for line in lines[1:]:
            edges.append(line.split(' '))
        assert self.V == graph.V(), '文件和图的顶点个数不一致'

        # 读取每一条边的信息
        for edge in edges:
            a = int(edge[0])
            b = int(edge[1])
            assert 0 <= a < self.V
            assert 0 <= a < self.V
            graph.addEdge(a, b)


# 图的深度优先遍历类
class Component:
    # 构造函数 求出无权图的联通分量
    def __init__(self, graph):
        self.__graph = graph
        self.__ccount = 0  # 记录连通分量的个数
        self.__visited = []  # 记录dfs过程中节点是否被访问
        self.__id = []  # 每个节点对应的连通分量的标记
        # 初始化两个指示数组
        for i in range(self.__graph.V()):
            self.__visited.append(False)
            self.__id.append(-1)
        # 求图的连通分量
        for i in range(self.__graph.V()):
            if not self.__visited[i]:
                self.__dfs(i)
                self.__ccount += 1

    # 图的深度优先遍历
    def __dfs(self, v):
        self.__visited[v] = True
        self.__id[v] = self.__ccount
        for i in self.__graph.getAdj(v):
            # i为v节点的临接点
            if not self.__visited[i]:
                self.__dfs(i)

    # 返回图的连通分量个数
    def count(self):
        return self.__ccount

    # 查询点v和是否联通
    def isConnect(self, v, w):
        assert v >= 0 and v < self.__graph.V()
        assert w >= 0 and w < self.__graph.V()
        return self.__id[v] == self.__id[w]


# 利用深度优先遍历进行图的寻路
class Path:
    # 构造函数 求出从s到任意一个点的路径
    def __init__(self, graph, s):
        assert 0 <= s < graph.V(), '源结点不在图中'
        self.__graph = graph
        self.__s = s  # 记录连通图的源节点
        self.__visited = []  # 记录dfs过程中节点是否被访问
        self.__from = []  # 每个结点从哪个结点过来
        # 初始化两个指示数组
        for i in range(self.__graph.V()):
            self.__visited.append(False)
            self.__from.append(-1)
        # 寻路算法
        self.__dfs(s)

    # 图的深度优先遍历
    def __dfs(self, v):
        self.__visited[v] = True
        for i in self.__graph.getAdj(v):
            # i为v节点的临接点
            if not self.__visited[i]:
                self.__from[i] = v
                self.__dfs(i)

    # 查询从s结点到w结点是否有路径
    def hasPath(self, w):
        assert 0 <= w < self.__graph.V(), 'w结点不在图中'
        return self.__visited[w]  # 如果该为True 证明从s访问过w

    # 查询从s到w的路径,返回一个存放路径的list
    def path(self, w):
        assert self.hasPath(w), '从源结点到该结点不存在路径'
        # 通过from数组你想查找从s到w的路径 存放到栈中 此处用list作为一个栈
        p = w
        stack = []
        while p != -1:
            stack.append(p)
            p = self.__from[p]
        stack.reverse()
        return stack

    def showPath(self, w):
        retVec = self.path(w)
        for i in range(len(retVec)-1):
            print(retVec[i], end='-')
        print(retVec[-1])


from queue import Queue
# 寻找无权图的最短路径
class ShortestPath:

    def __init__(self, graph, s):
        self.__graph = graph
        assert 0 <= s < self.__graph.V()
        self.__s = s
        self.__visited = []
        self.__from = []
        self.__ord = []  # 该点到源结点的最短路径长度
        for i in range(self.__graph.V()):
            self.__visited.append(False)
            self.__from.append(-1)
            self.__ord.append(-1)

        # 无向图最短路径算法,从s开始广度优先遍历整张图
        q = Queue()
        q.put(self.__s)
        self.__visited[self.__s] = True
        self.__ord[self.__s] = 0
        while not q.empty():
            v = q.get()  # 出队一个结点
            for i in self.__graph.getAdj(v):
                # i为结点v的邻接节点
                if not self.__visited[i]:
                    # 没有遍历该节点
                    q.put(i)
                    self.__visited[i] = True
                    self.__from[i] = v
                    self.__ord[i] = self.__ord[v] + 1

    def hasPath(self, w):
        assert 0 <= w < self.__graph.V()
        return self.__visited[w]

    def path(self, w):
        assert 0 <= w < self.__graph.V()

        stack = []
        p = w
        while p != -1:
            stack.append(p)
            p = self.__from[p]
        # 依此取出stack中的元素
        stack.reverse()
        return stack

    def showPath(self, w):
        retVec = self.path(w)
        for i in range(len(retVec)-1):
            print(retVec[i], end='-')
        print(retVec[-1])

    def length(self, w):
        assert 0 <= w < self.__graph.V()
        return self.__ord[w]





if __name__ == '__main__':
    filename = './data/testG1.txt'
    g1 = SparseGraph(13, False)
    readGraph1 = ReadgRraph(g1, filename)
    g1.show()
    component1 = Component(g1)
    print(component1.count())

    filename2 = './data/testG.txt'
    g2 = SparseGraph(7, False)
    readGraph2 = ReadgRraph(g2, filename2)
    g2.show()
    component2 = Component(g2)
    print(component2.count())
    path2 = Path(g2, 0)
    path2.showPath(6)


    path3 = ShortestPath(g2, 0)
    path3.showPath(6)