圖的鄰接矩陣存儲與 DFS/BFS 遍歷：C 語言完整實現詳解

數據結構定義

#define MAXV 20
typedef char VertexType;

typedef struct {
    VertexType vex[MAXV];           // 頂點表
    int arc[MAXV][MAXV];            // 鄰接矩陣
    int vexNum, arcNum;             // 頂點數、邊數
} Graph;

核心操作實現

1. 無向圖創建

輸入頂點數、邊數、頂點值、邊的兩端點，矩陣對稱置 1。

2. 深度優先搜索（DFS）遞歸版

int visited[MAXV];
void DFS(Graph G, int v) {
    visited[v] = 1;
    printf("%c ", G.vex[v]);
    for (int w = 0; w < G.vexNum; w++)
        if (G.arc[v][w] && !visited[w])
            DFS(G, w);
}
void DFSTraverse(Graph G) {
    for (int i = 0; i < G.vexNum; i++) visited[i] = 0;
    for (int i = 0; i < G.vexNum; i++)
        if (!visited[i]) DFS(G, i);
}

3. 廣度優先搜索（BFS）隊列版

typedef struct { int data[MAXV]; int front, rear; } Queue;

void BFSTraverse(Graph G) {
    for (int i = 0; i < G.vexNum; i++) visited[i] = 0;
    Queue q = {0, 0};
    for (int i = 0; i < G.vexNum; i++) {
        if (!visited[i]) {
            visited[i] = 1; q.data[q.rear++] = i;
            while (q.front != q.rear) {
                int v = q.data[q.front++];
                printf("%c ", G.vex[v]);
                for (int w = 0; w < G.vexNum; w++)
                    if (G.arc[v][w] && !visited[w]) {
                        visited[w] = 1;
                        q.data[q.rear++] = w;
                    }
            }
        }
    }
}

關鍵點對比

測試輸出示例

輸入頂點 A B C D，邊 A-B, A-C, B-D, C-D
DFS: A B D C
BFS: A B C D