C 语言 Kahn 算法

2025年1月7日 | 阅读13分钟

Kahn 算法是一种广泛用于有向无环图 (DAG) 拓扑排序的方法。DAG 的拓扑排序是其顶点的线性排序，使得对于从顶点 u 到顶点 v 的每条有向边 uv，u 在排序中都排在 v 之前。这种排序在各种应用中至关重要，例如任务调度、链接器中的符号依赖关系解析以及数据序列化。

Kahn 算法是一种迭代方法，它通过反复移除没有入边（入度为零）的顶点并将其添加到拓扑顺序来工作。该算法以Arthur B. Kahn的名字命名，他于 20 世纪 60 年代引入了该算法。它以其处理拓扑排序的简单性和效率而著称。

Kahn 算法的步骤

计算入度：算法开始时，计算图中每个顶点的入度（入边的数量）。此步骤涉及遍历所有边并计算每个顶点的入边数。

初始化队列：初始化一个队列，其中包含所有入度为零的顶点。这些顶点没有依赖关系，可以立即处理。

处理队列：然后算法处理队列中的每个顶点

从队列中移除顶点并将其添加到拓扑顺序中。

对于移除顶点的每个相邻顶点，其入度减一（因为一条边已被“移除”）。

如果相邻顶点的入度变为零，则将其添加到队列中，因为它现在可以被处理。

检查循环：处理完所有顶点后，算法检查添加到拓扑顺序中的顶点数量是否等于图中的总顶点数。如果不相等，则图包含循环，并且无法进行拓扑排序。

方法一：标准队列实现

Kahn 算法的拓扑排序可以使用标准队列来实现。此方法涉及跟踪每个顶点的入度，并使用队列来管理没有入边（即入度为零）的顶点。

程序

 
#include <stdio.h>
#include <stdlib.h>
// Define the maximum number of vertices
#define MAX 100
// Adjacency list node
struct AdjListNode {
    int dest;
    struct AdjListNode* next;
};
// Adjacency list
struct AdjList {
    struct AdjListNode* head;
};
// Graph structure
struct Graph {
    int V;
    struct AdjList* array;
};
// Create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest) {
    struct AdjListNode* newNode = (struct AdjListNode*)malloc(sizeof(struct AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}
// Create a graph with V vertices
struct Graph* createGraph(int V) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->V = V;
    graph->array = (struct AdjList*)malloc(V * sizeof(struct AdjList));
    for (int i = 0; i < V; ++i)
        graph->array[i].head = NULL;
    return graph;
}
// Add an edge to the graph
void addEdge(struct Graph* graph, int src, int dest) {
    struct AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;
}
//Function to perform Kahn's algorithm for topological sorting using a queue
void topologicalSort(struct Graph* graph) {
    int V = graph->V;
    int* in_degree = (int*)malloc(V * sizeof(int));
    for (int i = 0; i < V; i++)
        in_degree[i] = 0;
    // Calculate in-degrees of all vertices
    for (int u = 0; u < V; u++) {
        struct AdjListNode* node = graph->array[u].head;
        while (node != NULL) {
            in_degree[node->dest]++;
            node = node->next;
        }
    }
    // Enqueue vertices with in-degree 0
    int* queue = (int*)malloc(V * sizeof(int));
    int front = 0, rear = 0;
    for (int i = 0; i < V; i++)
        if (in_degree[i] == 0)
            queue[rear++] = i;
    int count = 0;
    int* topOrder = (int*)malloc(V * sizeof(int));
    while (front < rear) {
        int u = queue[front++];
        topOrder[count++] = u;
        struct AdjListNode* node = graph->array[u].head;
        while (node != NULL) {
            if (--in_degree[node->dest] == 0)
                queue[rear++] = node->dest;
            node = node->next;
        }
    }
    // Check if there was a cycle
    if (count != V) {
        printf("There exists a cycle in the graph\n");
        return;
    }
    // Print topological order
    for (int i = 0; i < count; i++)
        printf("%d ", topOrder[i]);
    printf("\n");
    // Free allocated memory
    free(in_degree);
    free(queue);
    free(topOrder);
}
// Driver program to test the above functions
int main() {
    // Create a graph given in the above diagram
    int V = 6;
    struct Graph* graph = createGraph(V);
    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("Following is a Topological Sort of the given graph\n");
    topologicalSort(graph);
    return 0;
}   

输出

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

说明

