图的遍历

介绍

是从图的某一顶点出发，按照某种搜索方式对图中所有顶点访问一次且仅一次。图的遍历可以解决很多搜索问题，在实际中应用非常广泛。图的遍历根据搜索方式的不同，分为广度优先搜索和深度优先搜索。

一.深度优先遍历

1.1介绍

深度优先搜索（Depth First Search, DFS）是最常见的图搜索方法之一。深度优先搜索沿着一条路径一直走下去，无法行进时，回退到刚刚访问的节点，似“不撞南墙不回头，不到黄河不死心”。深度优先遍历是按照深度优先搜索的方式对图进行遍历。
深度优先遍历秘籍：后被访问的顶点，其邻接点先被访问。
根据深度优先遍历秘籍，后来先服务，可以借助于栈实现。递归本身就是使用栈实现的，因此使用递归方法更方便。

举例

代码实现1—深度优先遍历邻接矩阵

//深度优先遍历 邻接矩阵
#include <iostream>
using namespace std;

#define MaxVnum 100 //顶点数最大值
bool visited[MaxVnum];  //访问标志数组，其初值为"false"
typedef char VexType;  //顶点的数据类型，根据需要定义
typedef int EdgeType;  //边上权值的数据类型，若不带权值的图，则为0或1
typedef struct {
   
    VexType Vex[MaxVnum];
    EdgeType Edge[MaxVnum][MaxVnum];
    int vexnum, edgenum; //顶点数，边数
}AMGragh;

int locatevex(AMGragh G, VexType x)
{
   
    for (int i = 0; i < G.vexnum; i++)//查找顶点信息的下标
        if (x == G.Vex[i])
            return i;
    return -1;//没找到
}

void CreateAMGraph(AMGragh& G)//创建无向图的邻接矩阵
{
   
    int i, j;
    VexType u, v;
    cout << "请输入顶点数：" << endl;
    cin >> G.vexnum;
    cout << "请输入边数:" << endl;
    cin >> G.edgenum;
    cout << "请输入顶点信息:" << endl;
    for (int i = 0; i < G.vexnum; i++)//输入顶点信息，存入顶点信息数组
        cin >> G.Vex[i];
    for (int i = 0; i < G.vexnum; i++)//初始化邻接矩阵所有值为0，如果是网，则初始化邻接矩阵为无穷大
        for (int j = 0; j < G.vexnum; j++)
            G.Edge[i][j] = 0;
    cout << "请输入每条边依附的两个顶点：" << endl;
    while (G.edgenum--)
    {
   
        cin >> u >> v;
        i = locatevex(G, u);//查找顶点u的存储下标
        j = locatevex(G, v);//查找顶点v的存储下标
        if (i != -1 && j != -1)
            G.Edge[i][j] = G.Edge[j][i] = 1; //邻接矩阵储置1，若有向图G.Edge[i][j]=1
        else
        {
   
            cout << "输入顶点信息错！请重新输入！" << endl;
            G.edgenum++;//本次输入不算
        }
    }
}

void print(AMGragh G)//输出邻接矩阵
{
   
    cout << "图的邻接矩阵为：" << endl;
    for (int i = 0; i < G.vexnum; i++)
    {
   
        for (int j = 0; j < G.vexnum; j++)
            cout << G.Edge[i][j] << "\t";
        cout << endl;
    }
}

void DFS_AM(AMGragh G, int v)//基于邻接矩阵的深度优先遍历
{
   
    int w;
    cout << G.Vex[v] << "\t";
    visited[v] = true;
    for (w = 0; w < G.vexnum; w++)//依次检查v的所有邻接点
    {
   
        if (G.Edge[v][w] && !visited[w])//v,w邻接且w未被访问
        {
   
            DFS_AM(G, w);//从w顶点开始递归深度优先遍历
        }
    }
}

