数据结构----BFS和DFS详解

系统管理员 2022-09-25 15:23 109阅读 0赞

*前言*  
The art of teaching is the art of assisting discovery.  
Name:Willam  
Time:2017/2/28

这篇博客将会介绍两种遍历图的算法，一种是：DFS—-深度优先搜索，另外一种就是：BFS–广度优先搜索。

## 1、DFS （深度优先搜索） ##

算法思路：  
从顶点V开始，访问这个顶点，然后依次从V的未被访问的邻接点出发深度优先遍历图，直至图中所有和V有路径的相通的顶点都被访问了，如果此时还有顶点未被访问，则选择图中未被访问的那个顶点作为起点，重复上述动作。

具体的代码实现如下：

#include<iostream>
    #include<string>
    using namespace std;
    
    //使用邻接矩阵完成图的遍历
    struct Graph_array {
        int vexnum;  //图的顶点数
        int edge;    //图的边数
        int ** arc;  //邻接矩阵
        int kind;    //0,为有向图，1，为无向图
        string * infromation; //表示每个顶点的信息
    
    };
    //使用邻接矩阵表示的图
    void createGraph_by_array(int **edge,Graph_array & g) {
        int i = 0;
        g.arc = new int*[g.vexnum];//为邻接矩阵开辟空间
        for (i = 0; i < g.vexnum; i++)
        {
            g.arc[i] = new int[g.vexnum];
            for (int j = 0; j < g.vexnum; j++)
                g.arc[i][j] = 0;
        }   
        for (i = 0; i < g.edge; i++)
        {
            //对矩阵进行赋值
            g.arc[edge[i][0] - 1][edge[i][1] - 1] = 1;
        }
    }
    //打印邻接矩阵
    void print_array(Graph_array g) {
    
        int i = 0;
        for (i = 0; i <g.vexnum; i++) {
            //cout << g.infromation[i] << " ";
            for (int j = 0; j < g.vexnum; j++) {
                cout << g.arc[i][j] << " ";
            }
            cout << endl;
        }
    }
    //进行DFS遍历，
    void DFS_store_array(Graph_array g,int v,bool * & visit) {
        cout << g.infromation[v] << " ";
        visit[v] = true;
        for (int i = 0; i < g.vexnum; i++) {
       //找出下一个位被访问的顶点
            if (g.arc[v][i] == 0 || g.arc[v][i] == INT_MAX) { //如果两个顶点不存在边
                continue;
            }
            else if (!visit[i]) {
       //如果没有被访问，访问该结点
                DFS_store_array(g, i, visit);
            }
        }
    }
    //调用对应的DFS函数进行图的遍历
    void DFS_array_travel(Graph_array g,int begin) {
        bool * visit;
        visit = new bool[g.vexnum];
        int i;
        for (i = 0; i < g.vexnum; i++) {
            visit[i] = false;
        }
        cout << "图的DFS遍历结果：" << endl;
        DFS_store_array(g,begin - 1,visit);
        //如果图是非联通同，那么我们这里还需要对每个顶点遍历一次，保证
        //全部顶点都被访问了
        for (i = 0; i < g.vexnum; i++) {
            if (!visit[i])
                DFS_store_array(g, i,visit);
        }
    
    }
    
    //使用邻接表表示图进行图的遍历
    //表结点
    struct ArcNode {
        int adfvex;//表示该边的另外一个顶点在顶点表中的下标
        ArcNode * next; //表示依附在该顶点的下一条边的信息
    };
    //头结点
    struct Vnode {
        string data; //记录基本信息i
        ArcNode * firstarc;//记录第一条依附在该顶点的边
    };
    //一个图的结构
    struct Graph_List {
        int vexnum;  //图的顶点数
        int edge;    //图的边数
        Vnode * node;  //邻接表
        int kind;    //0,为有向图，1，为无向图
    };
    //建立邻接表
    void createGraph_list(Graph_List & g, int **edge) {
        int i;
        for (i = 0; i < g.edge; i++)
        {
            ArcNode * next=new ArcNode;
            next->adfvex=edge[i][1]-1;
            next->next = NULL;
            //判断该顶点的是否已经有边依附
            if (g.node[edge[i][0]-1].firstarc == NULL) {
                g.node[edge[i][0]-1].firstarc = next;
            }
            else {
       //寻找链表的最后一个结点
                ArcNode * now;
                now = g.node[edge[i][0]-1].firstarc;
                while (now->next) {
                    now = now->next; 
                }
                now->next = next;
            }
        }
    }
    //打印邻接表
    void print_list(Graph_List g) {
        int i;
        for (i = 0; i < g.vexnum; i++) {
            cout << g.node[i].data << " ";
            ArcNode * now;
            now = g.node[i].firstarc;
            while (now) {
                cout << now->adfvex << " ";
                now = now->next;
            }
            cout << endl;
        }
    }
    //使用DFS进行遍历图，在邻接表的情况下进行遍历
    void DFS_store_list(Graph_List g, int v, bool * & visit) {
        cout << g.node[v].data << " ";
        visit[v] = true;
        ArcNode * next = g.node[v].firstarc;
        while (next) {
            if (!visit[next->adfvex]) {
                DFS_store_list(g, next->adfvex, visit);//递归
            }
            else {
                next = next->next;
            }
        }
    }
    //调用上面那个函数进行图的遍历
    void DFS_list(Graph_List g, int begin) {
        int i;
        bool * visit = new bool[g.vexnum];
        for (i = 0; i < g.vexnum; i++) {
            visit[i] = false;
        }
        cout << "图的DFS遍历结果：" << endl;
        DFS_store_list(g, begin - 1, visit);
        for (i = 0; i < g.vexnum; i++) {
            if(!visit[i])
                DFS_store_list(g, i, visit);
        }
    }
    int main()
    {
        Graph_array g;
        Graph_List G;
        int i;
        cout << "输入图的种类：" << endl;
        cin >> g.kind; G.kind = g.kind;
    
        cout << "输入图的顶点个数" << endl;
        cin >> g.vexnum; G.vexnum = g.vexnum;
    
        cout << "输入图的边的个数（输入时注意，无向图的边要比看的边乘以2，然后输入的记得把重复的边也要输进去）" << endl;
        cin >> g.edge; G.edge = g.edge;
    
        g.infromation = new string[g.vexnum];
        G.node = new Vnode[G.vexnum];
    
    
        cout << "输入每个顶点信息（如名称）:" << endl;
        for (i = 0; i < g.vexnum; i++) {
            cin >> g.infromation[i];
            G.node[i].data = g.infromation[i];
            G.node[i].firstarc = NULL;
        }
    
        int ** edge_information;
        edge_information = new int*[g.edge];
    
        cout << "输入每条边两个顶点的编号：" << endl;
        for (i = 0; i < g.edge; i++)
        {
            edge_information[i] = new int[2];
            cin >> edge_information[i][0];
            cin >> edge_information[i][1];
        }
    
        int **arc; //邻接矩阵
        //构造邻接矩阵,其中最后一次参数：1，代表无向图，0，代表有向图
        createGraph_by_array(edge_information,g);
        cout << "图的邻接矩阵为：" << endl;
        print_array(g);
        cout << endl;
        DFS_array_travel(g, 1);
        cout << endl;
    
        createGraph_list(G, edge_information);
        cout << "图的邻接表为：" << endl;
        print_list(G);
        cout << endl;
        DFS_list(G, 1);
        cout << endl;
        system("pause");
        return 0;
    
    
    }

