深度优先搜索的拓扑排序python

本文仅对算法进行实现，原理可百度

import pandas as pd
from collections import defaultdict


# 拓扑排序类
class Graph:
    # 使用邻接链表的形式初始化图和总顶点数
    def __init__(self, v_num):
        self.graph = defaultdict(list)
        self.v = v_num

    # 添加边，记录每个顶点的邻接顶点
    def addEdge(self, u, v):
        self.graph[u].append(v)

    # 使用基于深度优先搜索的拓扑排序解决
    def topological_recursive(self, ver, visited, stack):
        # 标记当前顶点为已访问
        visited[ver] = True
        # 对当前顶点的所有邻接顶点中，访问未访问过的顶点
        for i in self.graph[ver]:
            if visited[i] == False:
                self.topological_recursive(i, visited, stack)
        # 当搜索回溯时，将当前顶点插入到栈
        stack.insert(0, ver)

    # 拓扑排序控制
    def topological_sorting(self):
        # 标记数组
        visited = [False] * self.v
        stack = []
        # 对每个顶点都要访问，以对多个连通分量时仍能访问
        for i in range(self.v):
            # 当前顶点未访问时，继续搜索
            if visited[i] == False:
                self.topological_recursive(i, visited, stack)
        # 结果输出
        self.print_class(stack)

    def print_class(self, stack):
        # 需要安排的课程
        course = ['高等数学', '程序设计', '离散数学', '数据结构', '编译原理', '操作系统', '计算机组成原理']

        for i in range(len(stack)):
            if i % 2 == 0:
                if i == 0: print('第', (i // 2) + 1, '学期: ', end='')
                else: print('\n第', (i // 2) + 1, '学期: ', end='')
            print(course[stack[i]], end='  ')

# 拓扑排序
def topological_sort(graph):
    length = len(graph)

    tpgl = Graph(length)
    # 边的添加
    for i in range(len(graph)):
        for j in range(len(graph)):
            if graph[i][j] == True:
                tpgl.addEdge(i, j)
    tpgl.topological_sorting()


def main():
    graph = [
        [False, False, True, False, False, False, False],
        [False, False, False, True, True, False, True],
        [False, False, False, True, False, False, False],
        [False, False, False, False, True, True, False],
        [False, False, False, False, False, False, False],
        [False, False, False, False, False, False, False],
        [False, False, False, False, False, True, False]
    ]
    topological_sort(graph)


if __name__ == '__main__':
    main()