c++ 【深搜】题目 通过深搜遍历图【邻接矩阵存储时间限制:C/C++ 1000MS,其他语言 2000MS】
内存限制:C/C++ 256MB,其他语言 512MB
难度:简单
描述
上图是由五个顶点(编 号 为 1、2、3、4、5 ) 和 5 条 边 (1-2、 1-3、1-5、2-4、3-5)组成。
现 在 我 们 从 1 号顶点开始遍历这个图,遍历就是指把图的每一个顶点都访问一次。使用 深度优先搜索来遍历这个图将会得到如下的结果。
这五个顶点的被访问顺序如下图。图中每个顶点右上方的数就表示这个顶点是第几个被访问到的,我们还为这个数起了很好听的名字— 时间戳。
深度优先遍历是沿着图的某一条分支遍历直到末端,然后回溯,再沿着另一条进行同样的遍历,直到所有的顶点都被访问过为止。
们先来解决如何存储一个图的问题。最常用的方法是使用一个二维数组e来存储,如下。
上图二维数组中第/ 行第y 列表示的就是顶点/ 到顶点y 是否有边。1表示有边,~表示没有边,这里我们将自己到自己(即 z•等于y ) 设 为 0。
我们将这种存储图的方法称为
图的邻接矩阵存储法。
输入描述
第一行:n,m 分别表示n个点,m条边
接下来m行,分别点a和点b相连接。
5 5
1 2
1 3
1 5
2 4
3 5
输出描述
1 2 4 3 5
用例输入 1
5 5 1 2 1 3 1 5 2 4 3 5
用例输出 1
1 2 4 3 5
这题利用深搜即可解答
题解:
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e8; //无穷大的一个定义
int n, m;
int e[110][110];
int vis[110];
void dfs(int step) {
cout << step << " ";
for(int i = 1; i <= n; i++){
if(e[step][i] == 1 && vis[i] == 0){
vis[i] = 1;
dfs(i);
}
}
}
int main(){
memset(vis,0 ,sizeof vis);
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++){
if(i == j) e[i][j] = 0;
else e[i][j] = INF;
}
for(int i = 1; i <= n; i++){
int a, b;
cin >> a >> b;
e[a][b] = 1;
e[b][a] = 1;
}
vis[1] = 1;
dfs(1);
return 0;
}