//如果不是一个连通图,还需要进行验证.
void DFS_AM(AMGragh G)
{
   
    for (int i = 0; i < G.vexnum; i++)//检查未被访问的顶点
    {
   
        if (!visited[i])
        {
   
            DFS_AM(G, i);
        }
    }
}

int main()
{
   
    int v;
    VexType c;
    AMGragh G;
    CreateAMGraph(G);
    print(G);
    cout << "请输入遍历连通图的起始点: ";
    cin >> c;
    v = locatevex(G, c);//查找顶点u的存储下标
    if (v != -1)
    {
   
        cout << "深度优先搜索遍历连通图结果: " << endl;
        DFS_AM(G);
    }
    else {
   
        cout << "输入顶点信息错误!请重新输入!" << endl;
    }
    return 0;
}

运行结果1

如图:

代码实现2—深度优先遍历邻接表

//深度优先遍历 邻接表
#include <iostream>
using namespace std;

const int MaxVnum = 100;//顶点数最大值
bool visited[MaxVnum];  //访问标志数组，其初值为"false"
typedef char VexType;//顶点的数据类型为字符型

typedef struct AdjNode {
    //定义邻接点类型
    int v; //邻接点下标
    struct AdjNode* next; //指向下一个邻接点
}AdjNode;

typedef struct VexNode {
    //定义顶点类型
    VexType data; // VexType为顶点的数据类型，根据需要定义
    AdjNode* first; //指向第一个邻接点
}VexNode;

typedef struct {
   //定义邻接表类型
    VexNode  Vex[MaxVnum];
    int vexnum, edgenum; //顶点数，边数
}ALGragh;

int locatevex(ALGragh G, VexType x)
{
   
    for (int i = 0; i < G.vexnum; i++)//查找顶点信息的下标
        if (x == G.Vex[i].data)
            return i;
    return -1;//没找到
}

void insertedge(ALGragh& G, int i, int j)//插入一条边
{
   
    AdjNode* s;
    s = new AdjNode;
    s->v = j;
    s->next = G.Vex[i].first;
    G.Vex[i].first = s;
}

void printg(ALGragh G)//输出邻接表
{
   
    cout << "----------邻接表如下：----------" << endl;
    for (int i = 0; i < G.vexnum; i++)
    {
   
        AdjNode* t = G.Vex[i].first;
        cout << G.Vex[i].data << ": ";
        while (t != NULL)
        {
   
            cout << "---->";
            cout << "[" << G.Vex[t->v].data << "]";
            t = t->next;
        }
        cout << endl;
    }
}
void CreateALGraph(ALGragh& G)//创建无向图邻接表
{
   
    int i, j;
    VexType u, v;
    cout << "请输入顶点数和边数:" << endl;
    cin >> G.vexnum >> G.edgenum;
    cout << "请输入顶点信息:" << endl;
    for (i = 0; i < G.vexnum; i++)//输入顶点信息，存入顶点信息数组
        cin >> G.Vex[i].data;
    for (i = 0; i < G.vexnum; i++)
        G.Vex[i].first = NULL;
    cout << "请依次输入每条边的两个顶点u,v" << endl;
    while (G.edgenum--)
    {
   
        cin >> u >> v;
        i = locatevex(G, u);//查找顶点u的存储下标
        j = locatevex(G, v);//查找顶点v的存储下标
        if (i != -1 && j != -1)
        {
   
            insertedge(G, i, j);
            //insertedge(G, j, i);//无向图多插入一条边
        }
        else
        {
   
            cout << "输入顶点信息错！请重新输入！" << endl;
            G.edgenum++;//本次输入不算
        }
    }
}

void DFS_AL(ALGragh G, int v)//基于邻接表的深度优先遍历
{
   
    int w;
    AdjNode* p;//辅助指针
    cout << G.Vex[v].data << "\t";
    visited[v] = true;
    p = G.Vex[v].first;//获取该顶点的第一个邻接点
    while (p)//依次检查v的所有邻接点
    {
   
        w = p->v;//w为v的邻接点.
        if (!visited[w])//w未被访问,则从w出发,递归深度优先遍历
        {
   
            DFS_AL(G, w);
        }
        p = p->next;
    }
}

