以上代码可以用数据结构知识中图的基本操作实现吗?先建立邻接矩阵无向图,再写函数DFS深度优先遍历算法和函数DFSTraverse遍历所有顶点,最后用main函数调用,输出遍历顶点顺序。
时间: 2024-02-12 17:06:28 浏览: 61
可以的,使用邻接矩阵可以实现图的基本操作,其中DFS深度优先遍历算法和DFSTraverse遍历所有顶点函数也可以通过邻接矩阵实现。具体实现可以参考以下代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100; // 图的最大节点数
int n, m; // 图的节点数和边数
int graph[MAXN][MAXN]; // 邻接矩阵表示的图
bool visited[MAXN]; // 标记节点是否访问过
// 深度优先遍历算法
void DFS(int u)
{
visited[u] = true;
cout << u << " ";
for (int v = 0; v < n; v++)
{
if (graph[u][v] == 1 && !visited[v])
{
DFS(v);
}
}
}
// 遍历所有顶点
void DFSTraverse()
{
for (int u = 0; u < n; u++)
{
visited[u] = false;
}
for (int u = 0; u < n; u++)
{
if (!visited[u])
{
DFS(u);
}
}
}
int main()
{
cin >> n >> m;
// 初始化邻接矩阵
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
graph[i][j] = 0;
}
}
// 构建邻接矩阵
for (int i = 0; i < m; i++)
{
int u, v;
cin >> u >> v;
graph[u][v] = graph[v][u] = 1; // 无向图
}
DFSTraverse();
return 0;
}
```
以上代码中,输入第一行为图的节点数n和边数m,接下来m行为图的边。通过输入构建邻接矩阵,然后通过DFS深度优先遍历算法和DFSTraverse遍历所有顶点函数实现图的遍历。最后在main函数中调用DFSTraverse函数输出遍历顶点顺序。
阅读全文