数据结构图的遍历

待我称王封你为后i 2022-05-25 05:40 184阅读 0赞

图的遍历分为深度优先遍历（Depth\_First\_Search）和广度优先遍历（Breadth\_First\_Search），

分别简称为DFS和BFS。

图的遍历是从某一个顶点出发，访问其他顶点，但是不能重复访问（每个顶点只能访问一次）。

深度优先遍历（DFS）：

深度优先，就是沿着某一个方向不重复的一直便利下去，若走到尽头，退到上一个顶点，寻找附近有没有顶点，有且不重复的话，接着便利，否则退到上一个顶点。

下面我来讲解下DFS到底是怎么样实现的……

以下面的图为例吧，，

![70][]

下面是这个图的DFS遍历过程（黑色背景表示已访问过）：

![70 1][]

![70 2][]

![70 3][]

上面的遍历过程我来解释下：

我们起始位置时V0，根据箭头的指向，V0->V4，

然后V4周围没有邻接点了，退到V0，V0周围除了V4也没有邻接点（不能重复访问顶点），

接着我们新找一个顶点V1，V1周围有V0和V2，V0已访问过，遍历V2，V1->V2,

V2周围有V0和V3，遍历V3，V1->V2->V3,

V3周围有V2和V4，遍历V4，V1->V2->V3->V4，

V4周围有V0和V3，返回上一个顶点，指到结束。

emmm，下面我用了邻接矩阵的方式，

对了，邻接矩阵其实也可以自己构建，只要把每个顶点与另一个顶点之间的关系写对，就行了

代码如下：

#include <iostream>
    using namespace std;
    
    bool visited[5];    //标记顶点是否访问过
    //邻接矩阵
    int MGraph[5][5] = {
                        {0, 0, 0, 0, 1},
                        {1, 0, 1, 0, 0},
                        {1, 0, 0, 1, 0},
                        {0, 1, 0, 0, 1},
                        {0, 0, 0, 0, 0}
                        };
    //DFS
    void DFS(int MGraph[][5], int i)
    {
        visited[i] = true;
        cout << i;
        for(int j = 0; j < 5; j++)
        {
            if(MGraph[i][j] && !visited[j])
                DFS(MGraph, j);
        }
    }
    void DFSTraverse(int MGraph[][5])
    {
        for(int i = 0; i < 5; i++)
            visited[i] = false; //将顶点初始化为未访问
        for(int i = 0; i < 5; i++)
        {
            if(!visited[i]) //对未访问过的顶点调用DFS，如是连通图，只执行一次（我这个不是连通图）
                DFS(MGraph, i);
        }
    }
    int main()
    {
        DFSTraverse(MGraph);
        return 0;
    }

时间复杂度：若顶点数是n，因为是邻接矩阵，它是个二维数组遍历完成则需要O（n^2）。

运行结果：

![70 4][]

遍历的结果是：04123，与上图对应。

下面是邻接表的代码（DFS是主体，邻接表的代码就不需要看了）：

#include <iostream>
    using namespace std;
    
    //开始 邻接表请看上一节
    #define MAXVERTEX 100
    typedef char vertextype;
    
    typedef struct ArcNode
    {
        int adjvex;
        struct ArcNode *next;
    }ArcNode;
    
    typedef struct VertexNode
    {
        vertextype data;
        ArcNode *firstarc;
    }VertexNode, AdjList[MAXVERTEX];
    
    typedef struct
    {
        AdjList adjlist;
        int numvertex;
        int numarc;
    }GraphAdjList;
    
    void CreateAdjListGraph(GraphAdjList &G)
    {
        ArcNode *e;
        cin >> G.numvertex;
        cin >> G.numarc;
        for(int i = 0; i < G.numvertex; i++)
        {
            cin >> G.adjlist[i].data;
            G.adjlist[i].firstarc = NULL;
        }
        for(int k = 0; k < G.numarc; k++)
        {
            int i, j;
            cin >> i >> j;
            e = new ArcNode;
            e->adjvex = j;
            e->next = G.adjlist[i].firstarc;
            G.adjlist[i].firstarc = e;
        }
    }
    //打印邻接表
    void PrintfGraphAdjList(GraphAdjList G)
    {
        for(int i = 0; i < G.numvertex; i++)
        {
            ArcNode *p = G.adjlist[i].firstarc;
            cout << G.adjlist[i].data << '\t';
            while(p)
            {
                cout << p->adjvex << '\t';
                p = p->next;
            }
            cout << endl;
        }
    }
    //邻接表 结束
    
    bool visited[5];    //用于判断顶点是否被访问过
    //DFS
    void DFS(GraphAdjList G, int i)
    {
        ArcNode *p;
        p = G.adjlist[i].firstarc;
        visited[i] = true;  //将访问过的顶点置位true
        cout << G.adjlist[i].data;
        while(p)
        {
            if(!visited[p->adjvex])
                DFS(G, p->adjvex);
            p = p->next;
        }
    }
    void DFSTraverse(GraphAdjList G)
    {
        for(int i = 0; i < G.numvertex; i++)
            visited[i] = false; //将顶点初始化为未访问状态
        for(int i = 0; i < G.numvertex; i++)
        {
            if(!visited[i]) //若顶点没被访问过
                DFS(G, i);
        }
    }
    
    int main()
    {
        GraphAdjList G;
        CreateAdjListGraph(G);
        PrintfGraphAdjList(G);
        DFSTraverse(G);
        return 0;
    }

