拓扑排序
若图为有向无环图，则可进行拓扑排序。拓扑排序的结果为DFS后序遍历的倒序。选课是拓扑排序的经典应用场景之一，即：选修一门课程之前须先修完该课程的前置课程。
class Graph(object):
def __init__(self, points_nums, is_directed):
self.__points_nums = points_nums
self.__adj = [[] for _ in range(points_nums)]
self.__directed = is_directed
self.__in_degree = [0 for _ in range(points_nums)]
def add_edge(self, point1, point2):
self.__adj[point1].append(point2)
self.__in_degree[point2] += 1
if not self.__directed:
self.__adj[point2].append(point1)
def get_adj(self, point):
return self.__adj[point]
def get_point_nums(self):
return self.__points_nums
def get_in_degree(self, point):
return self.__in_degree[point]
class DepthFirstOrder(object):
def __init__(self, graph):
self.__graph = graph
self.__reverse_postorder = []
self.__marked[False for _ in range(graph.get_point_nums())]
for point in range(graph.get_point_nums()):
if not self.__marked[point] and graph.get_in_degree(point) == 0:
self.__dfs(self.graph, point)
def __dfs(self, point):
self.__marked[point] = True
for adj_point in self.__graph.get_adj(point):
if not self.__mark[adj_point]:
self.__dfs(adj_point)
self.__reverse_postorder.insert(0, point)
作者：11 + 17 = 28
