#include "stdio.h" #include "stdlib.h" #include "malloc.h" #define Null 0 #define MAX 20 typedef struct ArcNode { int adjvex; int weight; struct ArcNode *nextarc; }ArcNode,*AdjList; typedef struct Graph { AdjList elem[MAX+1]; int vexnum; int arcnum; int GraphKind; }Graph; typedef struct Stack { int s[MAX]; int top; }Stack; void initStack(Stack *s) { (*s).top=0; } int Push(Stack *s, int e) { if((*s).top>=MAX) return 0; else (*s).s[(*s).top++]=e; } int Pop(Stack *s, int *e) { if((*s).top<=0) return 0; else *e=(*s).s[--(*s).top]; } int StackEmpty(Stack s) { if(s.top==0)return 1; else return 0; } void create(Graph *G) { int i, start, end; AdjList p; for(i=0;i<=MAX;i++) (*G).elem[i]=Null; for(i=1;i<=(*G).arcnum;i++) { scanf("%d,%d",&start,&end); p=(AdjList)malloc(sizeof(ArcNode)); p->adjvex=end; p->nextarc=(*G).elem[start]; (*G).elem[start]=p; if((*G).GraphKind==0) { p=(AdjList)malloc(sizeof(ArcNode)); p->adjvex=start; p->nextarc=(*G).elem[end]; (*G).elem[end]=p; } } } int TopoSort(Graph G) { } main() { Graph G; printf("Please input the number of vex, arc and GraphKind:"); scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&G.GraphKind); create(&G); printf("The outcome of TopoSort is:\n"); TopoSort(G); }

这段代码是一个基于邻接表存储结构的有向图的拓扑排序的程序框架。但是其中的 TopoSort 函数还没有实现，需要我们来完成。

拓扑排序的算法是基于 Kahn 算法的。其基本思想是不断地选择入度为 0 的顶点，并将其从图中删除，直到所有顶点都被选择为止。在实现过程中，我们需要使用一个队列来存储入度为 0 的顶点。

在这个程序中，我们可以将入度为 0 的顶点入栈，然后依次出栈并处理它们的邻接节点，更新它们的入度。具体实现细节可以参考下面的代码。

int TopoSort(Graph G) {
    int i, e, cnt = 0;
    int *indegree = (int *)malloc(sizeof(int) * (G.vexnum + 1));
    Stack s;
    initStack(&s);
    for (i = 1; i <= G.vexnum; i++) {
        indegree[i] = 0;
    }
    for (i = 1; i <= G.vexnum; i++) {
        AdjList p = G.elem[i];
        while (p != Null) {
            indegree[p->adjvex]++;
            p = p->nextarc;
        }
    }
    for (i = 1; i <= G.vexnum; i++) {
        if (indegree[i] == 0) {
            Push(&s, i);
        }
    }
    while (!StackEmpty(s)) {
        Pop(&s, &e);
        printf("%d ", e);
        cnt++;
        AdjList p = G.elem[e];
        while (p != Null) {
            indegree[p->adjvex]--;
            if (indegree[p->adjvex] == 0) {
                Push(&s, p->adjvex);
            }
            p = p->nextarc;
        }
    }
    if (cnt != G.vexnum) {
        printf("Error: the graph has a cycle.\n");
        return 0;
    }
    return 1;
}

上面的代码实现了基于邻接表存储结构的有向图的拓扑排序。其中使用了一个栈来存储入度为 0 的顶点，使用了一个数组来存储每个顶点的入度。如果拓扑排序成功，会输出拓扑排序序列；如果图中存在环，会输出错误信息。

完整的程序如下：

#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"

#define Null 0
#define MAX 20

typedef struct ArcNode {
    int adjvex;
    int weight;
    struct ArcNode *nextarc;
} ArcNode, *AdjList;

typedef struct Graph {
    AdjList elem[MAX + 1];
    int vexnum;
    int arcnum;
    int GraphKind;
} Graph;

typedef struct Stack {
    int s[MAX];
    int top;
} Stack;

void initStack(Stack *s) {
    (*s).top = 0;
}

int Push(Stack *s, int e) {
    if ((*s).top >= MAX)
        return 0;
    else
        (*s).s[(*s).top++] = e;
}

int Pop(Stack *s, int *e) {
    if ((*s).top <= 0)
        return 0;
    else
        *e = (*s).s[--(*s).top];
}

int StackEmpty(Stack s) {
    if (s.top == 0)
        return 1;
    else
        return 0;
}

void create(Graph *G) {
    int i, start, end;
    AdjList p;
    for (i = 0; i <= MAX; i++)
        (*G).elem[i] = Null;
    for (i = 1; i <= (*G).arcnum; i++) {
        scanf("%d,%d", &start, &end);
        p = (AdjList) malloc(sizeof(ArcNode));
        p->adjvex = end;
        p->nextarc = (*G).elem[start];
        (*G).elem[start] = p;
        if ((*G).GraphKind == 0) {
            p = (AdjList) malloc(sizeof(ArcNode));
            p->adjvex = start;
            p->nextarc = (*G).elem[end];
            (*G).elem[end] = p;
        }
    }
}

int TopoSort(Graph G) {
    int i, e, cnt = 0;
    int *indegree = (int *) malloc(sizeof(int) * (G.vexnum + 1));
    Stack s;
    initStack(&s);
    for (i = 1; i <= G.vexnum; i++) {
        indegree[i] = 0;
    }
    for (i = 1; i <= G.vexnum; i++) {
        AdjList p = G.elem[i];
        while (p != Null) {
            indegree[p->adjvex]++;
            p = p->nextarc;
        }
    }
    for (i = 1; i <= G.vexnum; i++) {
        if (indegree[i] == 0) {
            Push(&s, i);
        }
    }
    while (!StackEmpty(s)) {
        Pop(&s, &e);
        printf("%d ", e);
        cnt++;
        AdjList p = G.elem[e];
        while (p != Null) {
            indegree[p->adjvex]--;
            if (indegree[p->adjvex] == 0) {
                Push(&s, p->adjvex);
            }
            p = p->nextarc;
        }
    }
    if (cnt != G.vexnum) {
        printf("Error: the graph has a cycle.\n");
        return 0;
    }
    return 1;
}

int main() {
    Graph G;
    printf("Please input the number of vex, arc and GraphKind:");
    scanf("%d,%d,%d", &G.vexnum, &G.arcnum, &G.GraphKind);
    create(&G);
    printf("The outcome of TopoSort is:\n");
    TopoSort(G);
    return 0;
}