减治法拓扑排序C语言

根据提供的引用内容，减治法拓扑排序是一种基于DFS的算法，可以用于解决拓扑排序问题。下面是一个使用C语言实现减治法拓扑排序的例子：

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 100 // 最大顶点数

typedef struct ArcNode {
    int adjvex; // 邻接点在数组中的位置下标
    struct ArcNode *nextarc; // 指向下一个邻接点的指针
} ArcNode;

typedef struct VNode {
    int data; // 顶点信息
    ArcNode *firstarc; // 指向第一个邻接点的指针
    int indegree; // 顶点的入度
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices; // 邻接表
    int vexnum, arcnum; // 顶点数和弧数
} ALGraph;

// 初始化邻接表
void InitGraph(ALGraph *G) {
    int i;
    G->vexnum = G->arcnum = 0;
    for (i = 0; i < MAX_VERTEX_NUM; i++) {
        G->vertices[i].firstarc = NULL;
        G->vertices[i].indegree = 0;
    }
}

// 添加一条边
void AddArc(ALGraph *G, int u, int v) {
    ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
    p->adjvex = v;
    p->nextarc = G->vertices[u].firstarc;
    G->vertices[u].firstarc = p;
    G->vertices[v].indegree++;
    G->arcnum++;
}

// 减治法拓扑排序
void TopoSort(ALGraph *G) {
    int i, j, k, count = 0;
    int topo[MAX_VERTEX_NUM]; // 存储拓扑序列的数组
    ArcNode *p;
    for (i = 0; i < G->vexnum; i++) {
        if (G->vertices[i].indegree == 0) { // 入度为0的顶点入队
            topo[count++] = i;
        }
    }
    for (i = 0; i < count; i++) { // 依次删除队头顶点及其所有出边
        k = topo[i];
        printf("%d ", G->vertices[k].data); // 输出拓扑序列
        for (p = G->vertices[k].firstarc; p; p = p->nextarc) {
            j = p->adjvex;
            if (--G->vertices[j].indegree == 0) { // 入度为0的顶点入队
                topo[count++] = j;
            }
        }
    }
}

int main() {
    ALGraph G;
    int i, u, v;
    printf("请输入顶点数和弧数：");
    scanf("%d%d", &G.vexnum, &G.arcnum);
    printf("请输入%d个顶点的值：", G.vexnum);
    for (i = 0; i < G.vexnum; i++) {
        scanf("%d", &G.vertices[i].data);
    }
    printf("请输入%d条弧的起点和终点：", G.arcnum);
    for (i = 0; i < G.arcnum; i++) {
        scanf("%d%d", &u, &v);
        AddArc(&G, u, v);
    }
    printf("拓扑序列为：");
    TopoSort(&G);
    printf("\n");
    return 0;
}