|
文章目录
前言Part 1：DFS（深度优先遍历）一、排列数字1.题目描述输入格式输出格式数据范围输入样例输出样例
2.算法
二、n皇后问题1.问题描述输入格式输出格式数据范围输入样例输出样例
2.算法
三、树的重心1.问题描述输入格式输出格式数据范围输入样例输出样例
2.算法
Part 2：BFS（广度优先遍历）一、走迷宫1.问题描述输入格式输出格式数据范围输入样例输出样例
2.算法
二、八数码1.题目描述输入格式输出格式输入样例输出样例
2.算法
三、图中点的层次1.题目描述输入格式输出格式数据范围输入样例输出样例
2.算法
Part 3：拓扑排序一、有向图的拓扑序列1.题目描述输入格式输出格式数据范围输入样例输出样例
2.算法
前言
本篇博客将介绍DFS-深度优先遍历、BFS-广度优先遍历和拓扑排序的常见题型（模板题及其扩展）。DFS和BFS是遍历图的两种方法，其中BFS多用于求最短路问题，在不要求最短时多用DFS，因为DFS的复杂度更低。而拓扑排序是图论中一种特殊的问题，用于求图中是否存在回路。
Part 1：DFS（深度优先遍历）
一、排列数字
1.题目描述
给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。
现在，请你按照字典序将所有的排列方法输出。
输入格式
共一行，包含一个整数 n。
输出格式
按字典序输出所有排列方案，每个方案占一行。
数据范围
1≤n≤7
输入样例
3
输出样例
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
2.算法
假设有 3 个空位，从前往后填数字，每次填一个位置，填的数字不能和前面一样。最开始的时候，三个空位都是空的： __。首先填写第一个空位，第一个空位可以填 1，填写后为：1。填好第一个空位，填第二个空位，第二个空位可以填 2，填写后为：1 2 __。填好第二个空位，填第三个空位，第三个空位可以填 3，填写后为： 1 2 3。这时候，空位填完，无法继续填数，所以这是一种方案，输出。然后往后退一步，退到了状态：1 2 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 3 ，没有其他数字可以填。因此再往后退一步，退到了状态：1 。第二个空位上除了填过的 2，还可以填 3。第二个空位上填写 3，填写后为：1 3 __。填好第二个空位，填第三个空位，第三个空位可以填 2，填写后为： 1 3 2。这时候，空位填完，无法继续填数，所以这是一种方案，输出。如此反复
#include
using namespace std;
const int N = 10;
int path[N];//保存序列
int state[N];//数字是否被用过
int n;
void dfs(int u)
{
if(u > n)//数字填完了，输出
{
for(int i = 1; i > a >> b;
add(a, b), add(b, a); //无向图
}
dfs(1); //可以任意选定一个节点开始 u> n >> m;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
cin >> g[i][j];
cout = 0 && b < 3)
{
//转移x
swap(t[k], t[a * 3 + b]);
//如果当前状态是第一次遍历，记录距离，入队
if(!d.count(t))
{
d[t] = distance + 1;
q.push(t);
}
//还原状态，为下一种转换情况做准备
swap(t[k], t[a * 3 + b]);
}
}
}
//无法转换到目标状态，返回-1
return -1;
}
int main()
{
string c, start;
//输入起始状态
for(int i = 0; i < 9; i++)
{
cin >> c;
start += c;
}
cout n >>m;
memset(h, -1, sizeof h);//初始化，所有节点没有后继，后继都是-1
for(int i = 0; i < m; i++)//读入所有边
{
int a, b;
cin >> a >> b;
add(a, b);//加入邻接表
}
bfs();//广度优先遍历
cout m;//保存点的个数和边的个数
memset(h, -1, sizeof h);//初始化邻接矩阵
while (m -- ){//依次读入边
int a, b;
cin >> a >> b;
d[b]++;//顶点b的入度+1
add(a, b);//添加到邻接矩阵
}
topsort();//进行拓扑排序
return 0;
}
|