图的遍历算法——DFS、BFS原理及实现

图的遍历定义

图的遍历（搜索）：从图的某一顶点出发，对图中所有顶点访问一次且仅访问一次。

• 访问：抽象操作，可以是对节点进行的各种处理。
• 连通图与非连通图都可以。

但是图结构具有复杂性，不像线性表和树结构的顶点是有先后次序的，在图结构中任何两个顶点之间都可能存在边，顶点是没有先后次序的，所以顶点编号不唯一。

如何判别某些顶点被访问过

图中可能存在回路，且图的任一顶点都可能与其他顶点“相通”，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点，那么如何避免某些顶点被重复访问？

• 解决方法：附设访问标志数组 visited[n]。

在图中，一个顶点可以和其他多个顶点相连，当这样的顶点访问过后，如何选取下一个要访问的顶点？

• 深度优先搜索；
• 广度优先搜索；

深度优先搜索（Depth-First-Search）

类似于树结构的先序遍历。

设图 G 的初态是所有顶点都 “未访问过（False）”，在 G 中任选一个顶点 v 为初始出发点（源点），则深度优先搜索可定义为：

• 首先，访问出发点 v，并将其标记为“访问过 (True) ”；
• 然后，从 v 出发依次考察与 v 相邻的顶点 w ：若 w “未访问过(False)”，则以 w 为新的出发点递归地进行深度优先搜索，直到图中所有与源点 v 有路径相通的顶点（亦称从源点可到达的顶点）均被访问为止，这个过程称为从源点出发的一次先深搜索；
• 若此时图中仍有未被访问过的顶点,则另选一个“未访问过”的顶点作为新的搜索起点,重复上述过程,直到图中所有顶点都被访问过为止。

注意到进行深度优先搜索的过程中，访问与当前节点邻接的节点的前提是该顶点没有被访问过。

深度优先搜索时间复杂度：

• 邻接矩阵： O ( N 2 ) O(N^2) O(N2)
• 邻接表： O ( N + E ) O(N + E) O(N+E)

深度优先遍历的特点：

• 是递归的定义，尽可能对纵深方向上进行搜索，故称先深或深度优先搜索。
• 搜索过程中，根据访问的顺序给顶点进行的编号，称为先深或深度优先编号；
• 搜索过程中，根据访问的顺序得到的顶点序列，称为先深序列或 DFS 序列；

生成森林（树）：由原图的所有顶点和搜索过程中所经过的边构成的子图。

由于深度优先搜索的结果不唯一，所以图的 DFS 序列、先深编号和生成森林不唯一。

深度优先搜索的递归实现

深度优先需要无路可走时按照来路往回退，恰好是后进先出，需要用到栈（递归写法（系统栈），非递归写法（显式定义栈））。

递归写法（邻接表形式、邻接矩阵形式）：

• 邻接矩阵形式，时间复杂度为 O ( N 2 ) O(N^2) O(N2)，因为对每个节点，都要判断一次矩阵中该行的所有位置是否非零。
• 邻接表形式，时间复杂度为 O ( N + E ) O(N + E) O(N+E)，对每个节点，可以直接找到与其邻接的顶点，不需要对其他顶点进行判断。

bool visited[NumVertices];      // 访问标记数组是全局变量
int dfn[NumVertices];           // 顶点的先深编号
int count = 1;                  // 当前访问节点个数

void DFSTraverse(AdjGraph G)    // 主函数
/* 先深搜索——邻接表表示的图G；而以邻接矩阵表示G时,算法完全相同 */
{ 
    for(int i = 0; i < G.n; i++)
        visited[i] = FALSE;     // 标志数组初始化
    for(int i = 0; i < G.n; i++)
        if(!visited[i])
            DFSX(G, i); 
}

void DFS1(AdjGraph* G, int i)
// 以 vi 为出发点时对邻接表表示的图 G 进行先深搜索
{
    EdgeNode *p;
    cout << G→vexlist[i].vertex;    // 访问顶点 vi 
    visited[i] = TRUE;              // 标记 vi 已访问
    dfn[i] = count++;               // 对 vi 进行编号

    p = G→vexlist[i].firstedge;     // 取 vi 边表的头指针
    
    while(p) {          //依次搜索 vi 的邻接点 vj, 这里j=p->adjvex
        if(!visited[p→adjvex])      // 若 vj 尚未访问 *
            DFS1(G, p→adjvex);      // 则以 vj 为出发点先深搜索
        p=p→next;
    }
} //DFS1

void DFS2(MTGraph *G, int i)
// 以 vi 为出发点对邻接矩阵表示的图 G 进行深度优先搜索
{ 
    int j;
    cout << G→vexlist[i];           // 访问定点vi
    visited[i] = TRUE;              // 标记 vi 已访问
    dfn[i] = count++;               // 对 vi 进行编号

    for(j=0; j<G→n; j++)            // 依次搜索 vi 的邻接点
        if((G→edge[i][j] == 1) && !visited[i])   // 若 vj 尚未访问 *
            DFS2(G, j);
}//DFS2

深度优先遍历的非递归写法也非常容易实现，需要自己定义栈。编写过程中应注意的问题：

