前言:
这篇文章还是是为了帮助一些
像我这样的菜鸟
找到简单的题解
问题描述:
读入一个用邻接矩阵存储的无向连通图，输出它的深度优先遍历序列
输入格式
第一行一个正整数 n(2≤n≤100)，表示图中的顶点数，顶点编号为 1~n 。
接下来是一个 n×nn×n 的邻接矩阵，a [i][j]=1 表示顶点 i 和顶点 j 之间有直接边相连，a[i][j]=0 表示没有直接边相连。
保证 i=j时，a[i][j]=0，并且 a[i][j]=a[j][i]。
输出格式
输出从顶点 1 开始，对该图进行深度优先遍历得到的顶点序列，每两个数之间用一个 - 分隔。
思考：如果不是连通图，比如某个顶点 x 孤立在外，即邻接矩阵中的 a[x][j]=0，a[i][x]=0，该如何处理？
样例输入
8
0 1 1 0 0 0 0 0
1 0 0 1 1 0 0 0
1 0 0 0 0 0 1 1
0 1 0 0 0 1 0 0
0 1 0 0 0 1 0 0
0 0 0 1 1 0 0 0
0 0 1 0 0 0 0 1
0 0 1 0 0 0 1 0
样例输出
1-2-4-6-5-3-7-8
问题提示
问题解析:
图DFS另外一种输入方法
第一种是读入每条边
图的遍历 DFS遍历(深学思维)_吾乃狙击神蛐的博客-CSDN博客
代码部分:
变量部分
const int N=105;//数组大小
int a[N][N];
bool vis[N];//标记
int n;然后是DFS部分
void dfs(int step)
{
if(step>n)
{
return;
}
for(int i=1;i<=n;i++)
{
if(a[step][i]==0) continue;//如果空不访问
if(vis[i]) continue;//如果走过不访问
cout<<"-"<<i;//输出答案
vis[i]=1;//标记本格
dfs(i);//递归调用DFS
}
return;
}最后是主函数部分
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>a[i][j];//输入答案
}
}
vis[1]=1;
cout<<1;//输出起点
dfs(1);//从起点遍历
return 0;
}完整代码:
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int a[N][N];
bool vis[N];
int n;
void dfs(int step)
{
if(step>n)
{
return;
}
for(int i=1;i<=n;i++)
{
if(a[step][i]==0) continue;
if(vis[i]) continue;
cout<<"-"<<i;
vis[i]=1;
dfs(i);
}
return;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
}
}
vis[1]=1;
cout<<1;
dfs(1);
return 0;
}