數據結構進階：C 語言實現圖的鄰接表存儲與 DFS/BFS 遍歷完整版

編輯：關於C語言

數據結構進階：C 語言實現圖的鄰接表存儲與 DFS/BFS 遍歷完整版

鄰接表是稀疏圖首選存儲結構，空間 O(V+E)。本文提供工業級完整實現：支持有向/無向、圖/網（帶權）、頂點字符串標識，包含創建、銷毀、增刪頂點邊、DFS/BFS 遍歷、顯示等全套操作，代碼模塊化、健壯性強。

核心數據結構設計

#define MAX_VERTEX_NUM 20
#define MAX_NAME 3

typedef enum { DG, DN, AG, AN } GraphKind; // 有向圖/網、無向圖/網
typedef char VertexType[MAX_NAME];
typedef int InfoType; // 權值類型

// 弧結點
typedef struct ArcNode {
    int adjvex;              // 目標頂點下標
    struct ArcNode *nextarc; // 下一條弧
    InfoType *info;          // 權值指針（網用）
} ArcNode;

// 頂點結點（鏈表頭）
typedef struct VNode {
    VertexType data;         // 頂點名
    ArcNode *firstarc;       // 第一條弧
} VNode, AdjList[MAX_VERTEX_NUM];

// 圖結構
typedef struct {
    AdjList vertices;
    int vexnum, arcnum;
    int kind;                // GraphKind
} ALGraph;

核心操作精選

1. 定位頂點

int LocateVex(ALGraph G, VertexType u) {
    for (int i=0; i

2. 創建圖（交互式，支持四種類型）
int CreateGraph(ALGraph *G) {
    // ...輸入 kind, vexnum, arcnum...
    // 初始化頂點鏈表頭
    for (int i=0; ivexnum; i++) {
        scanf("%s", G->vertices[i].data);
        G->vertices[i].firstarc = NULL;
    }
    // 輸入邊並調用 InsertArc
    for (int k=0; karcnum; k++) {
        scanf("%s%s", v1, v2);
        InsertArc(G, v1, v2); // 內部處理權值輸入、無向雙向插入
    }
    return 1;
}

3. 深度優先遍歷（遞歸）
void DFS(ALGraph G, int v) {
    visited[v] = 1;
    VisitFunc(G.vertices[v].data);
    for (int w = FirstAdjVex(G, G.vertices[v].data); w >= 0;
         w = NextAdjVex(G, G.vertices[v].data, G.vertices[w].data))
        if (!visited[w]) DFS(G, w);
}

void DFSTraverse(ALGraph G, void(*Visit)(char*)) {
    VisitFunc = Visit;
    memset(visited, 0, sizeof(visited));
    for (int v=0; v

4. 廣度優先遍歷（鏈隊列輔助）
void BFSTraverse(ALGraph G, void(*Visit)(char*)) {
    LinkQueue Q; InitQueue(&Q);
    memset(visited, 0, sizeof(visited));
    for (int v=0; v=0; w=NextAdjVex(...))
                if (!visited[w]) { visited[w]=1; Visit(...); EnQueue(&Q, w); }
        }
    }
}

5. 顯示鄰接表（區分圖/網、有向/無向）
void Display(ALGraph G) {
    // ...輸出類型、頂點集...
    for (int i=0; iadjvex].data);
                if (G.kind==DN) printf(":%d", *(p->info));
            } else { // 無向，避免重複輸出
                if (i < p->adjvex) {
                    printf("%s-%s", G.vertices[i].data, G.vertices[p->adjvex].data);
                    if (G.kind==AN) printf(":%d", *(p->info));
                }
            }
            p = p->nextarc;
        }
        printf("\n");
    }
}

運行效果


工程化亮點

統一錯誤碼：所有操作返回 int（1 成功/0 失敗），便於上層判斷。
內存管理嚴謹：DestroyGraph 遞歸釋放弧結點及權值內存；DeleteVex 同步修正後續頂點下標與弧結點 adjvex。
泛型訪問接口：遍歷函數接受函數指針 Visit，解耦業務邏輯。
隊列獨立實現：鏈式隊列 LinkQueue 封裝完整，可復用。


適用場景對比

結構 空間 查邊 遍歷 增刪頂點 適用
鄰接矩陣 O(V²) O(1) O(V²) 困難 稠密圖、矩陣算法
鄰接表 O(V+E) O(deg) O(V+E) 容易 稀疏圖、頻繁修改拓撲