1、用邻接表存储有向图; 2、程序模块清晰,输出该图的拓扑排序结果。3C语言实现,完整代码
时间: 2024-12-26 18:28:11 浏览: 0
1. 使用邻接表存储有向图是一种常见的图数据结构表示方法。在邻接表中,每个顶点对应一个链表,链表中的元素是与其相邻的所有边的目标顶点。这种方式对于稀疏图(即边的数量远小于顶点数的平方)非常高效,因为不需要为每一对可能的顶点都分配空间。在邻接表中,查找从一个顶点到另一个顶点是否存在边的时间复杂度通常是O(1)。
2. 程序模块清晰地进行有向图的拓扑排序,通常需要分步操作:
a. 首先,识别出所有的入度为0的顶点(也称为源节点),将其添加到结果列表中。
b. 对于每一步,从结果列表中移除最后一个加入的顶点,并更新其邻居的入度减一。
c. 如果发现新的入度为0的顶点,则再次将其添加到结果列表中。
d. 这个过程会一直持续,直到所有顶点都被处理过,或者无法找到新的源节点,这时如果存在未处理的顶点则说明图中有环,无法进行拓扑排序。
以下是简单的C语言实现(假设我们有一个名为AdjacencyList的邻接表结构体,其中包含顶点数组和邻接边数组):
```c
#include <stdio.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
typedef struct AdjList {
Node** adj;
int num_vertices;
} AdjList;
void add_edge(AdjList* graph, int src, int dest) {
graph->adj[src] = (Node*)malloc(sizeof(Node));
graph->adj[src]->data = dest;
graph->adj[src]->next = NULL;
}
void topological_sort(AdjList* graph, int vertices, int* result, int* indegree) {
for(int i = 0; i < vertices; ++i) {
if(indegree[i] == 0) {
dfs(graph, i, vertices, result, indegree);
}
}
}
void dfs(AdjList* graph, int vertex, int vertices, int* result, int* indegree) {
result[vertices - 1] = vertex;
*indegree[vertex]--;
Node* curr = graph->adj[vertex];
while(curr != NULL) {
(*indegree[curr->data])--;
dfs(graph, curr->data, vertices, result, indegree);
curr = curr->next;
}
}
int main() {
// 初始化图和数组...
// 添加边...
int vertices = ...;
int indegree[vertices] = {0};
int* result = malloc(vertices * sizeof(int));
topological_sort(...);
// 输出结果
printf("拓扑排序结果: ");
for(int i = 0; i < vertices; ++i) {
printf("%d ", result[i]);
}
free(result);
return 0;
}
```
注意:由于实际的代码长度和细节较多,这里给出的是核心部分,实际应用中还需要完善输入输出、错误处理和邻接表的初始化等部分。
阅读全文