• 在将一个节点 v i v_i vi​ 入栈前，需要将该节点的访问标记位 visited[i] 置 True，这样可以防止同一个节点多次入栈，重复入栈；
• 当一个节点 v i v_i vi​ 入栈时，不应对其进行访问，不然这样就既不是深搜也不是广搜。
• 当一个节点 v i v_i vi​ 出栈时，才对其进行访问。
• 实现可见https://blog.csdn.net/livecoldsun/article/details/25247071。

广度优先搜索（Breadth-First-Search）

类似于树的层序遍历。

设图 G 的初态是所有顶点都“未访问过(False)”，在 G 中任选一个顶点 v 为源点,则广度优先搜索可定义为:

• 首先访问出发点 v,并将其标记为“访问过 (True)”;
• 接着依次访问所有与 v 相邻的顶点 w1, w2 ...wt ;
• 然后依次访问与 w1, w2 ...wt 相邻的所有未访问的顶点;
• 依次类推，直至图中所有与源点 v 有路相通的顶点都已访问过为止，该过程称为从源点出发的一次先广搜索（广度优先搜索）。
• 此时，从 v 开始的搜索结束，若 G 是连通的，则遍历完成；否则在G中另选一个尚未访问的顶点作为新源点继续上述搜索过程，直到 G 中的所有顶点均已访问为止。

广度优先遍历特点:

• 尽可能横向上进行搜索，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问,故称先广搜索或广度优先搜索。
• 搜索过程中，根据访问顺序给顶点进行的编号，称为先广或广度优先编号；
• 搜索过程中，根据访问顺序得到的顶点序列,称为先广序列或BFS序列。

生成森林(树)：由原图的所有顶点和搜索过程中所经过的边构成的子图。

由于先广搜索结果不唯一，图的BFS序列、先广编号和生成森林不唯一。

广度优先搜索实现

广度优先搜索需要保证先访问的顶点的未访问邻接点要先被访问，恰好就是先进先出，需要用到队列。

时间复杂度：

• 邻接表 O ( N + E ) O(N + E) O(N+E)；
• 邻接矩阵 O ( N 2 ) O(N^2) O(N2)；

bool visited[NumVertices];      // 访问标记数组是全局变量
int bfn[NumVertices];           // 顶点的先广编号

void BFSTraverse(AdjGraph G)    // 主函数
/* 先深搜索——邻接表表示的图G；而以邻接矩阵表示G时,算法完全相同 */
{ 
    int count = 1;
    for(int i = 0; i < G.n; i++)
        visited[i] = FALSE;     // 标志数组初始化
    for(int i = 0; i < G.n; i++)
        if(!visited[i])
            BFSX(G, i); 
}

void BFS1(AdjGraph *G, int i)//这里没有进行先广编号
{ 
    int j; 
    EdgeNode *p; QUEUE Q; MAKENULL(Q);

    cout << G→vexlist[i].vertex;    // 访问顶点 vi
    visited[i] = TRUE;              // 标记 vi 已访问
    bfn[i] = count++;   
    ENQUEUE(i, Q);                  // 进队列

    while(!Empty(Q)) {              // 队空搜索结束
    
        j = DEQUEUE(Q);             // vj 出队，在这之前 vj 已经被访问过了
        p =G→vexlist[j].firstedge;  // 取vj 的边表头指针
    
        while(p) {    // 若 vj 的邻接点 vk(k=p→adjvex) 存在,依次搜索
            if (!visited[p→adjvex]) {       // 若 vk 未访问过
                cout << G→vexlist[p→adjvex].vertex;  // 访问 vk
                visited[p→adjvex] = TRUE;    // 给 vk 作访问过标记
                bfn[p->adjvex] = count++;
                ENQUEUE(p→adjvex , Q );    //访问过的 vk 入队
            }
            p = p→next;         // 找 vj 的下一个邻接点
        }                       // 重复检测 vj 的所有邻接顶点
    }       // 外层循环,判队列空否
}           // 以 vi 为出发点时对用邻接表表示的图 G 进行先广搜索

void BFS2(MTGraph *G, int i)
{ 
    int j, k; 
    QUEUE Q; MAKENULL(Q);

    cout << G→vexlist[i];       // 访问 vi
    visited[i] = TRUE;          // 给 vi 作访问过标记
    ENQUEUE(i, Q);              // vi 进队列

    while(!Empty(Q) ) {         // 队空时搜索结束
        i=j = DEQUEUE(Q);       // vj 出队
        for(k=0; k<G→n; k++) {  // 依次搜索 vj 的邻接点 v k
            if(G→edge[j][k] == 1 && !visited[k]) { // vk 未访问过
                cout << G→vexlist[k]; // 访问 vk
                visited[k] = TRUE;      // 给 vk 作访问过标记
                bfn(k) = count++;
                ENQUEUE(k, Q);  // 访问过 vk 入队
            }
        }   // 重复检测 vj 的所有邻接顶点
    } // 外层循环,判队列空否
}   // 以 vi 为出发点时对用邻接矩阵表示的图G进行先广搜索