用深度优先遍历实现图的拓扑排序并能判断有向图是否有环

要使用深度优先遍历实现图的拓扑排序并判断有向图是否有环，可以按照以下步骤进行：

1. 创建一个空的栈，用于存储拓扑排序的结果。
2. 遍历图中的每个顶点，如果该顶点未被访问过，则调用深度优先遍历函数进行拓扑排序。
3. 在深度优先遍历函数中，首先将当前顶点标记为已访问，并递归地访问其所有未被访问过的邻居顶点。
4. 在递归访问邻居顶点之前，检查邻居顶点是否已被访问过，如果已访问过，则跳过该邻居顶点的遍历。
5. 在递归访问邻居顶点之后，将当前顶点入栈。
6. 完成深度优先遍历后，如果图中存在环，则无法进行拓扑排序，直接返回空。
7. 如果图中不存在环，则将栈中的顶点逐个弹出，并按照弹出顺序形成的序列即为拓扑排序结果。

下面是一个示例代码实现：

def dfs(v, visited, graph, stack):
    visited[v] = True

    for neighbor in graph[v]:
        if not visited[neighbor]:
            dfs(neighbor, visited, graph, stack)

    stack.append(v)

def topological_sort(graph):
    num_vertices = len(graph)
    visited = [False] * num_vertices
    stack = []

    for v in range(num_vertices):
        if not visited[v]:
            dfs(v, visited, graph, stack)

    if len(stack) != num_vertices:
        return None  # 存在环，无法进行拓扑排序

    return stack[::-1]  # 返回拓扑排序结果

# 示例用法
graph = {
    0: [1, 2],
    1: [3],
    2: [3],
    3: []
}

topological_order = topological_sort(graph)
if topological_order is not None:
    print("拓扑排序结果:", topological_order)
else:
    print("图中存在环")

在示例代码中，我们使用邻接表来表示有向图，`graph`是一个字典，键表示顶点，值表示与该顶点相邻的顶点列表。通过调用`topological_sort`函数，可以得到图的拓扑排序结果，如果返回结果为None，则表示图中存在环。