深度優(yōu)先遍歷：類似與樹的前序遍歷。從圖中的某個頂點(diǎn)v出發(fā)，訪問此頂點(diǎn)，然后從v的未被訪問到的鄰接點(diǎn)進(jìn)行遍歷，直到圖中所有和v有路徑相通的頂點(diǎn)都被訪問到（注：優(yōu)先訪問外層節(jié)點(diǎn)，訪問到無新頂點(diǎn)時，會進(jìn)行回退，訪問未被訪問過的分支頂點(diǎn)）。
廣度優(yōu)先遍歷：類似于樹的層序遍歷。從圖中的某個頂點(diǎn)w出發(fā)，讓頂點(diǎn)w入隊，然后頂點(diǎn)w再出隊，并讓所有和頂點(diǎn)w相連的頂點(diǎn)入隊，然后再出隊一個頂點(diǎn)t，并讓所有和t相連但未被訪問過的頂點(diǎn)入隊……由此循環(huán)，指定圖中所有元素都出隊。

無向圖

鄰接矩陣深度優(yōu)先遍歷圖

鄰接矩陣廣度優(yōu)先遍歷圖

實(shí)現(xiàn)代碼如下：

// 鄰接矩陣的深度和廣度優(yōu)先遍歷
#include <stdio.h>

#define OK 1      // 執(zhí)行成功
#define ERROR 0   // 執(zhí)行失敗
#define TRUE 1    // 返回值為真
#define FALSE 0   // 返回值為假

typedef int Status; // 執(zhí)行狀態(tài)（OK、ERROR）
typedef int Boolean; // 布爾值（TRUE、FALSE）

typedef char VertexType; // 頂點(diǎn)元素類型
typedef int EdgeType; // 邊上權(quán)值的類型

#define MAXSIZE 9 // 隊列儲存空間初始分配量
#define MAXVEX 100 // 最大頂點(diǎn)數(shù)

// 鄰接矩陣結(jié)構(gòu)（無向圖）
typedef struct {
    VertexType vexs[MAXVEX]; // 頂點(diǎn)表
    EdgeType arc[MAXVEX][MAXVEX]; // 邊表
    int numNodes, numEdges; // 圖的頂點(diǎn)數(shù)、邊數(shù)
} MGraph;

/************** 用到的隊列結(jié)構(gòu)與函數(shù) **************/

// 循環(huán)隊列順序存儲結(jié)構(gòu)
typedef struct {
    int data[MAXSIZE]; // 用于存值的數(shù)組
    int front; // 頭指針
    int rear; // 尾指針，若隊列不空，指向隊尾元素的下一個位置
} Queue;

/**
 * 初始化一個空隊列
 * @param Q 隊列
 * @return 執(zhí)行狀態(tài)
 */
Status InitQueue(Queue *Q) {
    Q->front = Q->rear=  0; // 隊頭和隊尾指針都指向0
    return OK;
}

/**
 * 判斷隊列是否為空
 * @param Q 隊列
 * @return 隊列是否為空
 */
Boolean QueueEmpty(Queue Q) {
    if (Q.front == Q.rear) { // 隊頭等于隊尾指針，隊列為空
        return TRUE;
    } else {
        return FALSE;
    }
}

/**
 * 將元素e插入隊列Q的隊尾
 * @param Q 隊列
 * @param e 插入的元素
 * @return 執(zhí)行狀態(tài)
 */
Status EnQueue(Queue *Q, int e) {
    // 隊列已滿，插入失敗
    if ((Q->rear + 1) % MAXSIZE == Q->front) {
        return ERROR;
    }

    // 將元素e插入隊尾
    Q->data[Q->rear] = e;

    // 設(shè)置隊尾指針指向下一個位置，若到最后則轉(zhuǎn)向頭部
    Q->rear = (Q->rear + 1) % MAXSIZE;
    return OK;
}

/**
 * 隊頭元素出隊，用e返回其值
 * @param Q 隊列
 * @param e 隊頭元素的值
 * @return 執(zhí)行狀態(tài)
 */
Status DeQueue(Queue *Q, int *e) {
    // 對頭指針等于對尾指針，此時隊列為空，出隊失敗
    if (Q->front == Q->rear) {
        return ERROR;
    }

    // 將隊頭元素的值賦給元素e
    *e = Q->data[Q->front];

    // 設(shè)置隊頭指針指向下一個位置，若到最后則轉(zhuǎn)向頭部
    Q->front = (Q->front + 1) % MAXSIZE;
    return OK;
}

/*************************************************/

/**
 * 生成鄰接矩陣
 * @param G 鄰接矩陣
 */
