拓扑排序详解

1. 定义

拓扑排序（Topological Sorting）是对有向无环图（DAG, Directed Acyclic Graph）顶点进行的一种排序，使得对于每一条有向边 ( u \rightarrow v )，顶点 ( u ) 在排序中出现在顶点 ( v ) 之前。简言之，拓扑排序就是给定一组先决条件，找出一个符合这些条件的排列顺序。

2. 拓扑排序的性质

1. 有向无环图：只有DAG可以进行拓扑排序。
2. 唯一性：一个DAG可能有多个拓扑排序，但如果存在环路，则无法进行拓扑排序。
3. 拓扑序列：拓扑排序的结果是所有顶点的一个线性序列。

3. 拓扑排序算法

拓扑排序常用的算法有两种：

1. Kahn算法：基于入度的广度优先搜索。
2. DFS算法：基于深度优先搜索。

3.1 Kahn算法

Kahn算法利用入度的概念进行排序。具体步骤如下：

1. 找到所有入度为0的顶点，放入队列。
2. 从队列中取出一个顶点，输出到拓扑排序的结果中，并删除其指向的所有边。
3. 更新这些边所指向顶点的入度，如果入度变为0，则将这些顶点加入队列。
4. 重复上述过程直到队列为空。
5. 如果所有顶点都已输出，则排序完成，否则图中存在环路。

算法复杂度：时间复杂度为 $O(V + E)$，空间复杂度为 $O(V)$。

3.2 DFS算法

DFS算法利用递归的方式进行排序。具体步骤如下：

1. 初始化所有顶点为未访问状态。
2. 从任意一个未访问的顶点开始进行DFS。
3. 在DFS过程中，对于每一个顶点，将其所有邻接点进行递归访问。
4. 在访问完所有邻接点后，将该顶点压入栈。
5. 最终栈中的顶点序列即为拓扑排序的结果。

算法复杂度：时间复杂度为 $O(V + E)$，空间复杂度为 $O(V)$。

4. 拓扑排序的代码实现（C语言）

4.1 Kahn算法实现

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

// 邻接表结构
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

typedef struct Graph {
    int numVertices;
    Node** adjLists;
    int* inDegree;
} Graph;

// 创建图
Graph* createGraph(int vertices) {
    Graph* graph = malloc(sizeof(Graph));
    graph->numVertices = vertices;
    graph->adjLists = malloc(vertices * sizeof(Node*));
    graph->inDegree = malloc(vertices * sizeof(int));
    
    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
        graph->inDegree[i] = 0;
    }
    return graph;
}

// 添加边
void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
    graph->inDegree[dest]++;
}

// 拓扑排序
void topologicalSort(Graph* graph) {
    int* queue = malloc(graph->numVertices * sizeof(int));
    int front = 0, rear = 0;
    int* topOrder = malloc(graph->numVertices * sizeof(int));
    int index = 0;
    
    for (int i = 0; i < graph->numVertices; i++) {
        if (graph->inDegree[i] == 0) {
            queue[rear++] = i;
        }
    }
    
    while (front < rear) {
        int currentVertex = queue[front++];
        topOrder[index++] = currentVertex;
        
        Node* temp = graph->adjLists[currentVertex];
        while (temp) {
            int adjVertex = temp->vertex;
            graph->inDegree[adjVertex]--;
            if (graph->inDegree[adjVertex] == 0) {
                queue[rear++] = adjVertex;
            }
            temp = temp->next;
        }
    }
    
    if (index != graph->numVertices) {
        printf("Graph has a cycle\n");
        return;
    }
    
    for (int i = 0; i < graph->numVertices; i++) {
        printf("%d ", topOrder[i]);
    }
    printf("\n");
    
    free(queue);
    free(topOrder);
}

int main() {
    Graph* graph = createGraph(6);
    addEdge(graph, 5, 2);
    addEdge(graph, 5, 0);
    addEdge(graph, 4, 0);
    addEdge(graph, 4, 1);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 1);
    
    printf("Topological Sort of the given graph:\n");
    topologicalSort(graph);
    
    return 0;
}

4.2 DFS算法实现

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

// 邻接表结构
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

typedef struct Graph {
    int numVertices;
    Node** adjLists;
    int* visited;
} Graph;

// 创建图
Graph* createGraph(int vertices) {
    Graph* graph = malloc(sizeof(Graph));
    graph->numVertices = vertices;
    graph->adjLists = malloc(vertices * sizeof(Node*));
    graph->visited = malloc(vertices * sizeof(int));
    
    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
        graph->visited[i] = 0;
    }
    return graph;
}

// 添加边
void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
}

// DFS算法
void dfs(Graph* graph, int vertex, int* stack, int* top) {
    graph->visited[vertex] = 1;
    Node* temp = graph->adjLists[vertex];
    
    while (temp) {
        int adjVertex = temp->vertex;
        if (!graph->visited[adjVertex]) {
            dfs(graph, adjVertex, stack, top);
        }
        temp = temp->next;
    }
    
    stack[(*top)++] = vertex;
}

// 拓扑排序
void topologicalSort(Graph* graph) {
    int* stack = malloc(graph->numVertices * sizeof(int));
    int top = 0;
    
    for (int i = 0; i < graph->numVertices; i++) {
        if (!graph->visited[i]) {
            dfs(graph, i, stack, &top);
        }
    }
    
    for (int i = top - 1; i >= 0; i--) {
        printf("%d ", stack[i]);
    }
    printf("\n");
    
    free(stack);
}

int main() {
    Graph* graph = createGraph(6);
    addEdge(graph, 5, 2);
    addEdge(graph, 5, 0);
    addEdge(graph, 4, 0);
    addEdge(graph, 4, 1);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 1);
    
    printf("Topological Sort of the given graph:\n");
    topologicalSort(graph);
    
    return 0;
}

5. 复杂度分析

1. 时间复杂度：无论是Kahn算法还是DFS算法，时间复杂度均为 $O(V + E)$，其中 $V$ 是顶点数，$E$ 是边数。这是因为每个顶点和边都仅被处理一次。
2. 空间复杂度：空间复杂度主要取决于存储图的结构（邻接表）和辅助数据结构（如队列或栈）。总的空间复杂度为 $O(V + E)$。

6. 拓扑排序的应用

拓扑排序广泛应用于以下领域：

1. 编译器构造：确定代码模块的编译顺序。
2. 项目管理：任务调度和依赖关系的管理。
3. 数据序列化：确保依赖项先于被依赖项处理。

通过以上内容，您可以更好地理解拓扑排序及其实现。如果您需要更详细的内容或有其他问题，欢迎进一步交流。