时间复杂度：顶点数是n，边数是e，顶点循环是n，加上DFS里面while（p），边循环了e次，所以是O（n + e）。

运行结果：

![70 5][]

两个运行结果都是04123，，，

广度优先遍历（BFS）：

从一点出发，先寻找离它最近的几个顶点，然后继这几个顶点再次深入，但是每次搜寻的都是同一级别的（根据离顶点的距离）。

下面我画一个图：

深度优先遍历（DFS）：

![70 6][]

下面是遍历过程（左右上下的顺序）：

![70 7][]

![70 8][]

![70 9][]

![70 10][]

![70 11][]

emmm，解释下这个遍历过程，不过相信大家也能看懂吧（按照离起始点的远近依次访问）

广度搜索，也就是优先广范围搜索，我们从顶点0开始访问，先访问离它最近的顶点，2和6

这样0->2->6

然后再从2开始访问离它最近的顶点3，7和8

这样0->2->6->3->7->8

然后退回去再从离6最近的5和7访问，7访问过

这样0->2->6->3->7->8->5

然后是3周围的4，接着是7周围的1，这样我们就全部遍历了

最后的流程是0->2->6->3->7->8->5->4->1

然后理解了它的思想后就是代码了，下面是邻接矩阵的BFS：

#include <iostream>
    #include <queue>
    using namespace std;
    
    //邻接矩阵
    int mgraph[9][9] = {
    					{0, 0, 1, 0, 0, 0, 1, 0, 0},
    					{0, 0, 0, 0, 1, 1, 0, 1, 0},
    					{1, 0, 0, 1, 0, 0, 0, 1, 1},
    					{0, 0, 1, 0, 1, 0, 0, 0, 1},
    					{0, 1, 0, 1, 0, 1, 0, 0, 1},
    					{0, 1, 0, 0, 1, 0, 1, 0, 0},
    					{1, 0, 0, 0, 0, 1, 0, 1, 0},
    					{0, 1, 1, 0, 1, 0, 1, 0, 0},
    					{0, 0, 1, 1, 1, 0, 0, 0, 0}
    };
    //定义一个队列
    queue <int> q;
    // 定义判断顶点是否被访问过的数组
    bool visited[9];
    
    //BFS
    void BFSTraverse(int mgraph[][9])
    {
    	for(int i = 0; i < 9; i++)
    		visited[i] = false;
    	for(int i = 0; i < 9; i++)
    	{
    		if(!visited[i])
    		{
    			cout << i;
    			visited[i] = true;
    			q.push(i);
    		}
    		while(!q.empty())
    		{
    			i = q.front();
    			q.pop();
    			for(int j = 0; j < 9; j++)
    			{
    				if(mgraph[i][j] == 1 && !visited[j])
    				{
    					visited[j] = true;
    					cout << j;
    					q.push(j);
    				}
    			}
    		}
    	}
    }
    int main()
    {
    	BFSTraverse(mgraph);
    	return 0;
    }

时间复杂度：与DFS一样还是O（n^2），

运行结果：

![70 12][]

对吧，只要邻接矩阵构建的没有问题，运行结构就跟上面所构造的图一样。

接着是邻接表的BFS代码：

