您现在的位置：程式碼之家 >> 編程語言 > >> 更多程式語言 >> 程式設計綜合問答

圖的鄰接矩陣存儲：DFS/BFS 遍歷完整 C 代碼實現

編輯：程式設計綜合問答

問題

無向圖用鄰接矩陣存儲，從任意頂點進行深度優先（DFS）和廣度優先（BFS）遍歷。

數據結構定義

#define MAXV 100
#define INF 0x3f3f3f3f

typedef struct {
    int edges[MAXV][MAXV]; // 鄰接矩陣，0/1 或權重
    int n, e;              // 頂點數、邊數
    char vexs[MAXV];       // 頂點信息（可選）
} MGraph;

創建圖（示例）

void CreateGraph(MGraph *G) {
    G->n = 5; G->e = 6;
    char vertices[] = {'A','B','C','D','E'};
    memcpy(G->vexs, vertices, G->n);
    
    // 初始化矩陣
    for (int i = 0; i < G->n; i++)
        for (int j = 0; j < G->n; j++)
            G->edges[i][j] = (i == j) ? 0 : INF;
    
    // 添加邊（無向圖對稱）
    int edges[][2] = {{0,1},{0,2},{1,2},{1,3},{2,4},{3,4}};
    for (int k = 0; k < G->e; k++) {
        int u = edges[k][0], v = edges[k][1];
        G->edges[u][v] = G->edges[v][u] = 1;
    }
}

深度優先搜索（DFS）遞歸實現

int visited[MAXV]; // 全局訪問標記

void DFS(MGraph *G, int v) {
    visited[v] = 1;
    printf("%c ", G->vexs[v]); // 訪問頂點
    
    for (int w = 0; w < G->n; w++) {
        if (G->edges[v][w] != INF && !visited[w]) {
            DFS(G, w); // 遞歸訪問未訪問鄰接點
        }
    }
}

void DFSTraverse(MGraph *G, int start) {
    memset(visited, 0, sizeof(visited));
    printf("DFS 從 %c 開始: ", G->vexs[start]);
    DFS(G, start);
    // 若圖不連通，需遍歷所有頂點
    for (int i = 0; i < G->n; i++)
        if (!visited[i]) DFS(G, i);
    printf("\n");
}

廣度優先搜索（BFS）隊列實現

#define MAXQ MAXV
int queue[MAXQ];
int front, rear;

void BFS(MGraph *G, int v) {
    front = rear = 0;
    queue[rear++] = v;
    visited[v] = 1;
    
    while (front != rear) {
        int u = queue[front++];
        printf("%c ", G->vexs[u]);
        
        for (int w = 0; w < G->n; w++) {
            if (G->edges[u][w] != INF && !visited[w]) {
                visited[w] = 1;
                queue[rear++] = w;
            }
        }
    }
}

void BFSTraverse(MGraph *G, int start) {
    memset(visited, 0, sizeof(visited));
    printf("BFS 從 %c 開始: ", G->vexs[start]);
    BFS(G, start);
    for (int i = 0; i < G->n; i++)
        if (!visited[i]) BFS(G, i);
    printf("\n");
}

主函數測試

int main() {
    MGraph G;
    CreateGraph(&G);
    
    printf("圖頂點: ");
    for (int i = 0; i < G.n; i++) printf("%c ", G.vexs[i]);
    printf("\n鄰接矩陣:\n");
    for (int i = 0; i < G.n; i++) {
        for (int j = 0; j < G.n; j++)
            printf("%3d", G.edges[i][j] == INF ? -1 : G.edges[i][j]);
        printf("\n");
    }
    
    DFSTraverse(&G, 0); // 從頂點 0 (A) 開始
    BFSTraverse(&G, 0);
    
    return 0;
}

運行結果示例

圖頂點: A B C D E 
鄰接矩陣:
  0  1  1 -1 -1
  1  0  1  1 -1
  1  1  0 -1  1
 -1  1 -1  0  1
 -1 -1  1  1  0
DFS 從 A 開始: A B C D E 
BFS 從 A 開始: A B C D E

關鍵點總結

擴展：鄰接表版本（稀疏圖更優）

typedef struct ArcNode {
    int adjvex;
    struct ArcNode *next;
} ArcNode;

typedef struct VNode {
    char data;
    ArcNode *first;
} VNode, AdjList[MAXV];

typedef struct {
    AdjList vertices;
    int vexnum, arcnum;
} ALGraph;
// DFS/BFS 邏輯相同，只需將「遍歷矩陣行」改為「遍歷鏈表」