【Python】对一个有向无环图(Directed Acyclic Graph，DAG)G进行拓扑排序

梦里梦外; 2022-05-23 08:42 147阅读 0赞

### 拓扑排序 示例： ###

> 对一个有向无环图(Directed Acyclic Graph，DAG)G进行拓扑排序，是将G中所有顶点排成线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前  
> 一种可能的拓扑排序结果2->8->0->3->7->1->5->6->9->4->11->10->12  
> ![拓扑排序][70]

算法分析

> 拓扑排序的方法  
> 从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它；  
> 从网中删去该顶点，并且删去从该顶点发出的全部有向边；  
> 重复上述两步，直到剩余的网中不再存在没有前趋的顶点为止。

Python代码如下：

#### 解法1：用邻接矩阵表示图的拓扑排序 ####

import numpy as np
    
    
    def topological_sort(g):
        n = len(g)
        # 获取所有入度为0的结点
        q = []
        for j in range(n):
            flag = True
            for i in range(n):
                if g[i][j] == 1:
                    flag = False
                    break
            if flag:
                q.insert(0, j)
    
        li = []  # 记录结果
        while len(q) > 0:
            # p出队，把从p出度的数据置为0
            p = q.pop()
            li.append(p)
            for i in range(n):
                if g[p][i] == 1:
                    g[p][i] = 0  # 去掉连通
                    # 如果结点i的入度为0则入队结点i
                    in_degree_count = 0
                    for u in g:
                        if u[i] == 1:
                            in_degree_count += 1
                    if in_degree_count == 0:
                        q.insert(0, i)
    
        return li
    
    
    if __name__ == '__main__':
        # 用邻接矩阵表示图
        # 初始化图的数据，连通的标记为1
        g = np.zeros(shape=(13, 13), dtype='int')
        # g[i][j] = 1 表示 i -> j
        g[0][1] = g[0][5] = g[0][6] = 1
        g[2][0] = g[2][3] = 1
        g[3][5] = 1
        g[5][4] = 1
        g[6][4] = g[6][9] = 1
        g[7][6] = 1
        g[8][7] = 1
        g[9][10] = g[9][11] = g[9][12] = 1
        g[11][12] = 1
    
        result = topological_sort(g)
        print(result)

输出结果：\[2, 8, 0, 3, 7, 1, 5, 6, 4, 9, 10, 11, 12\]

#### 解法2：用邻接表表示图的拓扑排序 ####

def topological_sort2(g):
        n = len(g)
        # 计算所有结点的入度
        in_degree = [0] * n
        for i in range(n):
            for k in g[i]:
                in_degree[k] += 1
        # 入度为0的结点
        in_degree_0 = []
        for i in range(n):
            if in_degree[i] == 0:
                in_degree_0.insert(0, i)
    
        li = []  # 记录结果
        while len(in_degree_0) > 0:
            # p出队
            p = in_degree_0.pop()
            li.append(p)
            for k in g[p]:
                # 对应结点的入度减1
                in_degree[k] -= 1
                if in_degree[k] == 0:
                    in_degree_0.insert(0, k)
    
        return li
    
    
    if __name__ == '__main__':
        # 用邻接表表示图
        g2 = [[]] * 13
        g2[0] = [1, 5, 6]
        g2[2] = [3]
        g2[3] = [5]
        g2[5] = [4]
        g2[6] = [4, 9]
        g2[7] = [6]
        g2[8] = [7]
        g2[9] = [10, 11, 12]
        g2[11] = [12]
        result2 = topological_sort2(g2)
        print(result2)

输出结果：\[0, 2, 8, 1, 3, 7, 5, 6, 4, 9, 10, 11, 12\]

[70]: /images/20220523/4f3434a3fc5e4e40afaeda9806732760.png