#include <iostream>
    #include <queue>
    using namespace std;
    
    //开始 邻接表请看上一节
    #define MAXVERTEX 100
    typedef char vertextype;
    
    typedef struct ArcNode
    {
        int adjvex;
        struct ArcNode *next;
    }ArcNode;
    
    typedef struct VertexNode
    {
        vertextype data;
        ArcNode *firstarc;
    }VertexNode, AdjList[MAXVERTEX];
    
    typedef struct
    {
        AdjList adjlist;
        int numvertex;
        int numarc;
    }GraphAdjList;
    
    void CreateAdjListGraph(GraphAdjList &G)
    {
        ArcNode *e;
        cin >> G.numvertex;
        cin >> G.numarc;
        for(int i = 0; i < G.numvertex; i++)
        {
            cin >> G.adjlist[i].data;
            G.adjlist[i].firstarc = NULL;
        }
        for(int k = 0; k < G.numarc; k++)
        {
            int i, j;
            cin >> i >> j;
            e = new ArcNode;
            e->adjvex = j;
            e->next = G.adjlist[i].firstarc;
            G.adjlist[i].firstarc = e;
            e = new ArcNode;
            e->adjvex = i;
            e->next = G.adjlist[j].firstarc;
            G.adjlist[j].firstarc = e;
        }
    }
    //打印邻接表
    void PrintfGraphAdjList(GraphAdjList G)
    {
        for(int i = 0; i < G.numvertex; i++)
        {
            ArcNode *p = G.adjlist[i].firstarc;
            cout << G.adjlist[i].data << '\t';
            while(p)
            {
                cout << p->adjvex << '\t';
                p = p->next;
            }
            cout << endl;
        }
    }
    //邻接表 结束
    
    //定义一个队列
    queue <int> q;
    // 定义判断顶点是否被访问过的数组
    bool visited[9];
    
    //BFS
    void BFSTraverse(GraphAdjList G)
    {
        ArcNode *p;
    	for(int i = 0; i < 9; i++)
    		visited[i] = false;
    	for(int i = 0; i < 9; i++)
    	{
    		if(!visited[i])
    		{
    			cout << i;
    			visited[i] = true;
    			q.push(i);
    		}
    		while(!q.empty())
    		{
    			i = q.front();
    			q.pop();
    			p = G.adjlist[i].firstarc;
    			while(p)
    			{
    				if(!visited[p->adjvex])
    				{
    					visited[p->adjvex] = true;
    					cout << p->adjvex;
    					q.push(p->adjvex);
    				}
    				p = p->next;
    			}
    		}
    	}
    }
    int main()
    {
        GraphAdjList G;
        CreateAdjListGraph(G);
        PrintfGraphAdjList(G);
    	BFSTraverse(G);
    	return 0;
    }

时间复杂度：O（n + e）。

运行结果：

![70 13][]

emmm，虽然结果和上面不一样，但是层次都是一样的，按照离起始点的距离

分为4层，第一层是0，第二层是26，第三层是3578，第四层是14，输入的顺序不对，然后排出来的就不对，然是层次肯定是对的。

emmm，就这样吧！

[70]: /images/20220525/e5186373fcdd4d138350fc4e46c637dd.png
[70 1]: /images/20220525/2045fbc5987346d490e743535445494d.png
[70 2]: /images/20220525/c54c214cd3954737a10ff5918960d298.png
[70 3]: /images/20220525/91d46605da094f8b9ea009463a9d2fac.png
[70 4]: /images/20220525/85c569c040184a95b59ed1c14143afd3.png
[70 5]: /images/20220525/8ff2205bc7284463aa114d69c6614552.png
[70 6]: /images/20220525/181277da1ab84f3dbba36362f35461f6.png
[70 7]: /images/20220525/6d0d189b07b54b9e994940797af6d1b6.png
[70 8]: /images/20220525/8cc743f683244b8983c5eef07899cc99.png
[70 9]: /images/20220525/8db07113ed9d4e6cba7bfaec368386b0.png
[70 10]: /images/20220525/3a1f90245a5a4a719e328c08fa9570c6.png
[70 11]: /images/20220525/0d461d7579f044c4b96b95fcb0b61aa2.png
[70 12]: /images/20220525/976645336fab4c508a76e7d3b59db18b.png
[70 13]: /images/20220525/f6c0565308a84f99af4cbbdd890f67f5.png