选择合适的结构表示图,在此基础上实现拓扑排序算法。 要求:对所设计的图结构,提供必要的基本功能,用c语言实现
时间: 2023-12-14 10:36:15 浏览: 82
以下是使用邻接表表示图的拓扑排序算法实现,其中包括了图的初始化、添加边、拓扑排序等基本功能。
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100
typedef struct Node {
int adjvex; // 邻接点下标
struct Node *next; // 指向下一个邻接点的指针
} Node;
typedef struct Vertex {
int data; // 顶点数据
Node *first; // 指向第一个邻接点的指针
int inDegree; // 入度
} Vertex;
typedef struct Graph {
Vertex vertexes[MAX_VERTEX_NUM]; // 顶点数组
int vertexNum; // 顶点数
int edgeNum; // 边数
} Graph;
// 初始化图
void initGraph(Graph *graph, int vertexNum) {
graph->vertexNum = vertexNum;
graph->edgeNum = 0;
for (int i = 0; i < vertexNum; i++) {
graph->vertexes[i].data = i;
graph->vertexes[i].first = NULL;
graph->vertexes[i].inDegree = 0;
}
}
// 添加边
void addEdge(Graph *graph, int start, int end) {
Node *node = (Node *)malloc(sizeof(Node));
node->adjvex = end;
node->next = graph->vertexes[start].first;
graph->vertexes[start].first = node;
graph->vertexes[end].inDegree++;
graph->edgeNum++;
}
// 拓扑排序
void topoSort(Graph *graph) {
int *queue = (int *)malloc(graph->vertexNum * sizeof(int));
int front = 0, rear = 0;
int count = 0; // 记录已经输出的顶点数
for (int i = 0; i < graph->vertexNum; i++) {
if (graph->vertexes[i].inDegree == 0) {
queue[rear++] = i; // 将入度为0的顶点入队
}
}
while (front != rear) {
int cur = queue[front++]; // 出队
printf("%d ", cur);
count++;
for (Node *p = graph->vertexes[cur].first; p != NULL; p = p->next) {
int adjvex = p->adjvex;
graph->vertexes[adjvex].inDegree--;
if (graph->vertexes[adjvex].inDegree == 0) {
queue[rear++] = adjvex;
}
}
}
if (count != graph->vertexNum) {
printf("Error: Graph has a cycle.\n");
}
}
int main() {
Graph graph;
int vertexNum = 6;
initGraph(&graph, vertexNum);
addEdge(&graph, 0, 1);
addEdge(&graph, 0, 3);
addEdge(&graph, 1, 2);
addEdge(&graph, 1, 3);
addEdge(&graph, 3, 2);
addEdge(&graph, 3, 4);
addEdge(&graph, 4, 2);
topoSort(&graph);
return 0;
}
```
上述代码中,使用邻接表表示图,其中每个顶点包含一个指向第一个邻接点的指针和入度,每个邻接点包含邻接点下标和指向下一个邻接点的指针。初始化图时,将每个顶点的邻接点指针和入度都初始化为0。添加边时,将边连接的两个顶点的邻接表和入度更新。拓扑排序时,先将入度为0的顶点加入到队列中,然后从队列中取出一个顶点,输出该顶点,并将该顶点的邻接点的入度减一,如果减为0则加入到队列中。重复这个过程直到队列为空,如果输出的顶点数不等于图的顶点数,则说明图有环。
阅读全文