数据结构之图的遍历
广度优先遍历
广度优先遍历过程类似于二叉树的层序遍历，从起始顶点开始一层一层向外进行遍历
比如现在要找东西，假设有三个抽屉，东西在那个抽屉不清楚，现在要将其找到，广度优先遍历的做法是:
- 先将三个抽屉打开，在最外层找一遍
- 将每个抽屉中红色的盒子打开，再找一遍
- 将红色盒子中绿色盒子打开，再找一遍直到找完所有的盒子
- 广度优先遍历需要借助一个队列和一个标记数组，利用队列先进先出的特点实现一层一层向外遍历，利用标记数组来记录各个顶点是否被访问过。
- 刚开始时将起始顶点入队列，并将起始顶点标记为访问过，然后不断从队列中取出顶点进行访问，并判断该顶点是否有邻接顶点，如果有邻接顶点并且该邻接顶点没有被访问过，则将该邻接顶点入队列，并在入队列后立即将该邻接顶点标记为访问过。
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);
}
原文地址：https://blog.csdn.net/m0_74317866/article/details/142469467
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！