數據結構核心：C 語言實現圖的鄰接矩陣存儲與基本操作

編輯：關於C語言

數據結構核心：C 語言實現圖的鄰接矩陣存儲與基本操作

鄰接矩陣是圖存儲最直觀的結構，適合稠密圖、頻繁查詢邊是否存在的場景。本文給出完整 C 實現：結構定義、創建（有向/無向）、打印、頂點定位，代碼規範、可直接編譯運行。

核心數據結構

#define MAX_VEX_NUM 50
typedef char VertexType;
typedef enum { DG, UDG } GraphType; // 有向圖、無向圖

typedef struct {
    VertexType vexs[MAX_VEX_NUM];      // 頂點表
    int arcs[MAX_VEX_NUM][MAX_VEX_NUM]; // 鄰接矩陣，0/1 表示無/有邊
    int vexnum, arcnum;                // 頂點數、邊數
    GraphType type;                    // 圖類型
} MGraph;

關鍵操作實現

1. 頂點定位

int getIndexOfVexs(char vex, MGraph *MG) {
    for (int i = 1; i <= MG->vexnum; i++)
        if (MG->vexs[i] == vex) return i;
    return 0; // 未找到
}

2. 創建圖（交互式輸入）

void create_MG(MGraph *MG) {
    int type, v1, v2; char c1, c2;
    printf("圖類型 DG(0)/UDG(1): "); scanf("%d", &type);
    MG->type = (type==0)?DG:UDG;
    printf("頂點數: "); scanf("%d", &MG->vexnum);
    printf("邊數: "); scanf("%d", &MG->arcnum); getchar();
    for (int i=1; i<=MG->vexnum; i++) {
        printf("第%d個頂點字符: ", i); scanf("%c", &MG->vexs[i]); getchar();
    }
    // 初始化矩陣
    for (int i=1; i<=MG->vexnum; i++)
        for (int j=1; j<=MG->vexnum; j++)
            MG->arcs[i][j] = 0;
    // 輸入邊
    for (int k=1; k<=MG->arcnum; k++) {
        printf("第%d條邊 起點 終點: ", k); scanf("%c %c", &c1, &c2);
        v1 = getIndexOfVexs(c1, MG); v2 = getIndexOfVexs(c2, MG);
        if (MG->type == UDG) MG->arcs[v1][v2] = MG->arcs[v2][v1] = 1;
        else MG->arcs[v1][v2] = 1;
        getchar();
    }
}

3. 打印圖信息

void print_MG(MGraph MG) {
    printf("類型: %s\n", MG.type==DG?"有向圖":"無向圖");
    printf("頂點數: %d, 邊數: %d\n", MG.vexnum, MG.arcnum);
    printf("頂點集: "); for (int i=1;i<=MG.vexnum;i++) printf("%c ", MG.vexs[i]); printf("\n");
    printf("鄰接矩陣:\n");
    for (int i=1; i<=MG.vexnum; i++) {
        for (int j=1; j<=MG.vexnum; j++) printf("%d ", MG.arcs[i][j]);
        printf("\n");
    }
}

運行效果示例

優缺點分析與適用場景

優點	缺點	適用場景
判斷邊存在 O(1)	空間 O(V²)，稀疏圖浪費大	稠密圖、頻繁查邊、矩陣運算（如 Floyd）
實現簡單、易理解	增刪頂點需移動矩陣，代價高	頂點數固定、較小（<500）的圖