# 算法：如何实现有向无环图(DAG)的拓扑排序？

2021年3月19日17:21:38 发表评论 1,162 次浏览

## 本文概述

InDFS, 我们先打印一个顶点, 然后递归调用其相邻顶点的DFS。在拓扑排序中, 我们需要在相邻顶点之前打印顶点。例如, 在给定的图形中, 顶点" 5"应在顶点" 0"之前打印, 但与DFS, 顶点" 4"也应在顶点" 0"之前打印。因此, 拓扑排序不同于DFS。例如, 所示图形的DFS为" 5 2 3 1 0 4", 但这不是拓扑排序。

## C ++

// A C++ program to print topological
// sorting of a DAG
#include <iostream>
#include <list>
#include <stack>
using namespace std;

// Class to represent a graph
class Graph {
// No. of vertices'
int V;

// Pointer to an array containing adjacency listsList

// A function used by topologicalSort
void topologicalSortUtil( int v, bool visited[], stack< int >& Stack);

public :
// Constructor
Graph( int V);

// function to add an edge to graph
void addEdge( int v, int w);

// prints a Topological Sort of
// the complete graph
void topologicalSort();
};

Graph::Graph( int V)
{
this ->V = V;
adj = new list< int >[V];
}

void Graph::addEdge( int v, int w)
{
// Add w to v’s list.
}

// A recursive function used by topologicalSort
void Graph::topologicalSortUtil( int v, bool visited[], stack< int >& Stack)
{
// Mark the current node as visited.
visited[v] = true ;

// Recur for all the vertices
list< int >::iterator i;
if (!visited[*i])
topologicalSortUtil(*i, visited, Stack);

// Push current vertex to stack
// which stores result
Stack.push(v);
}

// The function to do Topological Sort.
// It uses recursive topologicalSortUtil()
void Graph::topologicalSort()
{
stack< int > Stack;

// Mark all the vertices as not visited
bool * visited = new bool [V];
for ( int i = 0; i < V; i++)
visited[i] = false ;

// Call the recursive helper function
// to store Topological
// Sort starting from all
// vertices one by one
for ( int i = 0; i < V; i++)
if (visited[i] == false )
topologicalSortUtil(i, visited, Stack);

// Print contents of stack
while (Stack.empty() == false ) {
cout << Stack.top() << " " ;
Stack.pop();
}
}

// Driver Code
int main()
{
// Create a graph given in the above diagram
Graph g(6);

cout << "Following is a Topological Sort of the given "
"graph \n" ;

// Function Call
g.topologicalSort();

return 0;
}

## Java

// A Java program to print topological
// sorting of a DAG
import java.io.*;
import java.util.*;

// This class represents a directed graph
class Graph {
// No. of vertices
private int V;

// Adjacency List as ArrayList of ArrayList's

// Constructor
Graph( int v)
{
V = v;
for ( int i = 0 ; i < v; ++i)
}

// Function to add an edge into the graph

// A recursive function used by topologicalSort
void topologicalSortUtil( int v, boolean visited[], Stack<Integer> stack)
{
// Mark the current node as visited.
visited[v] = true ;
Integer i;

// Recur for all the vertices adjacent
// to thisvertex
while (it.hasNext()) {
i = it.next();
if (!visited[i])
topologicalSortUtil(i, visited, stack);
}

// Push current vertex to stack
// which stores result
stack.push( new Integer(v));
}

// The function to do Topological Sort.
// It uses recursive topologicalSortUtil()
void topologicalSort()
{
Stack<Integer> stack = new Stack<Integer>();

// Mark all the vertices as not visited
boolean visited[] = new boolean [V];
for ( int i = 0 ; i < V; i++)
visited[i] = false ;

// Call the recursive helper
// function to store
// Topological Sort starting
// from all vertices one by one
for ( int i = 0 ; i < V; i++)
if (visited[i] == false )
topologicalSortUtil(i, visited, stack);

// Print contents of stack
while (stack.empty() == false )
System.out.print(stack.pop() + " " );
}

// Driver code
public static void main(String args[])
{
// Create a graph given in the above diagram
Graph g = new Graph( 6 );

System.out.println( "Following is a Topological "
+ "sort of the given graph" );
// Function Call
g.topologicalSort();
}
}
// This code is contributed by Aakash Hasija

## python

# Python program to print topological sorting of a DAG
from collections import defaultdict

# Class to represent a graph

class Graph:
def __init__( self , vertices):
self .graph = defaultdict( list )  # dictionary containing adjacency List
self .V = vertices  # No. of vertices

# function to add an edge to graph
def addEdge( self , u, v):
self .graph[u].append(v)

# A recursive function used by topologicalSort
def topologicalSortUtil( self , v, visited, stack):

# Mark the current node as visited.
visited[v] = True

# Recur for all the vertices adjacent to this vertex
for i in self .graph[v]:
if visited[i] = = False :
self .topologicalSortUtil(i, visited, stack)

# Push current vertex to stack which stores result
stack.append(v)

# The function to do Topological Sort. It uses recursive
# topologicalSortUtil()
def topologicalSort( self ):
# Mark all the vertices as not visited
visited = [ False ] * self .V
stack = []

# Call the recursive helper function to store Topological
# Sort starting from all vertices one by one
for i in range ( self .V):
if visited[i] = = False :
self .topologicalSortUtil(i, visited, stack)

# Print contents of the stack
print stack[:: - 1 ]  # return list in reverse order

# Driver Code
g = Graph( 6 )

print "Following is a Topological Sort of the given graph"

# Function Call
g.topologicalSort()

# This code is contributed by Neelam Yadav

## C#

// A C# program to print topological
// sorting of a DAG
using System;
using System.Collections.Generic;

// This class represents a directed graph
class Graph {

// No. of vertices
private int V;

// of ArrayList's
private List<List< int > > adj;

// Constructor
Graph( int v)
{
V = v;
adj = new List<List< int > >(v);
for ( int i = 0; i < v; i++)
}

// Function to add an edge into the graph

// A recursive function used by topologicalSort
void TopologicalSortUtil( int v, bool [] visited, Stack< int > stack)
{

// Mark the current node as visited.
visited[v] = true ;

// Recur for all the vertices
foreach ( var vertex in adj[v])
{
if (!visited[vertex])
TopologicalSortUtil(vertex, visited, stack);
}

// Push current vertex to
// stack which stores result
stack.Push(v);
}

// The function to do Topological Sort.
// It uses recursive topologicalSortUtil()
void TopologicalSort()
{
Stack< int > stack = new Stack< int >();

// Mark all the vertices as not visited
var visited = new bool [V];

// Call the recursive helper function
// to store Topological Sort starting
// from all vertices one by one
for ( int i = 0; i < V; i++) {
if (visited[i] == false )
TopologicalSortUtil(i, visited, stack);
}

// Print contents of stack
foreach ( var vertex in stack)
{
Console.Write(vertex + " " );
}
}

// Driver code
public static void Main( string [] args)
{

// Create a graph given
// in the above diagram
Graph g = new Graph(6);

Console.WriteLine( "Following is a Topological "
+ "sort of the given graph" );

// Function Call
g.TopologicalSort();
}
}

// This code is contributed by Abhinav Galodha

Following is a Topological Sort of the given graph
5 4 2 3 1 0

• 时间复杂度：O(V + E)。
上面的算法只是带有额外堆栈的DFS。因此, 时间复杂度与DFS相同。
• 辅助空间：O(V)。
堆栈需要额外的空间。

2

]。

：另一种O(V + E)算法。

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/topoSort.htm

http://en.wikipedia.org/wiki/Topological_sorting