一.实验目的
1.理解拓扑排序的特性和算法;
2.通过构造图的邻接表,掌握拓扑排序算法。
二.实验内容
1.建立邻接表存储的图;
2.对图进行拓扑排序;
3.输出拓扑排序序列。
三.代码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXSIZE 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAX_VERTEX_NUM 20
typedef int Elemtype;
typedef struct {
Elemtype data[MAXSIZE];
int top;
} SqStack;
int InitStack(SqStack &S) {
S.top = -1;
return OK;
}
int StackEmpty(SqStack S) {
return (S.top == -1 ? TRUE : FALSE);
}
int StackFull(SqStack S) {
return (S.top == MAXSIZE - 1 ? TRUE : FALSE);
}
int Push(SqStack &S, Elemtype e) {
if (StackFull(S)) return ERROR;
S.top++;
S.data[S.top] = e;
return OK;
}
int Pop(SqStack &S, Elemtype &e) {
if (StackEmpty(S)) return ERROR;
e = S.data[S.top];
S.top--;
return OK;
}
typedef struct ArcNode {
int adjvex;
struct ArcNode *nextarc;
char *info;
} ArcNode;
typedef struct VNode {
int data;
ArcNode *firstarc;
} VNode;
typedef struct {
VNode vertexs[MAX_VERTEX_NUM];
int vexnum, arcnum;
char kind;
} ALGraph;
void FindInDegree(ALGraph G, int indegree[]) {
for (int i = 0; i < G.vexnum; i++) indegree[i] = 0;
for (int i = 0; i < G.vexnum; i++) {
ArcNode *p = G.vertexs[i].firstarc;
while (p) {
int k = p->adjvex;
indegree[k]++;
p = p->nextarc;
}
}
}
int TopologicalSort(ALGraph G) {
int indegree[MAX_VERTEX_NUM];
FindInDegree(G, indegree);
SqStack S;
InitStack(S);
int count = 0;
for (int i = 0; i < G.vexnum; i++) {
if (indegree[i] == 0) Push(S, i);
}
while (!StackEmpty(S)) {
int n;
Pop(S, n);
printf("%d ", G.vertexs[n].data);
count++;
ArcNode *p;
for (p = G.vertexs[n].firstarc; p != NULL; p = p->nextarc) {
int k = p->adjvex;
if (!(--indegree[k])) Push(S, k);
}
}
if (count < G.vexnum) return FALSE;
else return TRUE;
}
void CreateGraph(ALGraph &G) {
G.kind = 'D';
printf("请输入顶点数和边数:");
scanf("%d%d", &G.vexnum, &G.arcnum);
printf("请输入各个顶点的值:\n");
for (int i = 0; i < G.vexnum; i++) {
printf("第 %d 个顶点的值:", i + 1);
scanf("%d", &G.vertexs[i].data);
G.vertexs[i].firstarc = NULL;
}
int u, v;
for (int i = 0; i < G.arcnum; i++) {
printf("请输入第 %d 条边的两个端点:", i + 1);
scanf("%d%d", &u, &v);
ArcNode *p = (ArcNode *) malloc(sizeof(ArcNode));
p->adjvex = v;
p->info = NULL;
p->nextarc = G.vertexs[u].firstarc;
G.vertexs[u].firstarc = p;
}
}
void PrintAL(ALGraph G) {
printf("各个顶点的邻接表如下:\n");
for (int i = 0; i < G.vexnum; i++) {
printf("[%d] %d ->", i, G.vertexs[i].data);
ArcNode *p = G.vertexs[i].firstarc;
while (p != NULL) {
printf(" %d", p->adjvex);
p = p->nextarc;
}
printf("\n");
}
}
int main() {
ALGraph G;
CreateGraph(G);
printf("初始图:\n");
PrintAL(G);
printf("拓扑排序:\n");
TopologicalSort(G);
return 0;
}
标签:return,int,拓扑,----,++,ArcNode,printf,数据结构,vertexs
From: https://blog.csdn.net/2301_79235379/article/details/140863385