下面，我们对如下这个图进行遍历，  
![这里写图片描述][SouthEast]  
使用上述程序，输出的结果为：  
（输入时注意，无向图的边要比看的边乘以2，然后输入的记得把重复的边也要输进去）  
![这里写图片描述][SouthEast 1]

## 2、BFS （广度优先搜索） ##

BFS就是我们所说的广度优先搜索，它的思路就是：假设从图中的顶点V出，在访问了v之后，依次访问v的各个未被访问的邻接点，然后，分别从这些邻接点出发，依次访问他们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的邻接点”先被访问，直至图中所有的顶点都被访问到为止，防止出现非连通图的情况，我们需要最后遍历一遍，看是否所有的点都被访问了，如果有未被访问的点，那么就把该点作为一个新的起点。

代码实现如下：

#include<iostream>
    #include<string>
    #include<queue>
    using namespace std;
    
    //使用邻接矩阵完成图的遍历
    struct Graph_array {
        int vexnum;  //图的顶点数
        int edge;    //图的边数
        int ** arc;  //邻接矩阵
        int kind;    //0,为有向图，1，为无向图
        string * infromation; //表示每个顶点的信息
    
    };
    //使用邻接矩阵表示的图
    void createGraph_by_array(int **edge, Graph_array & g) {
        int i = 0;
        g.arc = new int*[g.vexnum];//为邻接矩阵开辟空间
        for (i = 0; i < g.vexnum; i++)
        {
            g.arc[i] = new int[g.vexnum];
            for (int j = 0; j < g.vexnum; j++)
                g.arc[i][j] = 0;
        }
        for (i = 0; i < g.edge; i++)
        {
            //对矩阵进行赋值
            g.arc[edge[i][0] - 1][edge[i][1] - 1] = 1;
        }
    }
    //打印邻接矩阵
    void print_array(Graph_array g) {
    
        int i = 0;
        for (i = 0; i <g.vexnum; i++) {
            //cout << g.infromation[i] << " ";
            for (int j = 0; j < g.vexnum; j++) {
                cout << g.arc[i][j] << " ";
            }
            cout << endl;
        }
    }
    
    //调用对应的BFS函数进行图的遍历
    void BFS_array_travel(Graph_array g, int begin) {
        bool * visit;
        visit = new bool[g.vexnum];
        int i;
        for (i = 0; i < g.vexnum; i++) {
            visit[i] = false;
        }
        cout << "图的BFS遍历结果：" << endl;
        //通过我们之前说的算法思路，我们可以知道
        //我们需要使用先进先出的数据存储结构实现我们的BFS，其实那就是队列
        queue<int>  q;
        for (int v = 0; v < g.vexnum; v++) {
       //这重循环是为了保证非连通同的情况下，每个顶点都可以被访问
            if (!visit[(begin-1 + v) % g.vexnum])//注意起点不一定是v1
            {
                cout << g.infromation[(begin - 1 + v) % g.vexnum] << " ";
                visit[(begin - 1 + v) % g.vexnum] = true;
                q.push((begin - 1 + v) % g.vexnum);//初始化我们的队列
                while (!q.empty())
                {
                    int u = q.front();
                    q.pop();
                    for (int j = 0; j < g.vexnum; j++) {
                        if (g.arc[u][j] == 0 || g.arc[u][j] == INT_MAX) { //如果两个顶点不存在边
                            continue;
                        }
                        else if (!visit[j] ) {
       //先访问所有和u相连的顶点，并且把它们加入队列
                            cout << g.infromation[j] << " ";
                            visit[j] = true;
                            q.push(j);
                        }
                    }
                }
            }
    
        }
        cout << "完成" << endl;
    
    }
    
    //使用邻接表表示图进行图的遍历
    //表结点
    struct ArcNode {
        int adfvex;//表示该边的另外一个顶点在顶点表中的下标
        ArcNode * next; //表示依附在该顶点的下一条边的信息
    };
    //头结点
    struct Vnode {
        string data; //记录基本信息i
        ArcNode * firstarc;//记录第一条依附在该顶点的边
    };
    //一个图的结构
    struct Graph_List {
        int vexnum;  //图的顶点数
        int edge;    //图的边数
        Vnode * node;  //邻接表
        int kind;    //0,为有向图，1，为无向图
    };
    //建立邻接表
    void createGraph_list(Graph_List & g, int **edge) {
        int i;
        for (i = 0; i < g.edge; i++)
        {
            ArcNode * next = new ArcNode;
            next->adfvex = edge[i][1] - 1;
            next->next = NULL;
            //判断该顶点的是否已经有边依附
            if (g.node[edge[i][0] - 1].firstarc == NULL) {
                g.node[edge[i][0] - 1].firstarc = next;
            }
            else {
       //寻找链表的最后一个结点
                ArcNode * now;
                now = g.node[edge[i][0] - 1].firstarc;
                while (now->next) {
                    now = now->next;
                }
                now->next = next;
            }
        }
    }
    //打印邻接表
    void print_list(Graph_List g) {
        int i;
        for (i = 0; i < g.vexnum; i++) {
            cout << g.node[i].data << " ";
            ArcNode * now;
            now = g.node[i].firstarc;
            while (now) {
                cout << now->adfvex << " ";
                now = now->next;
            }
            cout << endl;
        }
    }
    
    //利用BFS进行图的遍历
    void BFS_list(Graph_List g, int begin) {
        int i;
        bool * visit = new bool[g.vexnum];
        for (i = 0; i < g.vexnum; i++) {
            visit[i] = false;
        }
        cout << "图的BFS遍历结果：" << endl;
        queue<int>  q;
        for (int v = 0; v < g.vexnum; v++) {
            if (!visit[(begin - 1 + v) % g.vexnum])//注意起点不一定是v1
            {
                cout << g.node[(begin - 1 + v) % g.vexnum].data << " ";
                visit[(begin - 1 + v) % g.vexnum] = true;
                q.push((begin - 1 + v) % g.vexnum);//初始化我们的队列
                while (!q.empty())
                {
                    int u = q.front();
                    q.pop();
                    ArcNode * next;
                    next = g.node[u].firstarc;//获得依附在该顶点的第一条边的信息
                    while (next) {
       //遍历该链表上的所有的点
                        if (!visit[next->adfvex]) {
                            cout << g.node[next->adfvex].data << " ";
                            visit[next->adfvex] = true;
                            q.push(next->adfvex);
                        }
                        next = next->next;
                    }
                }
            }
        }
    }
    int main()
    {
        Graph_array g;
        Graph_List G;
        int i;
        cout << "输入图的种类：" << endl;
        cin >> g.kind; G.kind = g.kind;
    
        cout << "输入图的顶点个数" << endl;
        cin >> g.vexnum; G.vexnum = g.vexnum;
    
        cout << "输入图的边的个数" << endl;
        cin >> g.edge; G.edge = g.edge;
    
        g.infromation = new string[g.vexnum];
        G.node = new Vnode[G.vexnum];
    
    
        cout << "输入每个顶点信息（如名称）:" << endl;
        for (i = 0; i < g.vexnum; i++) {
            cin >> g.infromation[i];
            G.node[i].data = g.infromation[i];
            G.node[i].firstarc = NULL;
        }
    
        int ** edge_information;
        edge_information = new int*[g.edge];
    
        cout << "输入每条边两个顶点的编号：" << endl;
        for (i = 0; i < g.edge; i++)
        {
            edge_information[i] = new int[2];
            cin >> edge_information[i][0];
            cin >> edge_information[i][1];
        }
    
        int **arc; //邻接矩阵
                   //构造邻接矩阵,其中最后一次参数：1，代表无向图，0，代表有向图
        createGraph_by_array(edge_information, g);
        cout << "图的邻接矩阵为：" << endl;
        print_array(g);
        cout << endl;
        BFS_array_travel(g, 1);
        cout << endl;
    
        createGraph_list(G, edge_information);
        cout << "图的邻接表为：" << endl;
        print_list(G);
        cout << endl;
        BFS_list(G, 1);
        cout << endl;
        system("pause");
        return 0;
    
    
    }

同样是对DFS遍历的那个图进行遍历，结果如下：  
![这里写图片描述][SouthEast 2]

## 3、总结 ##

上述我们采用两种方式对图进行的了遍历包括了两种表达方式：邻接表和邻接矩阵，首先我们看遍历的方法上的选择，其实这两种遍历算法的时间复杂度是一样的，它们的不同就是在于遍历顶点的顺序不同，另外，对于两种图的不同的表示方式，我们可以发现邻接矩阵的表示下，图遍历的时间复杂度为：o（n\*n），而在邻接表的下，遍历的时间复杂度只是：O(n+e),其中n为顶点个数，e为边的条数，所以，在实际中需要进行图的遍历的情况下，我们最好是采用邻接表的方式进行表示我们的图。

[SouthEast]: /images/20220717/678bd99903e54fa584c0098b37d9e55c.png
[SouthEast 1]: /images/20220717/b49fc346ed5949f487b31d42554bc010.png
[SouthEast 2]: /images/20220717/8f04dfa424e8421dbefaef3da9a603ab.png