C 語言實現圖結構：鄰接矩陣存儲與無向網創建完整代碼

圖的存儲結構對比

本文實現鄰接矩陣，支持有向/無向、帶權/不帶權四種圖類型。

核心數據結構定義

#define MAX_VERTEX_NUM 100
#define MAX_NAME 32
#define MAX_INFO 100

typedef int VRType;           // 頂點關係類型：無權圖用 0/1，帶權圖用權值
typedef char InfoType;        // 弧的附加信息
typedef char *VertexType;     // 頂點數據類型

typedef enum { DG, DN, UDG, UDN } GraphKind;  // 有向圖、有向網、無向圖、無向網

typedef struct {
    VRType adj;               // 權值或關係
    InfoType *info;           // 附加信息指針
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct {
    VertexType vexs[MAX_VERTEX_NUM];  // 頂點向量
    AdjMatrix arcs;                   // 鄰接矩陣
    int vexnum, arcnum;               // 頂點數、弧數
    GraphKind kind;                   // 圖類型
} MGraph;

輔助函數：頂點定位

int LocateVex(MGraph G, VertexType v) {
    for (int i = 0; i < G.vexnum; i++) {
        if (strcmp(v, G.vexs[i]) == 0) return i;
    }
    return -1;  // 未找到
}

無向網 (UDN) 創建算法

int CreateUDN(MGraph *G) {
    int i, j, k, w, IncInfo;
    char s[MAX_INFO];
    char va[MAX_NAME], vb[MAX_NAME];
    
    printf("輸入頂點數、弧數、弧是否含附加信息(1/0): ");
    scanf("%d %d %d", &G->vexnum, &G->arcnum, &IncInfo);
    
    /* 1. 輸入頂點信息 */
    printf("輸入 %d 個頂點值(每個<%d字符):\n", G->vexnum, MAX_NAME);
    for (i = 0; i < G->vexnum; i++) {
        G->vexs[i] = malloc(MAX_NAME);
        scanf("%s", G->vexs[i]);
        getchar();  // 吸收換行
    }
    
    /* 2. 初始化鄰接矩陣 */
    for (i = 0; i < G->vexnum; i++)
        for (j = 0; j < G->vexnum; j++) {
            G->arcs[i][j].adj = 0;      // 無權圖用 0 表示無邊，帶權用 0/INF
            G->arcs[i][j].info = NULL;
        }
    
    /* 3. 輸入弧信息 */
    printf("輸入 %d 條弧 (弧尾 弧頭 權值):\n", G->arcnum);
    for (k = 0; k < G->arcnum; k++) {
        scanf("%s %s %d", va, vb, &w);
        getchar();
        
        i = LocateVex(*G, va);
        j = LocateVex(*G, vb);
        if (i == -1 || j == -1) { k--; continue; }  // 重新輸入
        
        G->arcs[i][j].adj = w;  // 無向網：對稱設置
        G->arcs[j][i].adj = w;
        
        if (IncInfo) {
            printf("輸入弧附加信息(<%d字符): ", MAX_INFO);
            fgets(s, MAX_INFO, stdin);
            s[strcspn(s, "\n")] = '\0';  // 去除換行
            if (strlen(s) > 0) {
                G->arcs[i][j].info = malloc(strlen(s) + 1);
                strcpy(G->arcs[i][j].info, s);
                G->arcs[j][i].info = G->arcs[i][j].info;  // 共享信息
            }
        }
    }
    G->kind = UDN;
    return 1;
}

其他三種圖的創建差異

圖的銷毀與內存釋放

void DestroyGraph(MGraph *G) {
    for (int i = 0; i < G->vexnum; i++) {
        free(G->vexs[i]);
        for (int j = 0; j < G->vexnum; j++) {
            if (G->arcs[i][j].info) {
                // 注意：無向圖 info 可能被雙向共享，避免雙重 free
                if (i <= j) free(G->arcs[i][j].info);
            }
        }
    }
    G->vexnum = G->arcnum = 0;
}

遍歷算法框架 (DFS/BFS)

void DFS(MGraph G, int v, int visited[]) {
    visited[v] = 1;
    printf("%s ", G.vexs[v]);
    for (int w = 0; w < G.vexnum; w++) {
        if (G.arcs[v][w].adj != 0 && !visited[w])
            DFS(G, w, visited);
    }
}

void BFSTraverse(MGraph G) {
    int visited[MAX_VERTEX_NUM] = {0};
    int queue[MAX_VERTEX_NUM], front = 0, rear = 0;
    
    for (int i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            visited[i] = 1;
            printf("%s ", G.vexs[i]);
            queue[rear++] = i;
            
            while (front < rear) {
                int v = queue[front++];
                for (int w = 0; w < G.vexnum; w++) {
                    if (G.arcs[v][w].adj != 0 && !visited[w]) {
                        visited[w] = 1;
                        printf("%s ", G.vexs[w]);
                        queue[rear++] = w;
                    }
                }
            }
        }
    }
}

測試主程序

int main() {
    MGraph G;
    CreateUDN(&G);
    
    printf("\n鄰接矩陣 (權值):\n");
    for (int i = 0; i < G.vexnum; i++) {
        for (int j = 0; j < G.vexnum; j++)
            printf("%3d ", G.arcs[i][j].adj);
        printf("\n");
    }
    
    printf("\nDFS 遍歷: ");
    int visited[MAX_VERTEX_NUM] = {0};
    for (int i = 0; i < G.vexnum; i++)
        if (!visited[i]) DFS(G, i, visited);
    
    printf("\nBFS 遍歷: ");
    BFSTraverse(G);
    
    DestroyGraph(&G);
    return 0;
}

輸入示例與輸出

輸入:
4 5 0
A
B
C
D
A B 10
A C 20
B C 5
B D 15
C D 30

輸出鄰接矩陣:
  0  10  20   0
 10   0   5  15
 20   5   0  30
  0  15  30   0

DFS 遍歷: A B C D
BFS 遍歷: A B C D