C語言實現AOV網拓撲排序：有向無環圖線性化核心算法

編輯：關於C語言

AOV網拓撲排序C語言實現：從鄰接表到線性序列的完整指南

AOV網(Activity On Vertex Network)中頂點代表活動，有向邊代表先後依賴關係。拓撲排序將偏序集轉換為線性序列，是編譯器依賴分析、構建系統、課程規劃等領域的核心算法。本文提供基於鄰接表的完整C語言實現，包含圖構建、入度計算、棧式拓撲排序及環檢測全流程。

核心數據結構

// 定位頂點索引
int LocateVex(ALGraph *G, char *name) {
    for (int i = 0; i < G->vexNum; i++)
        if (strcmp(G->vertices[i].data, name) == 0) return i;
    return -1;
}

// 創建圖(支持4種類型)
int CreateGraph(ALGraph *G) {
    printf("圖類型(0有向圖 1有向網 2無向圖 3無向網): ");
    scanf("%d", &G->kind);
    
    printf("頂點數 邊數: ");
    scanf("%d %d", &G->vexNum, &G->arcNum);
    
    printf("輸入%d個頂點名(<%d字符): ", G->vexNum, MAX_NAME_LEN);
    for (int i = 0; i < G->vexNum; i++) {
        scanf("%s", G->vertices[i].data);
        G->vertices[i].first = NULL;
    }
    
    if (G->kind == 1 || G->kind == 3) // 網
        printf("輸入每條邊: 權值 起點 終點\n");
    else
        printf("輸入每條邊: 起點 終點\n");
    
    for (int k = 0; k < G->arcNum; k++) {
        int w; char va[MAX_NAME_LEN], vb[MAX_NAME_LEN];
        if (G->kind == 1 || G->kind == 3)
            scanf("%d %s %s", &w, va, vb);
        else
            scanf("%s %s", va, vb);
        
        int i = LocateVex(G, va);
        int j = LocateVex(G, vb);
        if (i == -1 || j == -1) return 0;
        
        // 插入邊 i->j
        ArcNode *p = malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->info = (G->kind == 1 || G->kind == 3) ? malloc(sizeof(int)) : NULL;
        if (p->info) *p->info = w;
        p->next = G->vertices[i].first;
        G->vertices[i].first = p;
        
        // 無向圖/網添加反向邊
        if (G->kind >= 2) {
            ArcNode *q = malloc(sizeof(ArcNode));
            q->adjvex = i;
            q->info = (G->kind == 3) ? malloc(sizeof(int)) : NULL;
            if (q->info) *q->info = w;
            q->next = G->vertices[j].first;
            G->vertices[j].first = q;
        }
    }
    return 1;
}

棧輔助結構(順序棧)

// 計算所有頂點入度
void CalcInDegree(ALGraph *G, int *indeg) {
    for (int i = 0; i < G->vexNum; i++) indeg[i] = 0;
    for (int i = 0; i < G->vexNum; i++) {
        ArcNode *p = G->vertices[i].first;
        while (p) {
            indeg[p->adjvex]++;
            p = p->next;
        }
    }
}

// 拓撲排序主函數
int TopologicalSort(ALGraph *G) {
    int indeg[MAX_VERTICES];
    CalcInDegree(G, indeg);
    
    SqStack S;
    InitStack(&S);
    
    // 入度為0的頂點入棧
    for (int i = 0; i < G->vexNum; i++)
        if (indeg[i] == 0) Push(&S, i);
    
    int count = 0;
    printf("拓撲序列: ");
    
    while (!StackEmpty(&S)) {
        int u;
        Pop(&S, &u);
        printf("%s ", G->vertices[u].data);
        count++;
        
        // 遍歷u的出邊，減少終點入度
        ArcNode *p = G->vertices[u].first;
        while (p) {
            int v = p->adjvex;
            if (--indeg[v] == 0) Push(&S, v);
            p = p->next;
        }
    }
    
    printf("\n");
    
    if (count < G->vexNum) {
        printf("圖中存在環，無法拓撲排序\n");
        return 0;
    }
    printf("有效拓撲序列\n");
    return 1;
}

圖的輸出顯示

kind], G->vexNum, G->arcNum);
    
    for (int i = 0; i < G->vexNum; i++) {
        ArcNode *p = G->vertices[i].first;
        while (p) {
            if (G->kind <= 1) { // 有向
                printf("%s->%s", G->vertices[i].data, G->vertices[p->adjvex].data);
                if (G->kind == 1) printf(":%d", *p->info);
            } else { // 無向，避免重複輸出
                if (i < p->adjvex) {
                    printf("%s--%s", G->vertices[i].data, G->vertices[p->adjvex].data);
                    if (G->kind == 3) printf(":%d", *p->info);
                }
            }
            p = p->next;
        }
        printf("\n");
    }
}

完整主程序與測試

運行結果

測試用例與結果

輸入:
圖類型: 0 (有向圖)
頂點數: 6, 邊數: 7
頂點: V0 V1 V2 V3 V4 V5
邊:
V0 V1
V0 V2
V1 V3
V2 V3
V3 V4
V2 V5
V4 V5

輸出:
有向圖: 6頂點 7邊
V0->V1
V0->V2
V1->V3
V2->V3
V2->V5
V3->V4
V4->V5

拓撲序列: V0 V1 V2 V3 V4 V5
有效拓撲序列

算法複雜度與正確性證明

指標	複雜度	說明
時間	O(V+E)	每頂點入棧出棧一次，每邊遍歷一次
空間	O(V)	入度數組、棧、拓撲序列
正確性	保證	若無環，必存在入度0頂點；移除後子圖仍無環