“链式前向星”等三种存图方式分别输出“无向无权图”的“DFS序列”

【DFS序列】
DFS序列（深度优先搜索序列），是树或图结构在深度优先遍历过程中生成的节点访问顺序记录。
下面三段代码，分别采用链式前向星、邻接表、邻接矩阵存图，输出图的“DFS序列”。

【DFS：链式前向星】

#include <bits/stdc++.h>
using namespace std;const int N=1e5+5;
int h[N],e[N<<1],ne[N<<1],idx;
bool st[N];
int n,m,x;void add(int a,int b) {e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}void dfs(int u) {cout<<u<<" ";st[u]=true;for(int i=h[u]; i!=-1; i=ne[i]) {int j=e[i];if(!st[j]) dfs(j);}
}int main() {cin>>n>>m;memset(h,-1,sizeof(h));while(m--) {int a,b;cin>>a>>b;add(a,b),add(b,a);}cin>>x;dfs(x);return 0;
}/*
in:
6 5
2 1
3 2
4 3
5 2
6 1
2out:
2 5 3 4 1 6
*/

【DFS：邻接表】

#include <bits/stdc++.h>
using namespace std;const int N=1e5+5;
vector<int> g[N];
bool st[N];
int n,m,x;void dfs(int u) {cout<<u<<" ";st[u]=true;for(int i=0; i<g[u].size(); i++) {int j=g[u][i];if(!st[j]) dfs(j);}
}int main() {cin>>n>>m;while(m--) {int a,b;cin>>a>>b;g[a].push_back(b);g[b].push_back(a);}cin>>x;dfs(x);return 0;
}/*
in:
6 5
2 1
3 2
4 3
5 2
6 1
2out:
2 1 6 3 4 5
*/

【DFS：邻接矩阵】

#include <bits/stdc++.h>
using namespace std;const int N=100;
int g[N][N];
bool st[N];
int n,m,x;void dfs(int u) {cout<<u<<" ";st[u]=true;for(int i=1; i<=n; i++) {if(!st[i] && g[u][i]!=0) dfs(i);}
}int main() {cin>>n>>m;while(m--) {int a,b;cin>>a>>b;g[a][b]=g[b][a]=1;}cin>>x;dfs(x);return 0;
}/*
in:
6 5
2 1
3 2
4 3
5 2
6 1
2out:
2 1 6 3 4 5
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/139369904
https://blog.csdn.net/hnjzsyjyj/article/details/147622977
https://blog.csdn.net/hnjzsyjyj/article/details/140361781