void DFS_AL(ALGragh G) //非连通图,基于邻接表的深度优先遍历
{
   
    for(int i = 0; i < G.vexnum; i++)//检查未被访问的点.
        if (!visited[i])
        {
   
            DFS_AL(G, i);
        }
}

int main()
{
   
    ALGragh G;
    int v;
    VexType c;
    CreateALGraph(G);//创建有向图邻接表
    printg(G);//输出
    cout << "请输入遍历连通图的起始点: ";
    cin >> c;
    v = locatevex(G, c);
    if (v != -1)
    {
   
        cout << "深度优先搜索遍历连通图结果: " << endl;
        DFS_AL(G, v);
    }
    else
    {
   
        cout << "输入顶点信息错误!请重新输入!" << endl;
    }
    return 0;
}

运行结果2

如图:

算法分析

基于邻接矩阵的DFS算法
查找每个顶点的邻接点需要O(n)时间，一共n个顶点，总的时间复杂度为O(n^2)，使用了一个递归工作栈，空间复杂度为O(n)。
基于邻接表的DFS算法
查找顶点vi的邻接点需要O(d(vi))时间，d(vi)为vi的出度（无向图为度），对有向图而言，所有顶点的出度之和等于边数e，对无向图而言，所有顶点的度之和等于2e，因此查找邻接点的时间复杂度为O(e)，加上初始化时间O(n)，总的时间复杂度为O(n+e)，(由于n和e大小未知,所以时间复杂度两者都涉及)使用了一个递归工作栈，空间复杂度为O(n)。

二.广度优先遍历

2.1介绍

广度优先搜索（Breadth First Search, BFS），又称宽度优先搜索，是最常见的图搜索方法之一。广度优先搜索是从某个顶点（源点）出发，一次性访问所有未被访问的邻接点，再依次从这些访问过的邻接点出发……似水中涟漪，一层层地传播开来.

举例

广度优先遍历秘籍：先被访问的顶点，其邻接点先被访问。
根据广度优先遍历秘籍，先来先服务，可以借助于队列实现。每个节点访问一次且只访问一次，因此可以设置一个辅助数组visited[i]=false，表示第i个顶点未访问；visited[i]=true，表示第i个顶点已访问。

代码实现1—广度优先遍历邻接矩阵

#include <iostream>
#include <queue>//引入队列头文件
using namespace std;

#define MaxVnum 100 //顶点数最大值
bool visited[MaxVnum];  //访问标志数组，其初值为"false"
typedef char VexType;  //顶点的数据类型，根据需要定义
typedef int EdgeType;  //边上权值的数据类型，若不带权值的图，则为0或1
typedef struct {
   
    VexType Vex[MaxVnum];
    EdgeType Edge[MaxVnum][MaxVnum];
    int vexnum, edgenum; //顶点数，边数
}AMGragh;

int locatevex(AMGragh G, VexType x)
{
   
    for (int i = 0; i < G.vexnum; i++)//查找顶点信息的下标
        if (x == G.Vex[i])
            return i;
    return -1;//没找到
}

