圖的鄰接表存儲與深度/廣度優先遍歷完整實現

圖的鄰接表結構定義

#define MAXV 255
typedef char VertexType;
typedef int Bool;

typedef struct EdgeNode {
    int adjvex;              // 鄰接點下標
    struct EdgeNode *next;   // 下一條邊
} EdgeNode;

typedef struct VertexNode {
    VertexType data;         // 頂點信息
    EdgeNode *firstedge;     // 第一條邊
} VertexNode, AdjList[MAXV];

typedef struct {
    AdjList adjList;
    int numVertexes, numEdges;
} Graph, *GraphAdjList;

無向圖每條邊在兩個頂點鏈表中各插入一個EdgeNode。

深度優先遍歷 (DFS)

思想：從起點出發，沿一條路走到底，無路可走則回溯。
遞歸實現：

Bool visited[MAXV];

void DFS(GraphAdjList G, int i) {
    visited[i] = TRUE;
    printf("%c ", G->adjList[i].data);
    for (EdgeNode *p = G->adjList[i].firstedge; p; p = p->next)
        if (!visited[p->adjvex]) DFS(G, p->adjvex);
}

void DFSTraverse(GraphAdjList G) {
    for (int i = 0; i < G->numVertexes; i++) visited[i] = FALSE;
    for (int i = 0; i < G->numVertexes; i++)
        if (!visited[i]) DFS(G, i); // 處理非連通圖
}

廣度優先遍歷 (BFS)

思想：層層推進，先訪問起點，再訪問其所有鄰接點，再訪問鄰接點的鄰接點……需輔助隊列。
循環隊列實現：

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

void initQueue(Queue Q) { Q->front = Q->rear = 0; }
Bool QueueEmpty(Queue Q) { return Q->front == Q->rear; }
Bool QueueFull(Queue Q) { return (Q->rear+1)%MAXV == Q->front; }
void EnQueue(Queue Q, int e) { if(!QueueFull(Q)) { Q->data[Q->rear]=e; Q->rear=(Q->rear+1)%MAXV; } }
void DeQueue(Queue Q, int *e) { if(!QueueEmpty(Q)) { *e=Q->data[Q->front]; Q->front=(Q->front+1)%MAXV; } }

BFS主流程：

void BFSTraverse(GraphAdjList G) {
    Queue Q = malloc(sizeof(LoopQueue));
    for (int i = 0; i < G->numVertexes; i++) visited[i] = FALSE;
    initQueue(Q);
    for (int i = 0; i < G->numVertexes; i++) {
        if (!visited[i]) {
            visited[i] = TRUE;
            printf("%c ", G->adjList[i].data);
            EnQueue(Q, i);
            while (!QueueEmpty(Q)) {
                int u; DeQueue(Q, &u);
                for (EdgeNode *p = G->adjList[u].firstedge; p; p = p->next)
                    if (!visited[p->adjvex]) {
                        visited[p->adjvex] = TRUE;
                        printf("%c ", G->adjList[p->adjvex].data);
                        EnQueue(Q, p->adjvex);
                    }
            }
        }
    }
    free(Q);
}

完整可運行程序

包含CreateALGraph交互式構建圖（輸入頂點數、邊數、頂點標籤、邊對），main調用遍歷並輸出。測試例：5頂點、邊(0,3)(0,4)(3,1)(3,2)(4,1)。
DFS輸出：0 3 1 2 4（依鄰接表插入順序）
BFS輸出：0 3 4 1 2

關鍵差異總結