图的表示
图使用邻接表表示。在此表示中，每个顶点都有一个指向它的顶点列表。这是一种常用且高效的图表示方法，尤其是在图稀疏（边数远少于顶点数）时。图结构包含一个邻接表数组，每个列表对应图中的一个顶点。
邻接表节点
邻接表节点结构表示邻接表中的一个元素。每个节点包含目标顶点（即当前顶点指向的顶点）以及指向列表中下一个节点的指针。这形成了一个链表，其中每个节点都指向邻接表中的下一个顶点。
图初始化
图根据给定的顶点数 (V) 进行初始化。为图结构和邻接表数组分配内存。每个列表最初设置为 NULL，表示尚未添加任何边。
添加边
要从源顶点添加边到目标顶点，会创建一个新的邻接表节点，其中包含目标顶点。然后将此节点插入到源顶点邻接表的开头。这种开头插入可确保以 O(1) 的时间复杂度高效添加边。

使用 Kahn 算法进行拓扑排序

计算入度

in_degree 数组存储每个顶点的入度（入边数）。最初，所有入度都设置为零。

算法通过遍历每个顶点的邻接表来遍历图。对于每个相邻顶点，都会增加其入度。此步骤可确保所有顶点的入度都已正确计算。

初始化队列

初始化一个队列来存储入度为零的顶点。这些顶点没有依赖关系，可以立即处理。所有入度为零的顶点都已入队。这是可以安全处理而不会违反拓扑顺序的初始顶点集。

处理队列

算法进入一个循环，在该循环中它从队列的前面反复出队一个顶点。出队的顶点被添加到拓扑顺序中，确保它出现在它指向的任何顶点之前。

对于出队顶点的每个相邻顶点，其入度减一。如果相邻顶点的入度变为零，则将其入队。此步骤确保顶点按正确的顺序处理。

此过程一直持续到队列为空。每个顶点都处理一次，确保所有顶点都包含在拓扑顺序中。

环检测
处理完所有顶点后，算法会检查拓扑顺序中的顶点数量是否等于图中的总顶点数。如果计数较少，则表示图中存在循环。循环将阻止有效的拓扑排序，因为它会产生一个情况，即无法满足约束的线性排序。
如果检测到循环，算法会打印一条消息指示其存在。否则，它会打印拓扑顺序。
驱动程序
驱动程序创建了一个具有指定数量顶点（在本例中为六个顶点）的图。它向图中添加边以表示任务之间的依赖关系。设置好图之后，就调用topologicalSort 函数，该函数执行拓扑排序并打印结果。

复杂度分析

时间复杂度

Kahn 算法的时间复杂度可以分解为几个步骤

图表示初始化

创建图并初始化邻接表数组需要 O(V) 时间，其中 V 是顶点的数量。

计算入度

初始化入度数组需要 O(V) 时间。

计算入度涉及遍历图的所有边。对于每个顶点，我们遍历其邻接表。操作总数与所有邻接表长度之和成正比，等于边数 (E)。因此，此步骤需要 O(E) 时间。

队列初始化

将所有入度为零的顶点入队需要扫描一次入度数组，耗时 O(V)。

处理队列

每个顶点都入队和出队一次。队列的入队和出队操作每个操作耗时 O(1)。由于有 V 个顶点，这些操作加起来耗时O(V) 时间。

递减相邻顶点的入度涉及再次遍历所有边。每条边在其起始顶点出队时处理一次，从而减少其结束顶点的入度。这需要O(E) 时间。

循环检测和最终检查

检查处理过的顶点数是否等于总顶点数只需一次简单的比较，耗时 O(1)。

将这些步骤结合起来，总时间复杂度为：O(V)+O(E)+O(V)+O(E)+O(1)=O(V+E)

因此，Kahn 算法的时间复杂度为 O(V+E)，与图中的顶点和边数呈线性关系。这种效率使其适用于大型图。

空间复杂度

空间复杂度分析考虑了算法中数据结构使用的内存

图的表示

图使用邻接表表示。邻接表数组包含 V 个列表，所有列表中的节点总数为 E。因此，邻接表所需的空间为O(V + E)。

入度数组

使用大小为 V 的数组存储每个顶点的入度，这需要O(V) 空间。

Queue

队列存储入度为零的顶点。在最坏的情况下，所有顶点都可能在某个时候入队，这需要O(V) 空间。

拓扑顺序数组

用于存储顶点拓扑顺序的数组也需要 O(V) 空间。

将这些结合起来，算法的总空间复杂度为：O(V+E)+O(V)+O(V)+O(V)=O(V+E)

