数据结构之图的遍历

文章目录

广度优先遍历
深度优先遍历

广度优先遍历

广度优先遍历过程类似于二叉树的层序遍历，从起始顶点开始一层一层向外进行遍历

在这里插入图片描述

比如现在要找东西，假设有三个抽屉，东西在那个抽屉不清楚，现在要将其找到，广度优先遍历的做法是:

先将三个抽屉打开，在最外层找一遍
将每个抽屉中红色的盒子打开，再找一遍
将红色盒子中绿色盒子打开，再找一遍直到找完所有的盒子

在这里插入图片描述

广度优先遍历需要借助一个队列和一个标记数组，利用队列先进先出的特点实现一层一层向外遍历，利用标记数组来记录各个顶点是否被访问过。
刚开始时将起始顶点入队列，并将起始顶点标记为访问过，然后不断从队列中取出顶点进行访问，并判断该顶点是否有邻接顶点，如果有邻接顶点并且该邻接顶点没有被访问过，则将该邻接顶点入队列，并在入队列后立即将该邻接顶点标记为访问过。

void BFS(const V& src) //图的广度优先遍历
{size_t srci = _index[src];//找到值src对应在数组中的下标queue<int> q;vector<bool> visited(_vertex.size(), false); //用来标记哪些元素已经入过队列了q.push(srci);visited[srci] = true;while (!q.empty()){int front = q.front();cout << front << ": " << _vertex[front] << endl;q.pop();//把这个顶点的朋友带入队列,并更新visited数组for (int i = 0; i < _vertex.size(); i++){//_matrix[front][i]代表front->i是否有边,数组值不等于MAX_W就代表它们之间直接相连if (_matrix[front][i] != MAX_W && visited[i] == false){visited[i] = true;q.push(i);}}}
}

深度优先遍历

深度优先遍历过程类似于二叉树的先序遍历，从起始顶点开始不断对顶点进行深入遍历

在这里插入图片描述
比如现在要找东西，假设有三个抽屉，东西在那个抽屉不清楚，现在要将其找到，广度优先遍历的做法是:

先将第一个抽屉打开，在最外层找一遍
将第一个抽屉中红盒子打开，在红盒子中找一遍
将红盒子中绿盒子打开，在绿盒子中找一遍
递归查找剩余的两个盒子

深度优先遍历:将一个抽屉一次性遍历完(包括该抽屉中包含的小盒子)，再去递归遍历其他盒子

深度优先遍历可以通过递归实现，同时也需要借助一个标记数组来记录各个顶点是否被访问过。
从起始顶点处开始进行递归遍历，在遍历过程中先对当前顶点进行访问，并将其标记为访问过，然后判断该顶点是否有邻接顶点，如果有邻接顶点并且该邻接顶点没有被访问过，则递归遍历该邻接顶点。

void _DFS(size_t srci, vector<bool>& visited)
{cout << srci << ":" << _vertexs[srci] << endl;visited[srci] = true;// 找一个srci相邻的没有访问过的点，去往深度遍历for (size_t i = 0; i < _vertexs.size(); ++i){if (_matrix[srci][i] != MAX_W && visited[i] == false){_DFS(i, visited);}}}void DFS(const V& src)
{size_t srci = GetVertexIndex(src);vector<bool> visited(_vertexs.size(), false);_DFS(srci, visited);
}