c++图的邻接矩阵,图的深度优先遍历,广度优先遍历算法
时间: 2025-06-15 22:22:03 浏览: 6
C++中,邻接矩阵是一种用于表示图的数据结构,其中矩阵的行和列分别代表图中的节点,矩阵的元素值则表示对应节点之间是否存在边以及边的关系(例如,0或1表示无边或有边)。邻接矩阵适合稠密图,即边的数量接近于节点数的平方。
**深度优先遍历(Depth First Search, DFS)**:
DFS是一种从源节点开始,沿着一条路尽可能深地探索下去,直到遇到不可达节点或到达目标节点为止。它的核心思想是维护一个栈(递归时通常是函数调用堆栈),将当前节点压入栈,然后递归访问相邻节点。C++中可以使用递归或迭代方式进行实现。
**广度优先遍历(Breadth First Search, BFS)**:
BFS则是从源节点开始,先访问所有距离源节点1步的节点,再访问2步的,以此类推,直到找到目标节点。它是使用队列数据结构来实现的,首先放入起始节点,然后取出节点并访问其邻居,将邻居加入队列,按层次逐层遍历。
以下是简单的C++代码示例:
```cpp
#include <iostream>
#include <vector>
using namespace std;
// 邻接矩阵示例
vector<vector<int>> adjMatrix; // 初始化为二维数组
// DFS伪代码
void dfs(int node) {
visited[node] = true;
cout << node << " ";
for (int neighbor : adjMatrix[node]) {
if (!visited[neighbor])
dfs(neighbor);
}
}
// BFS伪代码
void bfs(int node) {
queue<int> q;
q.push(node);
while (!q.empty()) {
int current = q.front();
q.pop();
cout << current << " ";
for (int neighbor : adjMatrix[current])
if (!visited[neighbor])
q.push(neighbor);
visited[current] = true;
}
}
```
阅读全文
相关推荐

