因此，Kahn 算法的空间复杂度为 O(V+E)。这种线性空间复杂度确保了该算法即使对于大型图也能高效利用内存。

方法二：使用向量的 Kahn 算法

使用向量实现 Kahn 算法是实现拓扑排序的另一种方法。此方法是标准队列实现的一种变体，它使用向量来维护零入度顶点的列表。

程序

 
#include <stdio.h>
#include <stdlib.h>
// Define the maximum number of vertices
#define MAX 100
// Adjacency list node
struct AdjListNode {
    int dest;
    struct AdjListNode* next;
};
// Adjacency list
struct AdjList {
    struct AdjListNode* head;
};
// Graph structure
struct Graph {
    int V;
    struct AdjList* array;
};
// Create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest) {
    struct AdjListNode* newNode = (struct AdjListNode*)malloc(sizeof(struct AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}
// Create a graph with V vertices
struct Graph* createGraph(int V) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->V = V;
    graph->array = (struct AdjList*)malloc(V * sizeof(struct AdjList));
    for (int i = 0; i < V; ++i)
        graph->array[i].head = NULL;
    return graph;
}
// Add an edge to the graph
void addEdge(struct Graph* graph, int src, int dest) {
    struct AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;
}
//Function to perform Kahn's algorithm for topological sorting using a vector
void topologicalSort(struct Graph* graph) {
    int V = graph->V;
    int* in_degree = (int*)malloc(V * sizeof(int));
    for (int i = 0; i < V; i++)
        in_degree[i] = 0;
    // Calculate in-degrees of all vertices
    for (int u = 0; u < V; u++) {
        struct AdjListNode* node = graph->array[u].head;
        while (node != NULL) {
            in_degree[node->dest]++;
            node = node->next;
        }
    }
    // Vector to store vertices with in-degree 0
    int* zero_in_degree = (int*)malloc(V * sizeof(int));
    int zero_count = 0;
    for (int i = 0; i < V; i++)
        if (in_degree[i] == 0)
            zero_in_degree[zero_count++] = i;
    int count = 0;
    int* topOrder = (int*)malloc(V * sizeof(int));
    while (zero_count > 0) {
        int u = zero_in_degree[--zero_count];
        topOrder[count++] = u;
        struct AdjListNode* node = graph->array[u].head;
        while (node != NULL) {
            if (--in_degree[node->dest] == 0)
                zero_in_degree[zero_count++] = node->dest;
            node = node->next;
        }
    }
    // Check if there was a cycle
    if (count != V) {
        printf("There exists a cycle in the graph\n");
        return;
    }
    // Print topological order
    for (int i = 0; i < count; i++)
        printf("%d ", topOrder[i]);
    printf("\n");
    // Free allocated memory
    free(in_degree);
    free(zero_in_degree);
    free(topOrder);
}
// Driver program to test the above functions
int main() {
    // Create a graph given in the above diagram
    int V = 6;
    struct Graph* graph = createGraph(V);
    addEdge(graph, 1, 2);
    addEdge(graph, 3, 0);
    addEdge(graph, 4, 0);
    addEdge(graph, 4, 2);
    addEdge(graph, 2, 3);
    addEdge(graph, 4, 1);
    printf("Following is a Topological Sort of the given graph\n");
    topologicalSort(graph);
    return 0;
}   

输出

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

说明

图的表示
图使用邻接表表示。在此表示中，每个顶点都有一个指向它的顶点列表（即其出边）。图结构包含一个邻接表数组，每个列表表示一个顶点的邻居。这是一种表示图的有效方法，尤其是在图稀疏时，因为它使用的内存与边数成正比。
创建图并添加边
图根据给定的顶点数 (V) 进行初始化。为图结构和邻接表数组分配内存。每个列表最初设置为 NULL，表示尚未添加任何边。要从源顶点添加边到目标顶点，会创建一个表示目标顶点的新节点，并将其添加到源顶点的邻接表的开头。
入度计算
使用 in_degree 数组来存储每个顶点的入度。顶点的入度是指它拥有的入边数。最初，所有顶点的入度都设置为零。算法然后遍历每个顶点的邻接表。对于它指向的每个顶点，都会增加相应的入度。此步骤确保了所有顶点的入度都已准确计算。
初始化零入度顶点向量
零入度向量 zero_in_degree 存储入度为零的顶点。这些顶点没有依赖关系，可以立即处理。该向量通过扫描 in_degree 数组并将所有入度为零的顶点添加到其中来初始化。此设置至关重要，因为它确定了拓扑排序的起点。
处理向量
算法进入一个循环，在该循环中它处理 zero_in_degree 向量中的顶点。涉及的步骤是
顶点处理：从向量中移除最后一个顶点并将其添加到拓扑顺序中。
入度更新：算法遍历已处理顶点的邻接表，将其每个相邻顶点的入度减一。如果相邻顶点的入度变为零，则将其添加到 zero_in_degree 向量中。这确保了顶点按正确的顺序处理，保持拓扑排序属性。
循环检测和最终检查
处理完所有顶点后，算法会检查拓扑顺序中的顶点数量是否等于图中的总顶点数。如果计数不匹配，则表示图中存在循环，因为循环会阻止有效的拓扑排序。如果检测到循环，算法会打印一条消息指示其存在。否则，它会打印拓扑顺序。