void CreateAMGraph(AMGragh& G)//创建有向图的邻接矩阵
{
   
    int i, j;
    VexType u, v;
    cout << "请输入顶点数：" << endl;
    cin >> G.vexnum;
    cout << "请输入边数:" << endl;
    cin >> G.edgenum;
    cout << "请输入顶点信息:" << endl;
    for (int i = 0; i < G.vexnum; i++)//输入顶点信息，存入顶点信息数组
        cin >> G.Vex[i];
    for (int i = 0; i < G.vexnum; i++)//初始化邻接矩阵所有值为0，如果是网，则初始化邻接矩阵为无穷大
        for (int j = 0; j < G.vexnum; j++)
            G.Edge[i][j] = 0;
    cout << "请输入每条边依附的两个顶点：" << endl;
    while (G.edgenum--)
    {
   
        cin >> u >> v;
        i = locatevex(G, u);//查找顶点u的存储下标
        j = locatevex(G, v);//查找顶点v的存储下标
        if (i != -1 && j != -1)
            G.Edge[i][j] = G.Edge[j][i] = 1; //邻接矩阵储置1，若无向图G.Edge[i][j]=G.Edge[j][i]=1
        else
        {
   
            cout << "输入顶点信息错！请重新输入！" << endl;
            G.edgenum++;//本次输入不算
        }
    }
}

void print(AMGragh G)//输出邻接矩阵
{
   
    cout << "图的邻接矩阵为：" << endl;
    for (int i = 0; i < G.vexnum; i++)
    {
   
        for (int j = 0; j < G.vexnum; j++)
            cout << G.Edge[i][j] << "\t";
        cout << endl;
    }
}

void BFS_AM(AMGragh G, int v)
{
   
    int u, w;
    queue<int> Q;//创建一个队列,里面存放节点的下标
    cout << G.Vex[v] << "\t";
    visited[v] = true;
    Q.push(v);//源点v入队
    while (!Q.empty())
    {
   
        u = Q.front();//取对头
        Q.pop();
        for (w = 0; w < G.vexnum; w++)//一次检查u的所有邻接点
        {
   
            if (G.Edge[u][w] && !visited[w])//是邻接点但没有访问则进行访问
            {
   
                cout << G.Vex[w] << "\t";
                visited[w] = true;
                Q.push(w);
            }
        }
    }
}

int main()
{
   
    int v;
    VexType c;
    AMGragh G;
    CreateAMGraph(G);
    print(G);
    cout << "请输入遍历连通图的起始点: ";
    cin >> c;
    v = locatevex(G, c);//查找顶点u的存储下标
    if (v != -1)
    {
   
        cout << "广度优先搜索遍历连通图结果: " << endl;
        BFS_AM(G, v);
    }
    else {
   
        cout << "输入顶点信息错! 请重新输入!" << endl;
    }
    return 0;
}

运行结果1

如图:

代码实现2—广度优先遍历邻接表

#include <iostream>
#include <queue>//引入队列头文件
using namespace std;

const int MaxVnum = 100;//顶点数最大值
bool visited[MaxVnum];  //访问标志数组，其初值为"false"
typedef char VexType;//顶点的数据类型为字符型

typedef struct AdjNode {
    //定义邻接点类型
    int v; //邻接点下标
    struct AdjNode* next; //指向下一个邻接点
}AdjNode;

typedef struct VexNode {
    //定义顶点类型
    VexType data; // VexType为顶点的数据类型，根据需要定义
    AdjNode* first; //指向第一个邻接点
}VexNode;

typedef struct {
   //定义邻接表类型
    VexNode  Vex[MaxVnum];
    int vexnum, edgenum; //顶点数，边数
}ALGragh;

int locatevex(ALGragh G, VexType x)
{
   
    for (int i = 0; i < G.vexnum; i++)//查找顶点信息的下标
        if (x == G.Vex[i].data)
            return i;
    return -1;//没找到
}

void insertedge(ALGragh& G, int i, int j)//插入一条边
{
   
    AdjNode* s;
    s = new AdjNode;
    s->v = j;
    s->next = G.Vex[i].first;
    G.Vex[i].first = s;
}

void printg(ALGragh G)//输出邻接表
{
   
    cout << "----------邻接表如下：----------" << endl;
    for (int i = 0; i < G.vexnum; i++)
    {
   
        AdjNode* t = G.Vex[i].first;
        cout << G.Vex[i].data << ": ";
        while (t != NULL)
        {
   
            cout << "---->";
            cout << "[" << G.Vex[t->v].data << "]";
            t = t->next;
        }
        cout << endl;
    }
}

