一、深度优先搜索
DFS : 使用的数据结构stack 空间:O(h),因为深搜只用存一个路径上的点。
BFS:使用的数据结构 queue 空间;O(2^h),每一层的节点个数是指数级别。
BFS是一层一个往外扩展的，如果当一个图的所有边的权重都是1的时候，它第一次搜到某点的所经过的距离一定是最短的距离，因此最短路的概念，DFS则不具有最短性。
DFS两个比较重要的概念：回溯和剪枝。
如果觉得DFS难以思考,可以通过一个搜索树来思考怎么操作。
1 排列数字
DFS的关键是搜索的顺序，我们到底要以什么样的顺序搜索。
回溯时一定要注意恢复现场。
#include <iostream>
using namespace std;
int n;
const int N = 10;
int a[N];
bool used[N];
void dfs(int idx)
{
if (idx == n)
{
for (int i = 0; i < n; ++i) cout << a[i] << ' ';
cout << endl;
return;
}
// 枚举第一个没被
for (int i = 1; i <= n; ++i)
{
if (used[i] == false)
{
a[idx] = i;
used[i] = true;
dfs(idx + 1);
// 回来以后恢复现场
used[i] = false;
}
}
}
int main()
{
cin >> n;
dfs(0);
return 0;
}
2 N皇后
思路1：从第一行开始枚举，枚举第一行的皇后能放在哪，放下后考虑下一行，同排列数字的思路一致。
这里可以在搜索的过程中进行剪枝，即如果摆放的点不合法，就去搜对应的子树，直接去看下一个位置。
时间复杂度：O(n * n!)
#include <iostream>
using namespace std;
const int N = 20;
char table[N][N];
bool cols[N];
bool dgs[N];
bool udgs[N];
int n;
void dfs(int row)
{
if (row == n)
{
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
cout << table[i][j];
}
cout << endl;
}
cout << endl;
return;
}
for (int j = 0; j < n; ++j)
{
if (!cols[j] && !dgs[row + j] && !udgs[n - row + j])
{
table[row][j] = 'Q';
cols[j] = true;
dgs[row + j] = true;
udgs[n - row + j] = true;
dfs(row + 1);
cols[j] = false;
dgs[row + j] = false;
udgs[n - row + j] = false;
table[row][j] = '.';
}
}
}
int main()
{
cin >> n;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
table[i][j] = '.';
dfs(0);
return 0;
}
第二种思路：
前面的思路经过了一种抽象：我们已经知道了不同皇后不能放在同一行，所以枚举的不同行的皇后摆放位置。我们还可以更原始的枚举：枚举每个格子是否可以放皇后。
时间复杂度： O ( 2 n 2 ) O(2^{n^2}) O(2n2)
#include <iostream>
using namespace std;
const int N = 20;
char table[N][N];
bool rows[N];
bool cols[N];
bool dgs[N];
bool udgs[N];
int n;
// cnt是放皇后的个数
void dfs(int x, int y, int cnt)
{
// 如果y出界了 则到下一行的起始位置
if (y == n) x += 1, y = 0;
if (x == n)
{
// 如果放够了n个皇后
if (cnt == n)
{
for (int i = 0; i < n; ++i)
{
// puts 输出字符串并换行
puts(table[i]);
}
puts("");
}
return;
}
// 不在这个点放皇后
dfs(x, y + 1, cnt);
// 放皇后 注意前提
if (!rows[x] && !cols[y] && !dgs[x + y] && !udgs[x - y + n])
{
table[x][y] = 'Q';
rows[x] = cols[y] = dgs[x + y] = udgs[x - y + n] = true;
dfs(x, y + 1, cnt + 1);
rows[x] = cols[y] = dgs[x + y] = udgs[x - y + n] = false;
table[x][y] = '.';
}
}
int main()
{
cin >> n;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
table[i][j] = '.';
dfs(0, 0, 0);
return 0;
}
二、宽度优先搜索
宽度有限搜索是一层一层往外搜的，就好像先吃“窝边草”。
1 走迷宫
// 一种bfs模板：
#include <iostream>
#include <queue>
#include <utility>
#include <cstring>
using namespace std;
const int N = 101;
int d[N][N];// 用来存每个点到(0, 0)的距离
int g[N][N];// 用来存本来的迷宫
int n, m;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int bfs()
{
queue<pair<int, int>> q;
q.push({0, 0});
memset(d, -1, sizeof(d));// 初始距离设置为-1表示还没访问过这个点
d[0][0] = 0;
while (!q.empty())
{
auto l = q.front();
q.pop();
// 拓展新的点
int x = l.first, y = l.second;
for (int i = 0; i < 4; ++i)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] != 1 && d[nx][ny] == -1)
{
d[nx][ny] = d[x][y] + 1;
q.push({nx, ny});
}
}
}
return d[n - 1][m - 1];
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
cin >> g[i][j];
cout << bfs() << endl;
}
如果要记录路径，就是用一个prev数组记录每个点是由那个点转移而来的即可，然后从(n-1,m-1)往回转移即可。
#include <iostream>
#include <queue>
#include <utility>
#include <cstring>
using namespace std;
const int N = 101;
int d[N][N];// 用来存每个点到(0, 0)的距离
int g[N][N];// 用来存本来的迷宫
int n, m;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, -1, 1};
pair<int, int> Prev[N][N];
int bfs()
{
queue<pair<int, int>> q;
q.push({0, 0});
memset(d, -1, sizeof(d));// 初始距离设置为-1表示还没访问过这个点
d[0][0] = 0;
while (!q.empty())
{
auto l = q.front();
q.pop();
// 拓展新的点
int x = l.first, y = l.second;
for (int i = 0; i < 4; ++i)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] != 1 && d[nx][ny] == -1)
{
d[nx][ny] = d[x][y] + 1;
q.push({nx, ny});
Prev[nx][ny] = l;
}
}
}
int x = n - 1, y = m - 1;
while (x || y)
{
cout << x << ' ' << y << endl;
auto l = Prev[x][y];
x = l.first;
y = l.second;
}
return d[n - 1][m - 1];
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
cin >> g[i][j];
cout << bfs() << endl;
}
2 八数码
思路：每个状态可以视为图论中的一个结点，如果状态a通过一次变换能够变成状态b，则a和b之间就有一条边，边的权值是1.
本题就转化为：从起点走到终点，至少需要多少步。
难点1：
- 本题状态比较复杂，每个状态都是一个3*3的小矩阵，因为状态比较难表示，所以如何以队列存储状态、如何存储每个状态之间的距离都是一个问题。
简单的存储方式：使用一个字符串来存储状态，则队列就是queue<string>，距离就可以用unordered_map<string, int>来存储。
难点2：
- 如何做状态转移？
先想像成一个3*3的矩阵，然后移动x，然后把想想的矩阵恢复成字符串。
一维数组转化为二维矩阵的下标：x = k / n, y = k % n,n是列宽。
代码如下：
// 使用哈希表
#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <algorithm>
using namespace std;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int bfs(string & start)
{
string end = "12345678x";
queue<string> q;// 用字符串存储状态 用队列存储字符串以搜索不同状态的距离
unordered_map<string, int> d;
// 用一个哈希表来存储距离
d[start] = 0;
q.push(start);
while (!q.empty())
{
auto s = q.front();
q.pop();
if (s == end) return d[s];// 如果搜到了 直接返回距离
int k = s.find('x');// 找到x点的一维数组下标
int x = k / 3, y = k % 3;
// 一维数组下标转二维数组下下标 更方便的用上下左右处理
int dist = d[s];
// 处理上下左右
for (int i = 0; i < 4; ++i)
{
int nx = x + dx[i], ny = y + dy[i];
// 先进去交换 然后查找是否搜过 然后然后恢复状态
if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3)
{
swap(s[k], s[nx * 3 + ny]);
if (d.count(s) == 0)
{
d[s] = dist + 1;
q.push(s);
}
swap(s[k], s[nx * 3 + ny]);
}
}
}
return -1;
}
int main()
{
string start;
char c;
for (int i = 0; i < 9; ++i)
{
cin >> c;
start += c;
}
cout << bfs(start);
return 0;
}
// 手写字符串的哈希方式
#include <iostream>
#include <string>
#include <queue>
using namespace std;
typedef unsigned long long ULL;
const int N = 10;
const int P = 13331;
const int M = 1000000;
ULL h[N];// 存储前缀的哈希值
ULL d[M];// 存储距离
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, -1, 1};
ULL strhash(const string& str)
{
for (int i = 1; i <= 9; ++i)
{
h[i] = h[i - 1] * P + str[i];
}
return h[9] % M;
}
int bfs(string& start)
{
string end = "12345678x";
queue<string> q;
q.push(start);
d[strhash(start)] = 0;
while (!q.empty())
{
string s = q.front();
q.pop();
ULL t = strhash(s);
if (s == end) return d[t];
int k = s.find('x');
int x = k / 3, y = k % 3;
for (int i = 0; i < 4; ++i)
{
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3)
{
swap(s[k], s[nx * 3 + ny]);
ULL t1 = strhash(s);
if (d[t1] == 0)
{
d[t1] = d[t] + 1;
q.push(s);
}
swap(s[k], s[nx * 3 + ny]);
}
}
}
return -1;
}
int main()
{
string start;
char ch;
for (int i = 1; i <= 9; ++i)
{
cin >> ch;
start += ch;
}
cout << bfs(start);
return 0;
}
三、树与图的存储
1 树的存储
??树是一种无环连通图，所以我们只讲图的存储即可。
2 图的存储
??图分为无向图和有向图，一般无向图通过建两条双向的边就可以使用有向图表示。
??所以无向图就是一种特殊的有向图，我们只需要考虑有向图如何存储即可。
有向图的存储方式：
- 邻接矩阵：
g[a][b]存储a->b的信息，如果有权重就是权值，没有权重就是一个布尔值表示是否有边。 - 邻接表：n个点开n个单链表，存链表头对应的结点直接相连的点，插入一般选择头插。
当输入的规模超过1000000时，出于效率考虑，必须使用scanf.
四、树与图的深度优先遍历
1 概念
??因为树也是一种特殊的图，所以我们只要知道图是怎么遍历的即可。
??图的深度优先遍历也是先沿着一条路猛走，走不动了开始回溯，代码如下：
#include <iostream>
#include <cstring>
using namespace std;
const int N = 10010;
const int M = 2 * N;
int h[N], e[M], ne[M];
bool visited[N];
int idx = 0;
void init()
{
memset(h, -1, sizeof(h));
}
void dfs(int u)
{
visited[u] = true;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!visited[j]) dfs(j);
}
}
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx;
++idx;
}
2 树的重心
思路：
代码：
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
const int M = 2 * N;
int h[N], e[M], ne[M];
bool visited[N];
int idx = 0;
int n;
int ans = N;
void init()
{
memset(h, -1, sizeof(h));
}
int dfs(int u)
{
visited[u] = true;
// res是最终得到子结点的块
int sum = 1, res = 0;
for (int i = h[u]; i != -1; i = ne[i])
{
// 获得对应的结点号
int j = e[i];
if (!visited[j])
{
int tmp = dfs(j);
// res与子结点连通块取小
res = max(res, tmp);
sum += tmp;
}
}
// res与父节点连通块取小
res = max(res, n - sum);
// ans与此轮最大的连通块结点数取小
ans = min(ans, res);
return sum;
}
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx;
++idx;
}
int main()
{
cin >> n;
int a, b;
init();
for (int i = 0; i < n; ++i)
{
cin >> a >> b;
add(a, b);
add(b, a);
}
dfs(1);
cout << ans << endl;
return 0;
}
五、树与图的宽度优先遍历
1 图中点的层次
由于本图中距离都是1，所以本题可以使用宽度优先搜索获得最短距离。
代码：
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int h[N], ne[N], e[N];
int idx = 0;
int n, m;
int d[N];
void init()
{
memset(h, -1, sizeof(h));
}
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx;
++idx;
}
int bfs()
{
queue<int> q;
memset(d, -1, sizeof(d));
d[1] = 0;
q.push(1);
while (!q.empty())
{
int s = q.front();
q.pop();
for (int i = h[s]; i != -1; i = ne[i])
{
int j = e[i];
if (d[j] == -1)
{
d[j] = d[s] + 1;
q.push(j);
}
}
}
return d[n];
}
int main()
{
cin >> n >> m;
init();
int a, b;
for (int i = 0; i < m; ++i)
{
cin >> a >> b;
add(a, b);
}
cout << bfs() << endl;
return 0;
}
2 图的宽搜的经典应用—求拓扑序列
??拓扑序列是针对有向图才有的概念。
??若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x, y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。
??就是对每条边来说，起点在序列中的位置都在终点的前面。
??换句话说，就是想把图展开成一个从前往后指的形式。
??可以证明，一个有向无环图一定存在拓扑序列，因此有向无环图也被称为拓扑图。
??首先，引入出度和入度。
??入度就是指有多少边指向这个点，出度就是这个点有多少边指出去。
??怎么根据出度入度来求拓扑序列？
??所有入度为0的点都可以做起点，所以先把他们都入队列。
??然后弹出队头元素，看队头元素的每条边，假设是t->j,因为t已经作为拓扑序列的起点了，所以它的边已经不会对它和它后面的点有限制了，所以删掉t->j这条边，这个删除操作唯一的影响就是j的入度减1，即d[j]--,若此时d[j]等于0了，那说明j前面的点都摆好了，j可以入拓扑序列了，j入队列代表其入拓扑序列。
??一个有向无环图，至少存在一个入度为0的点。
证明：采用反证法，假设所有点的入度都不是0，那么从任何一个点出发一定能找到一条边指向它的点的起点，又因为图中的点数量是优先的，因此在这个无穷无尽找的过程一定有两个点相同，这就使得我们找的路径形成了一个环，与题设矛盾，所以结论成立。
??所以我们前面的思路的正确性就得证了，每次我们面对的都是一个有向无环图，每次都肯定能找到一个入度为0的点，然后去掉它的往外指的边，然后又是一个有向无环图，然后又一定存在入度为0的点，循环往复。
代码：
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int h[N], ne[N], e[N];
int idx = 0;
int q[N];
int hh = 0, tt = -1;
int d[N];// 入度
int n, m;
void init()
{
memset(h, -1, sizeof(h));
}
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx;
idx++;
}
bool topsort()
{
for (int i = 1; i <= n; ++i)
{
if (d[i] == 0)
{
q[++tt] = i;// 入队
}
}
while (hh <= tt)
{
int s = q[hh++];// 取出队头
for (int i = h[s]; i != -1; i = ne[i])
{
int j = e[i];
--d[j];// 去掉s->j这条边 d[j]--
// 如果入度为0 则它可以作为当前的又一起点 让它入队列
if (d[j] == 0)
{
q[++tt] = j;
}
}
}
// 如果最后入了n个元素 tt应该会指向n - 1 所有结点都入进去了 说明存在拓扑序列
// 如果有环 则那个环上的任何点都入不了队列
return tt == n - 1;
}
int main()
{
cin >> n >> m;
init();
int a, b;
for (int i = 0; i < m; ++i)
{
cin >> a >> b;
add(a, b);
d[b]++;
}
if (topsort())
{
for (int i = 0; i < n; ++i)
{
// 队列中的元素顺序就是拓扑序
cout << q[i] << ' ';
}
}
else
{
puts("-1");
}
return 0;
}
3 拓扑排序经典例题——LeetCode课程表II
??本题可以把a课程是b课程的先修课程看做是a到b有一条边，因此本题就转化为了由先修顺序构成的图是否是有向无环图，如果是，输出它的一个拓扑排序即可，简单套用上面的代码即可。
class Solution {
public:
static const int N = 5000;
int h[N], e[N], ne[N];
int idx = 0;
int d[N];
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx;
idx++;
}
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites)
{
memset(h, -1, sizeof(h));
memset(d, 0, sizeof(d));
vector<int> topo;
for (auto& l : prerequisites)
{
add(l[1], l[0]);
++d[l[0]];
}
queue<int> q;
for (int i = 0; i < numCourses; ++i)
{
if (d[i] == 0)
{
q.push(i);
topo.push_back(i);
}
}
while (!q.empty())
{
int s = q.front();
q.pop();
for (int i = h[s]; i != -1; i = ne[i])
{
int j = e[i];
--d[j];
if (d[j] == 0)
{
q.push(j);
topo.push_back(j);
}
}
}
if (topo.size() != numCourses) return vector<int>();
return topo;
}
};
4 LeetCode课程表IV
??本题可以用一个set<int>数组来放每个课程的先修课程集合，每次使用拓扑排序那种算法考虑当前正在处理课程的后继课程时，都把当前课程以及当前课程的前继课程放进后继课程的先修课程和中，然后同样的若入度为0了，就让它入队。
class Solution {
public:
static const int N = 5000;
int h[N], ne[N], e[N], d[N];
int idx = 0;
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx;
++idx;
}
vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries)
{
vector<set<int>> prev(numCourses);
memset(h, -1, sizeof(h));
memset(d, 0, sizeof(d));
for (auto& l : prerequisites)
{
add(l[0], l[1]);
++d[l[1]];
}
queue<int> q;
for (int i = 0; i < numCourses; ++i)
{
if (d[i] == 0)
{
q.push(i);
}
}
while (!q.empty())
{
int s = q.front();
q.pop();
for (int i = h[s]; i != -1; i = ne[i])
{
int j = e[i];
--d[j];
/*它的先修课有s和s的所有先修课*/
prev[j].insert(prev[s].begin(), prev[s].end());
prev[j].insert(s);
if (d[j] == 0)
{
q.push(j);
}
}
}
vector<bool> ret;
for (auto& query : queries)
{
if (prev[query[1]].count(query[0]) != 0)
{
ret.push_back(true);
}
else
{
ret.push_back(false);
}
}
return ret;
}
};