图的遍历

图的遍历：

• 从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历（Traversing Graph）。
• 树的遍历中由于根节点只有一个，遍历都是从根结点开始。但是图比较复杂，任一顶点都可能和其余的所有顶点相邻接，极有可能存在沿着某条路径搜索后，又回到原顶点，而有些顶点还没有遍历到。因此需要在遍历的过程中打上标记，避免同一个顶点访问多次，可以设置一个访问数组visited[n]，n是图中顶点的个数，初值为false，访问过后设置为true。
• 对于图的遍历来说，通常包括深度优先遍历(DFS)和广度优先遍历(BFS)两种方法。

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

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

广度优先遍历：（Breadth First Search，BFS）:

我们可以发现图的深度优先遍历类似于树的前序遍历，而广度优先遍历类似于树的层序遍历。两者在存储结构相同的情况下时间复杂度是一样的，仅仅是对顶点访问的顺序不同。

代码示例

此处分别使用图的邻接矩阵和邻接表结构实现DFS和BFS，图的结构创建可查看https://www.jianshu.com/p/b50ba1b3c327
MGraph.h

//DFS(深度优先搜索遍历)
void DFS(MGraph G, int v);

//BFS(广度优先搜索遍历)
void BFS(MGraph G, int v);

MGraph.cpp

//DFS(深度优先搜索遍历,使用邻接矩阵的时间复杂度为O(n^2))
void DFS(MGraph G, int v)
{
    cout << G.vexs[v] << " ";
    visited[v] = true;                      //标志已经遍历过
    for (int i = 0; i < G.numVertexes; i++)
    {
        if (G.arc[v][i] && !visited[i])     //未遍历过的邻接点
        {
            DFS(G, i);                          //遍历第i个邻接点
        }
    }
}

//BFS(广度优先搜索遍历  O(n^2)---与存储结构相关)
void BFS(MGraph G, int v)
{
    cout << G.vexs[v] << " ";                           //先遍历当前顶点
    visited[v] = true;

    queue<int> q;
    q.push(v);

    while (!q.empty())                          //如果队列不为空
    {
        int u = q.front();                      //取队列第一个元素
        q.pop();                                //出队

        for (int i = 0; i < G.numVertexes; i++)
        {
            if (G.arc[u][i] && !visited[i])     //未遍历过的邻接点
            {
                cout << G.vexs[i] << " ";
                visited[i] = true;

                q.push(i);
            }
        }
    }
}

ALGraph.h

//DFS（深度优先搜索遍历）
void DFS(GraphAdjList G, int v);

//BFS（广度优先搜索遍历）
void BFS(GraphAdjList G, int v);

ALGraph.cpp

//DFS（深度优先搜索遍历）
void DFS(GraphAdjList G, int v)
{
    cout << G.adjList[v].data << " ";                       //输出顶点名称
    visited1[v] = true;

    EdgeNode* p = G.adjList[v].firstEdge;                   //顶点的第一条边
    while (p)
    {
        if (!visited1[p->adjvex])
        {
            DFS(G, p->adjvex);
        }
        p = p->next;
    }
}

//BFS（广度优先搜索遍历 O(n+e)--与存储结构相关 ）
void BFS(GraphAdjList G, int v)
{
    cout << G.adjList[v].data << " ";                       //输出顶点名称
    visited1[v] = true;

    queue<int> q;
    q.push(v);

    EdgeNode* p;
    while (!q.empty())                                      //顶点还有邻接点
    {
        int u = q.front();
        q.pop();                                            //出队

        p = G.adjList[u].firstEdge;
        while (p)                                           //如果该顶点的边存在
        {
            if (!visited1[p->adjvex])
            {
                cout << G.adjList[p->adjvex].data << " ";
                visited1[p->adjvex] = true;
                q.push(p->adjvex);
            }
            p = p->next;
        }
    }
}

main.cpp

#include <iostream>
#include "MGraph.h"
#include "ALGraph.h"

using namespace std;

extern bool* visited, * visited1;

int main(int argc, char** argv)
{
    //1.邻接矩阵
    MGraph MG;
    CreateMGrah(MG);

    for (int i = 0; i < MG.numVertexes; i++)    //对于连通图，只执行一次
    {
        if (!visited[i])
        {
            DFS(MG, i);                         //深度优先搜索遍历
            //BFS(MG, 0);                       //广度优先搜索遍历
        }

    }

    //////////////////////////////////////////////////
    //2.邻接表
    GraphAdjList ALG;
    CreateALGraph(ALG);

    for (int i = 0; i < ALG.numVertexes; i++)   //对于连通图，只执行一次
    {
        if (!visited1[i])
        {
            DFS(ALG, i);
            //BFS(ALG, 0);
        }
    }
    return 0;
}