图的存储与遍历：DFS、BFS 与回溯

图的存储方式与基础遍历

邻接矩阵

邻接表

1. 前向星
2. vector（支持排序）

​ 单向边，无向边（双向边）

DFS 与 BFS 示例

https://www.starrycoding.com/problem/42

#include<bits/stdc++.h>
using namespace std;
const int N = 60;
int fa[N];
vector<int> g[N];

void dfs(int x)
{
	cout << x << ' ';
	for(auto &y : g[x]) dfs(y);
}

void bfs(int st)
{
	queue<int> q;
	q.push(st);
	while(q.size())
	{
		int x = q.front();q.pop();
		cout << x << ' ';
		for(auto &y : g[x])q.push(y);
	}
}

int main()
{
	int n;cin >> n;
	for(int i = 2;i <= n;++i)cin >> fa[i];
	for(int i = 2;i <= n;++i)g[fa[i]].push_back(i);
	
	for(int i = 1;i <= n;++i)sort(g[i].begin(),g[i].end());
	
	dfs(1);
	cout << '\n';
	bfs(1);
	
	return 0;
	
}

DFS：访问标记与递归

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+9;

vector<int> g[N];

bitset<N> vis;

void dfs(int x)
{
	vis[x] = true; 
	for(auto &y : g[x])
	{
		if(vis[y]) continue;
		dfs(y);
	}
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,m;cin >> n >> m;
	int u,v;
	while(m--)
	{
		cin >> u >> v;
		if(u != v) g[u].push_back(v);
	}
	
	dfs(1);
	
	for(int i = 1;i <= n;++i)if(vis[i]) cout << i << ' ';
	
}

回溯：生成全排列

全排列问题
//https://www.starrycoding.com/problem/30

#include<bits\stdc++.h>
using namespace std;
const int N  = 15;
int n, a[N];
bitset<N> vis;

void dfs(int dep)
{
	if(dep == n+1)
	{
		for(int i = 1;i <= n;i++) cout << a[i] << " \n"[i==n];
		return;
	}
	for(int i = 1;i <= n;++i)
	{
		if(vis[i])continue;
		
		vis[i]=true;
		a[dep] = i;
		dfs(dep+1);
		
		a[dep] = 0;
		vis[i] = false;
	}
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n;
	dfs(1);
	return 0;
}