void CreateMGraph(MGraph *G) {
    int i, j; // 用于遍歷元素

    G->numEdges = 15; // 設(shè)置有15條邊
    G->numNodes = 9; // 設(shè)置有9個頂點(diǎn)

    // 讀入頂點(diǎn)信息，建立頂點(diǎn)表
    G->vexs[0] = 'A';
    G->vexs[1] = 'B';
    G->vexs[2] = 'C';
    G->vexs[3] = 'D';
    G->vexs[4] = 'E';
    G->vexs[5] = 'F';
    G->vexs[6] = 'G';
    G->vexs[7] = 'H';
    G->vexs[8] = 'I';

    // 初始化圖的邊
    for (i = 0; i < G->numNodes; i++) {
        for (j = 0; j < G->numNodes; j++) {
            G->arc[i][j] = 0; // 設(shè)置所有邊的值都為0
        }
    }

    // 設(shè)置特定邊（如果arc[i][j] = 1，代表頂點(diǎn)i到頂點(diǎn)j有邊相連）
    G->arc[0][1] = 1;
    G->arc[0][5] = 1;

    G->arc[1][2] = 1;
    G->arc[1][8] = 1;
    G->arc[1][6] = 1;

    G->arc[2][3] = 1;
    G->arc[2][8] = 1;

    G->arc[3][4] = 1;
    G->arc[3][7] = 1;
    G->arc[3][6] = 1;
    G->arc[3][8] = 1;

    G->arc[4][5] = 1;
    G->arc[4][7] = 1;

    G->arc[5][6] = 1;

    G->arc[6][7] = 1;

    // 設(shè)置對稱邊
    for (i = 0; i < G->numNodes; i++) {
        for (j = i; j < G->numNodes; j++) {
            G->arc[j][i] = G->arc[i][j];
        }
    }
}

// 訪問標(biāo)志的數(shù)組
Boolean visited[MAXVEX];


/**
 * 鄰接矩陣的深度優(yōu)先遞歸算法
 * @param G 鄰接矩陣
 * @param i 頂點(diǎn)下標(biāo)
 */
void DFS(MGraph G, int i) {
    int j; // 用于遍歷元素

    visited[i] = TRUE; // 記錄該下標(biāo)的元素已被訪問

    printf("%c ", G.vexs[i]); // 打印該位置的頂點(diǎn)值

    // 遍歷圖中的頂點(diǎn)
    for (j = 0; j < G.numNodes; j++) {
        // 頂點(diǎn)i到頂點(diǎn)j有邊相連，并且頂點(diǎn)j未被訪問過
        if (G.arc[i][j] == 1 && !visited[j]) {
            DFS(G, j); // 對頂點(diǎn)j進(jìn)行訪問
        }
    }
}

/**
 * 鄰接矩陣的深度遍歷
 * @param G 鄰接矩陣
 */
void DFSTraverse(MGraph G) {
    int i; // 用于遍歷元素

    // 初始化設(shè)置所有頂點(diǎn)都沒被訪問過
    for (i = 0; i < G.numNodes; i++) {
        visited[i] = FALSE;
    }

    // 遍歷頂點(diǎn)i
    for (i = 0; i < G.numNodes; i++) {
        // 如果頂點(diǎn)i未被訪問過
        if (!visited[i]) {
            DFS(G, i); // 訪問頂點(diǎn)i
        }
    }
}

/**
 * 鄰接矩陣的廣度遍歷算法
 * @param G 鄰接矩陣
 */
void BFSTraverse(MGraph G) {
    int i, j; // 用于遍歷元素
    Queue Q; // 隊列

    // 初始設(shè)置圖的所有頂點(diǎn)都沒被訪問過
    for (i = 0; i < G.numNodes; i++) {
        visited[i] = FALSE;
    }

    InitQueue(&Q); // 初始化隊列

    // 對每一個頂點(diǎn)做循環(huán)
    for (i = 0; i < G.numNodes; i++) {
        if (!visited[i]) { // 該頂點(diǎn)未被訪問過，進(jìn)行處理
            visited[i] = TRUE; // 設(shè)置該頂點(diǎn)i已被訪問

            printf("%c ", G.vexs[i]); // 打印該頂點(diǎn)i的值

            EnQueue(&Q, i); // 將該頂點(diǎn)i入隊

            // 當(dāng)隊列非空時，進(jìn)行循環(huán)
            while (!QueueEmpty(Q)) {
                DeQueue(&Q, &i); // 將隊頭元素出隊，賦值給i

                // 遍歷當(dāng)前節(jié)點(diǎn)以外的節(jié)點(diǎn)j
                for (j = 0; j < G.numNodes; j++) {
                    // 若頂點(diǎn)j與當(dāng)前節(jié)點(diǎn)存在邊，并且未被訪問過
                    if (G.arc[i][j] == 1 && !visited[j]) {
                        visited[j] = TRUE; // 設(shè)置頂點(diǎn)j已被訪問
                        printf("%c ", G.vexs[j]); // 打印頂點(diǎn)j的值

                        EnQueue(&Q, j); // 將頂點(diǎn)j入隊
                    }
                }
            }
        }
    }
}

int main() {
    MGraph G; // 鄰接矩陣
    CreateMGraph(&G); // 創(chuàng)建鄰接矩陣
    printf("深度遍歷：");
    DFSTraverse(G); // 深度遍歷鄰接矩陣

    printf("\n廣度遍歷：");
    BFSTraverse(G); // 廣度遍歷鄰接矩陣

    return 0;
}

運(yùn)行結(jié)果