从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历（Traversing Graph）。

  • 深度优先遍历（Depth_First_Search）

    从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。这是连通图的情况，如果是非连通图，只需要对它的连通分量分别进行深度优先遍历，即在先前一个顶点进行一次深度优先遍历后，若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

    如果我们用的是邻接矩阵的方式，则代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
     1 typedef bool Boolean; // Boolean是布尔类型，其值是TRUE或FALSE
     2 Boolean visited[MAX]; // 访问标志的数组
     3 // 邻接矩阵的深度优先递归算法
     4 void DFS(MGraph G, int i) {
     5     visited[i] = TRUE;
     6     printf("%c ", G.vexs[i]); // 打印顶点，也可以其他操作
     7     for (int j = 1; j < G.numVertexes; j++)
     8         if (G.arc[i][j] == 1 && !visited[j])
     9             DFS(G, j); // 对未访问的邻接顶点递归调用
    10 }
    11 // 邻接矩阵的深度遍历操作
    12 void DFSTraverse(MGraph G) {
    13     for (int i = 0; i < G.numVertexes; i++)
    14         visited[i] = FALSE; // 初始所有顶点状态都是未访问过状态
    15     for (int i = 0; i < G.numVertexes; i++)
    16         if (!visited[i]) // 对未访问过的顶点调用DFS，若是连通图，只会执行一次
    17             DFS(G, i);
    18 }

    如果图结构是邻接表结构，其DFSTraverse函数的代码是几乎相同的，只是在递归函数中因为将数组换成了链表而有所不同。代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
     1 // 邻接表的深度优先递归算法
     2 void DFS(GraphAdjList GL, int i) {
     3     EdgeNode *p;
     4     visited[i] = TRUE;
     5     printf("%c ", GL->adjList[i].data); // 打印顶点，也可以其他操作
     6     p = GL->adjList[i].firstedge;
     7     while (p) {
     8         if (!visited[p->adjvex])
     9             DFS(GL, p->adjvex);
    10         p = p->next;
    11     }
    12 }
    13 // 邻接表的深度遍历操作
    14 void DFSTraverse(GraphAdjList GL) {
    15     for (int i = 1; i < GL->numVertexes; i++)
    16         visited[i] = FALSE; // 初始所有顶点状态都是未访问过状态
    17     for (int i = 1; i < GL->numVertexes; i++)
    18         if (!visited[i]) // 对未访问过的顶点调用DFS
    19             DFS(GL, i);
    20 }

  • 广度优先遍历（Breadth_First_Search）

    邻接矩阵结构的广度优先遍历算法代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
     1 void BFSTraverse(MGraph G) {
     2     Queue Q;
     3     for (int i = 0; i < G.numVertexes; i++)
     4         visited[i] = FALSE;
     5     InitQueue(&Q); // 初始化一辅助用的队列
     6     for (int i = 0; i < G.numVertexes; i++) { // 对每一个顶点loop
     7         if (!visited[i]) { // 若是未访问过就处理
     8             visited[i] = TRUE; // 设置当前顶点访问过
     9             printf("%c ", G.vexs[i]); // 打印顶点，也可以其他操作
    10             EnQueue(&Q, i); // 将此顶点入队
    11             while (!QueueEmpty(Q)) { // 若当前队列不为空
    12                 DeQueue(&Q, &i); // 将队中元素出队，赋值给i
    13                 for (int j = 0; j < G.numVertexes; j++) {
    14                     // 判断其他顶点若与当前顶点存在边且未访问过
    15                     if (G.arc[i][j] == 1 && !visited[j]) {
    16                         visited[j] = TRUE; // 将找到的此顶点标记为已访问
    17                         printf("%c ", G.vexs[j]); // 打印顶点
    18                         EnQueue(&Q, j); // 将找到的此顶点入队
    19                     }
    20                 }
    21             }
    22         }
    23     }
    24 }

    邻接表的广度优先遍历的代码的邻接矩阵差距不大。代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
     1 void BFSTraverse(GraphAdjList GL) {
     2     EdgeNode *p;
     3     Queue Q;
     4     for (int i = 0; i < GL->numVertexes; i++)
     5         visited[i] = FALSE;
     6     InitQueue(&Q);
     7     for (int i = 0; i < GL->numVertexes; i++) {
     8         if (!visited[i]) {
     9             visited[i] = TRUE;
    10             printf("%c ", GL->adjList[i].data); // 打印顶点，也可以其他操作
    11             EnQueue(&Q, i);
    12             while (!QueueEmpty(Q)) {
    13                 DeQueue(&Q, &i);
    14                 p = GL->adjList[i].firstedge; // 找到当前顶点边表链表头指针
    15                 while (p) {
    16                     if (!visited[p->adjvex]) { // 若此顶点未被访问
    17                         visited[p->adjvex] = TRUE;
    18                         printf("%c ", GL->adjList[p->adjvex].data);
    19                         Enqueue(&Q, p->adjvex); // 将此顶点入队
    20                     }
    21                     p = p->next; // 指针指向下一个邻接点
    22                 }
    23             }
    24         }
    25     }
    26 }