void CreateALGraph(ALGragh& G)//创建有向图邻接表
{
   
    int i, j;
    VexType u, v;
    cout << "请输入顶点数和边数:" << endl;
    cin >> G.vexnum >> G.edgenum;
    cout << "请输入顶点信息:" << endl;
    for (i = 0; i < G.vexnum; i++)//输入顶点信息，存入顶点信息数组
        cin >> G.Vex[i].data;
    for (i = 0; i < G.vexnum; i++)
        G.Vex[i].first = NULL;
    cout << "请依次输入每条边的两个顶点u,v" << endl;
    while (G.edgenum--)
    {
   
        cin >> u >> v;
        i = locatevex(G, u);//查找顶点u的存储下标
        j = locatevex(G, v);//查找顶点v的存储下标
        if (i != -1 && j != -1)
            insertedge(G, i, j);
        else
        {
   
            cout << "输入顶点信息错！请重新输入！" << endl;
            G.edgenum++;//本次输入不算
        }
    }
}

void BFS_AL(ALGragh G, int v)//基于邻接表的广度优先遍历
{
   
    int u, w;
    AdjNode* p;
    queue<int> Q;
    cout << G.Vex[v].data << "\t";
    visited[v] = true;
    Q.push(v);
    while (!Q.empty())
    {
   
        u = Q.front();//取对头元素
        Q.pop();
        p = G.Vex[u].first;
        while (p)
        {
   
            w = p->v;
            if (!visited[w])//w未被访问
            {
   
                cout << G.Vex[w].data << "\t";
                visited[w] = true;
                Q.push(w);
            }
            p = p->next;
        }
    }
}

void BFS_AL(ALGragh G)//非连通图,基于邻接表的广度优先遍历
{
   
    for (int i = 0; i < G.vexnum; i++)//查漏点.
    {
   
        if (!visited[i])//未被访问则进行访问
        {
   
            BFS_AL(G, i);
        }
    }
}

int main()
{
   
    ALGragh G;
    int v;
    VexType c;
    CreateALGraph(G);//创建有向邻接表
    printg(G);//输出
    cout << "请输入遍历连通图的起始点: ";
    cin >> c;
    v = locatevex(G, c);//查找顶点u的存储下标
    if (v != -1)
    {
   
        cout << "广度优先搜索遍历连通图结构: " << endl;
        BFS_AL(G, v);
    }
    else
    {
   
        cout << "输入顶点错!请重新输入!" << endl;
    }
    return 0;
}

运行结果2

如图:

算法分析

基于邻接矩阵的BFS算法
查找每个顶点的邻接点需要O(n)时间，一共n个顶点，总的时间复杂度为O(n^2)，使用了一个辅助队列，最坏的情况下每个顶点入队一次(访问完就入队)，空间复杂度为O(n)。
基于邻接表的BFS算法
查找顶点vi的邻接点需要O(d(vi))时间，d(vi)为vi的出度（无向图为度），对有向图而言，所有顶点的出度之和等于边数e，对无向图而言，所有顶点的度之和等于2e，因此查找邻接点的时间复杂度为O(e)，加上初始化时间O(n)，总的时间复杂度为O(n+e)，使用了一个辅助队列，最坏的情况下每个顶点入队一次，空间复杂度为O(n)。

总结

容易发现,广度优先和深度优先的算法效率基本相同,在实际应用中要根据需要合理选择.
需要注意的是，一个图的邻接矩阵是唯一的，因此基于邻接矩阵的BFS或DFS遍历序列也是唯一的。而图的邻接表不是唯一的，边的输入顺序不同，正序或逆序建表都会影响邻接表的邻接点顺序，因此基于邻接表的BFS或DFS遍历序列不是唯一的。