c++图的创建,深度遍历,广度遍历加注释
时间: 2024-03-17 10:45:45 浏览: 20
好的,下面是C++代码(包括注释):
```c++
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int MAXN = 100;//最大节点数
vector<int> G[MAXN];//邻接表存图
bool vis[MAXN];//标记数组,用于记录节点是否被访问
int n, m;//n表示节点数,m表示边数
//深度优先遍历
void dfs(int u)
{
vis[u] = true;//标记u节点已被访问
cout << u << " ";//访问节点u
for (int i = 0; i < G[u].size(); i++)
{
int v = G[u][i];//v是u的一个邻居节点
if (!vis[v])//如果v节点未被访问
{
dfs(v);//递归访问v节点
}
}
}
//广度优先遍历
void bfs(int u)
{
queue<int> q;//队列,用于存储待访问的节点
q.push(u);//将起始节点放入队列
vis[u] = true;//标记起始节点已被访问
while (!q.empty())//当队列不为空
{
int frontNode = q.front();//取出队首节点
q.pop();//弹出队首节点
cout << frontNode << " ";//访问队首节点
for (int i = 0; i < G[frontNode].size(); i++)
{
int v = G[frontNode][i];//v是frontNode的一个邻居节点
if (!vis[v])//如果v节点未被访问
{
q.push(v);//将v节点放入队列
vis[v] = true;//标记v节点已被访问
}
}
}
}
int main()
{
cin >> n >> m;//输入节点数和边数
for (int i = 0; i < m; i++)
{
int u, v;
cin >> u >> v;//输入一条边的两个端点u和v
G[u].push_back(v);//将v节点加入u节点的邻接表中
G[v].push_back(u);//将u节点加入v节点的邻接表中
}
//从节点1开始进行深度优先遍历
dfs(1);
cout << endl;
//清空标记数组
memset(vis, false, sizeof(vis));
//从节点1开始进行广度优先遍历
bfs(1);
cout << endl;
return 0;
}
```
希望这份代码能够帮到你!