定义：从图中某一顶点出发，访遍图中其余结点，且使每一个顶点仅被访问一次，此过程称之为图的遍历

此文主要介绍两种遍历方法：DFS和BFS

深度优先遍历（DFS -- Depth First Search）

深度优先遍历也称之为深度优先搜索，是一种常用的图遍历算法

深度优先遍历实现总的来说就是两句话：

  1. 从一顶点开始，在图中进行 ”深入“ —— 即从这个顶点开始，顺着某条边进行遍历
  2. 无法 ”深入“ 时，进行 ”回溯“ —— 即若遍历到这条边的终点，则原路返回上一个结点，在此结点进行查询通过此结点所有可以到达的所有结点是否还有未遍历过的结点，再次进行 ”深入“

可见，此遍历的实现过程描述是一种递归描述，所以首先考虑通过递归的方法进行实现

代码：

1
2
3
4
5
6
7
8
void DFS(MGraph graph, int i) {
    int j;
    visited[i] = TRUE;
    printf("%5d", graph->data[i]);
    for (j = 0; j < graph->nv; j++)
        if (graph->g[i][j] != 0  && !visited[j])
            DFS(graph, j);
}

注：

  • 此代码为邻接数组实现的图的DFS遍历
  • visited[] 为标记数组，标记某结点是否被遍历到

代码：

1
2
3
4
5
6
7
8
9
void DFS(LGraph graph, Vertex v){
    PtrToAdjVNode w;
    visited[v] = TRUE;
    printf("%5d", graph->g[v].data);
    for (w = graph->g[v].firstEdge; w; w = w->next) {
        if (!visited[w->adjv])
            DFS(graph, w->adjv);
    }
}

注：

  • 此代码为邻接表实现的图的DFS遍历
  • visited[] 为标记数组，标记某结点是否被遍历到，使用之前应进行初始化为FALSE

广度优先遍历（BFS -- 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
void BFS(MGraph graph){
    int i, j;
    Queue Q;
    for (i = 0; i < graph->nv; ++i)
        visited[i] = FALSE;
    Q = CreateQueue(MAXSIZE);   // 初始化辅助队列
    for (i = 0; i < graph->nv; i++) // 循环每一个顶点
        if (!visited[i]){   // 判断是否访问过
            visited[i] = TRUE;
            printf("%d", graph->data[i]);
            AddQ(Q, i);
            while (!IsEmpty(Q)){    // 队列不空
                i = Delete(Q);  // 取出元素 赋值给i
                for (j = 0; j < graph->nv; j++) {
                    if (graph->g[i][j] == 1 && !visited[j]){    // 判断其他顶点与当前顶点之间是否存在边且是否被访问
                        visited[j] = TRUE;
                        printf("%d", graph->data[j]);
                        AddQ(Q, j); // 将j结点压入队列
                    }
                }
            }
        }
}

两步：

  1. 创造辅助队列，并将 i 压入队列
  2. 弹出 i ，并将其联通的结点依次压入队列

邻接表实现方式，基本代码相同

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void BFS(MGraph graph){
    int i, j;
    Queue Q;
    for (i = 0; i < graph->nv; ++i)
        visited[i] = FALSE;
    Q = CreateQueue(MAXSIZE);   // 初始化辅助队列
    for (i = 0; i < graph->nv; i++) // 循环每一个顶点
        if (!visited[i]){   // 判断是否访问过
            visited[i] = TRUE;
            printf("%d", graph->data[i]);
            AddQ(Q, i);
            while (!IsEmpty(Q)){    // 队列不空
                i = Delete(Q);  // 取出元素 赋值给i
                for (j = 0; j < graph->nv; j++) {
                    if (graph->g[i][j] == 1 && !visited[j]){    // 判断其他顶点与当前顶点之间是否存在边且是否被访问
                        visited[j] = TRUE;
                        printf("%d", graph->data[j]);
                        AddQ(Q, j); // 将j结点压入队列
                    }
                }
            }
        }
}

注：

注意指针的指向并深刻理解代码含义即可