复杂度分析

时间复杂度

Kahn 算法的时间复杂度可以分解为几个不同的阶段

图表示初始化

创建图并初始化邻接表数组需要 O(V) 时间，其中 V 是顶点的数量。

入度计算

初始化入度数组需要O(V) 时间。

计算入度涉及遍历图的所有边。对于每个顶点，我们遍历其邻接表。操作总数与所有邻接表长度之和成正比，等于边数 (E)。因此，此步骤需要 O(E) 时间。

初始化零入度顶点向量

将所有入度为零的顶点入队需要扫描一次入度数组，耗时O(V) 时间。

处理顶点

每个顶点都处理一次。处理过程包括将顶点添加到拓扑顺序，然后遍历其邻接表以更新其邻居的入度。

对于每个顶点 u，遍历其邻接表并递减其邻居的入度需要 O(degree(u)) 时间，其中 degree(u) 是从顶点 u开始的边数。

因此，处理所有顶点和边的总时间为 O(V)（用于顶点）和 O(E)（用于边），使得此步骤为O(V + E)。

循环检测和最终检查

检查拓扑顺序中的顶点数是否等于总顶点数只需一次简单的比较，耗时 O(1)。

将所有这些步骤结合起来，总时间复杂度为：O(V)+O(E)+O(V)+O(V+E)+O(1)=O(V+E)

因此，使用向量的 Kahn 算法的时间复杂度为 O(V + E)。

空间复杂度

空间复杂度分析考虑了算法中数据结构使用的内存

图的表示

图使用邻接表表示。邻接表数组包含 V 个列表，所有列表中的节点总数为 E。因此，邻接表所需的空间为O(V + E)。

入度数组

使用大小为 V 的数组存储每个顶点的入度，这需要 O(V) 空间。

零入度顶点向量

zero_in_degree 向量存储入度为零的顶点。在最坏的情况下，所有顶点都可能添加到该向量中，这需要O(V) 空间。

拓扑顺序数组

用于存储顶点拓扑顺序的数组也需要 O(V) 空间。

将这些结合起来，算法的总空间复杂度为：O(V+E)+O(V)+O(V)+O(V)=O(V+E)

因此，使用向量的 Kahn 算法的空间复杂度为 O(V + E)。这种线性空间复杂度确保了该算法即使对于大型图也能高效利用内存。

下一主题Scalbn-function-in-c

C 语言 Kahn 算法

Kahn 算法的步骤

方法一：标准队列实现

程序

说明

复杂度分析

方法二：使用向量的 Kahn 算法

程序

说明

复杂度分析

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C 语言教程

C 语言控制语句

C 语言函数

C 语言数组

C 语言指针

C 语言动态内存

C 语言字符串

C 语言数学

C 语言结构体和联合体

C 语言文件处理

C 语言预处理器

C 语言命令行

C 语言程序

C 语言面试

选择题

C 语言编程测试

C 语言基础测试

C 语言控制语句测试

C 语言函数测试

C 语言数组测试

C 语言指针测试

C 语言字符串测试

C 语言结构体测试

C 语言预处理器测试

数学

C 语言杂项

C 语言 Kahn 算法

Kahn 算法的步骤

方法一：标准队列实现

程序

说明

复杂度分析

方法二：使用向量的 Kahn 算法

程序

说明

复杂度分析

相关帖子

C 语言头文件和库的区别

C 语言双指针技术程序

C 语言 complex.h 头文件

C 语言使用指针查找数组中最大元素的程序

C 语言单字母密码程序

C 语言和 C# 的区别

关于 C 语言的有趣事实

在 C 语言的 scanf() 函数中添加空格的效果

C 语言 scalbn() 函数

C 语言锯齿数组或数组的数组

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器