#include <iostream>#include <queue>using namespace std;#define MAX_NODES 30// 邻接矩阵存储图int graph[MAX_NODES][MAX_NODES];int visited[MAX_NODES];int n; // 节点数// 深度优先遍历void DFS(int node) { cout << node << " "; visited[node] = 1; for (int i = 0; i < n; i++) { if (graph[node][i] && !visited[i]) { DFS(i); } }}// 广度优先遍历void BFS(int node) { visited[node] = 1; queue<int> q; q.push(node); while (!q.empty()) { int cur = q.front(); q.pop(); cout << cur << " "; for (int i = 0; i < n; i++) { if (graph[cur][i] && !visited[i]) { visited[i] = 1; q.push(i); } } }}int main() { cout << "请输入节点数(不超过 " << MAX_NODES << "):"; cin >> n; cout << "请输入 " << n << " 行 " << n << " 列的邻接矩阵:" << endl; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> graph[i][j]; } } cout << "深度优先遍历结果:" << endl; memset(visited, 0, sizeof(visited)); DFS(0); cout << endl; cout << "广度优先遍历结果:" << endl; memset(visited, 0, sizeof(visited)); BFS(0); cout << endl; return 0;}
时间: 2023-06-19 22:06:29 浏览: 105
这是一个使用邻接矩阵存储图,并实现深度优先遍历和广度优先遍历的程序。
程序首先要求用户输入节点数和邻接矩阵,然后分别调用DFS和BFS函数进行遍历。
其中,DFS函数使用递归实现,从当前节点出发,遍历与其相邻的未访问过的节点,直到所有节点都被访问过。
BFS函数则使用队列实现,从当前节点出发,先将其加入队列中,然后依次取出队列中的节点,并将与其相邻的未访问过的节点加入队列中,直到队列为空。
程序中使用visited数组记录每个节点是否被访问过,防止重复访问。
需要注意的是,邻接矩阵中的1表示两个节点之间有边,0表示没有边。
相关问题
#include <iostream> #include<algorithm> #include<cmath> #include <queue> using namespace std;
#include <iostream>:这是C++标准库中的头文件,用于输入输出流操作,包括cin、cout等。
#include<algorithm>:这是C++标准库中的头文件,用于提供各种算法操作,如排序、查找等。
#include<cmath>:这是C++标准库中的头文件,用于提供数学函数操作,如绝对值、平方根等。
#include <queue>:这是C++标准库中的头文件,用于提供队列操作,包括入队、出队等。
using namespace std;:这是C++的命名空间声明,表示使用std命名空间,可以直接使用std中的函数和对象。
#include <iostream> #include <vector> #include <algorithm> #include <queue> using namespace std; s
这段代码是C++语言中的头文件引入部分,用于在程序中引入iostream、vector、algorithm和queue等库,以便使用这些库中的函数和类。其中,iostream库提供了C++输入输出流的功能,vector库提供了可变大小的数组容器,algorithm库提供了常用的算法函数,queue库提供了队列容器的支持。通过这些库,可以方便地进行程序开发和数据处理。
阅读全文