DFS与BFS
两者的对比:(h是树的高度)
DFS:使用的是栈,空间O(h),不具有最短性
BFS:使用的是队列,空间O(2^h),最短路--涉及最短路径,最小距离等概念的就使用BFS算法
1.DFS-深度优先搜索
全排列问题
func permute(nums []int) [][]int { n := len(nums) var res [][]int var path []int var is_used []bool = make([]bool,n) var dfs func(int) dfs = func(u int){ if u == n { res = append(res,append([]int(nil),path...)) return } for i := 0 ; i < n ; i++ { if !is_used[i] { path = append(path,nums[i]) is_used[i] = true dfs(u+1) path = path[:len(path)-1] is_used[i] = false } } } dfs(0) return res }
N皇后问题
func solveNQueens(n int) [][]string { var res [][]string if n < 1 { return res } var path [][]byte = make([][]byte,n) var col []bool = make([]bool,n) var zdj []bool = make([]bool,n*2) var udj []bool = make([]bool,n*2) for i := 0 ; i < n ; i++ { path[i] = make([]byte,n) for j := 0 ; j < n ; j++ { path[i][j] = '.' } } var dfs func(int) dfs = func(u int) { if u == n { ans := make([]string,n) for i := 0 ; i < n ; i ++{ ans[i] = string(path[i]) } res = append(res,ans) return } for i := 0 ; i < n ; i++ { if !col[i] && !zdj[u+i] && !udj[i-u+n] { path[u][i] = 'Q' col[i] = true zdj[u+i] = true udj[i-u+n] = true dfs(u+1) col[i] = false zdj[u+i] = false udj[i-u+n] = false path[u][i] = '.' } } } dfs(0) return res }
2.BFS-宽度优先搜索
先遍历第一个节点,然后遍历与第一个节点距离为1的所有节点,然后遍历与第一个节点距离为2的所有节点等等等
当所有边的权重都为1时,最短路径问题用BFS来解决
#include <cstring> #include <iostream> #include <algorithm> #include <queue> using namespace std; typedef pair<int, int> PII; const int N = 110; int n, m; //g用来存储地图,d用来存储每个点到起点的距离 int g[N][N], d[N][N]; //如果想要将路径输出的话,可以增加一个额外的数组来存储当前点是从哪个点过来的 //int pre[N][N] int bfs() { queue<PII> q; memset(d, -1, sizeof d);//初始化距离为-1 d[0][0] = 0; q.push({0, 0}); //上右下左的游走 int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; while (q.size()) { auto t = q.front();//队头 q.pop(); for (int i = 0; i < 4; i ++ ) { int x = t.first + dx[i], y = t.second + dy[i]; if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) { d[x][y] = d[t.first][t.second] + 1; //pre[x][y] = t q.push({x, y}); } } } int x = n-1,y=m-1; while(x || y ){ cout << x << ' ' << y << endl; auto t = pre[x][y] x = t.first,y=t.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; return 0; }
3.树与图的存储
树是无环连通图
有向图和无向图
1、邻接矩阵存储 g[a][b] 存储a->b的信息 较适合用来存储稠密图,使用频率比较少
2、邻接表存储
![图片说明]
// 对于每个点k,开一个单链表,存储k所有可以走到的点。h[k]存储这个单链表的头结点 int h[N], e[N], ne[N], idx; // 添加一条边a->b void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; } // 初始化 idx = 0; memset(h, -1, sizeof h);
不管是深度优先遍历还是广度优先遍历,每个节点一般只遍历一次即可,所以一般会用一个布尔数组标记哪个节点被搜索过
4.树与图的深度优先遍历
//时间复杂度 O(n+m), n 表示点数,m 表示边数 int dfs(int u) { st[u] = true; // st[u] 表示点u已经被遍历过 for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) dfs(j); } }
5.树与图的宽度优先遍历
queue<int> q; st[1] = true; // 表示1号点已经被遍历过 q.push(1); while (q.size()) { int t = q.front(); q.pop(); for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) { st[j] = true; // 表示点j已经被遍历过 q.push(j); } } }
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <queue> using namespace std; const int N = 100010; int n, m; int h[N], e[N], ne[N], idx; int d[N]; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; } int bfs() { memset(d, -1, sizeof d); queue<int> q; d[1] = 0; q.push(1); while (q.size()) { int t = q.front(); q.pop(); for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (d[j] == -1) { d[j] = d[t] + 1; q.push(j); } } } return d[n]; } int main() { scanf("%d%d", &n, &m); memset(h, -1, sizeof h); for (int i = 0; i < m; i ++ ) { int a, b; scanf("%d%d", &a, &b); add(a, b); } cout << bfs() << endl; return 0; }
6.拓扑排序
针对有向图来说的,无向图没有拓扑序列,且一个有向无环图的拓扑序列是不唯一的
对一个有向无环图(拓扑图)进行拓扑排序,是将图中所有顶点排成一个线性序列,使得图中任意一对顶点u,v,若存在从 u 到 v 的路径,则在拓扑排序序列中一定是 u 出现在 v 的前面。
入度:u 的入度是指向 u 的边的条数。一个有向无环图一定至少存在一个入度为0的点
出度:u 的出度是从 u 出发的边的条数
所有入度为0的点都可以排在当前最前面的位置。
时间复杂度 O(n+m),n 表示点数,m 表示边数
bool topsort() { int hh = 0, tt = -1; // d[i] 存储点i的入度 for (int i = 1; i <= n; i ++ ) if (!d[i]) q[ ++ tt] = i; while (hh <= tt) { int t = q[hh ++ ]; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (-- d[j] == 0) q[ ++ tt] = j; } } // 如果所有点都入队了,说明存在拓扑序列;否则不存在拓扑序列。 return tt == n - 1; }
#include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 100010; int n, m; int h[N], e[N], ne[N], idx; int d[N]; int q[N]; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; } bool topsort() { int hh = 0, tt = -1; for (int i = 1; i <= n; i ++ ) if (!d[i]) q[ ++ tt] = i; while (hh <= tt) { int t = q[hh ++ ]; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (-- d[j] == 0) q[ ++ tt] = j; } } return tt == n - 1; //判断该图是否存在拓扑序列 } int main() { scanf("%d%d", &n, &m); memset(h, -1, sizeof h); for (int i = 0; i < m; i ++ ) { int a, b; scanf("%d%d", &a, &b); add(a, b); d[b] ++ ; } if (!topsort()) puts("-1"); else { for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);//队列里面的次序就是图的拓扑序 puts(""); } return 0; }
最短路问题
常见的最短路问题分为两大类:
朴素Dijkstra算法适用于稠密图)
int g[N][N]; // 存储每条边 int dist[N]; // 存储1号点到每个点的最短距离 bool st[N]; // 存储每个点的最短路是否已经确定 // 求1号点到n号点的最短路,如果不存在则返回-1 int dijkstra() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; for (int i = 0; i < n - 1; i ++ ) { int t = -1; // 在还未确定最短路的点中,寻找距离最小的点 for (int j = 1; j <= n; j ++ ) if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j; // 用t更新其他点的距离 for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], dist[t] + g[t][j]); st[t] = true; } if (dist[n] == 0x3f3f3f3f) return -1; return dist[n]; }
堆优化的dijkstra算法(适用于稀疏图)
typedef pair<int, int> PII; int n; // 点的数量 int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边 int dist[N]; // 存储所有点到1号点的距离 bool st[N]; // 存储每个点的最短距离是否已确定 // 求1号点到n号点的最短距离,如果不存在,则返回-1 int dijkstra() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; priority_queue<PII, vector<PII>, greater<PII>> heap; heap.push({0, 1}); // first存储距离,second存储节点编号 while (heap.size()) { auto t = heap.top(); heap.pop(); int ver = t.second, distance = t.first; if (st[ver]) continue; st[ver] = true; for (int i = h[ver]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > distance + w[i]) { dist[j] = distance + w[i]; heap.push({dist[j], j}); } } } if (dist[n] == 0x3f3f3f3f) return -1; return dist[n]; }
#include <cstring> #include <iostream> #include <algorithm> #include <queue> using namespace std; typedef pair<int, int> PII; const int N = 1e6 + 10; int n, m; //w表示权重 int h[N], w[N], e[N], ne[N], idx; int dist[N]; bool st[N]; void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ; } int dijkstra() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; priority_queue<PII, vector<PII>, greater<PII>> heap; heap.push({0, 1}); //队列里面存储pair,表示距离是0,编号是1 while (heap.size()) { auto t = heap.top();//当前距离最小的点 heap.pop(); int ver = t.second, distance = t.first; if (st[ver]) continue;//如果之前点已经出现过,可以不用处理了 st[ver] = true; //用当前点来更新其它点的距离 for (int i = h[ver]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[ver] + w[i]) { dist[j] = dist[ver] + w[i]; heap.push({dist[j], j}); } } } if (dist[n] == 0x3f3f3f3f) return -1; return dist[n]; } int main() { scanf("%d%d", &n, &m); memset(h, -1, sizeof h); while (m -- ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); add(a, b, c); } cout << dijkstra() << endl; return 0; }
Bellman-Ford算法
在求最短路的时候,如果有负权回路,那么最短路径不一定存在
迭代K次以后得到的dist的含义是,从1号点经过不超过k条边到各个点的最短距离
如果迭代n次后,最短路还有更新的话,那么说明存在一条最短路径上面有n条边,那么就一定有n+1个结点,也就是说这个路径上一定存在环路,并且这个环路是负环
#include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 510, M = 10010; struct Edge { int a, b, c; }edges[M]; int n, m, k; int dist[N]; int last[N]; void bellman_ford() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; for (int i = 0; i < k; i ++ ) { memcpy(last, dist, sizeof dist);//每次在进行新的迭代之前,需要将dist数组备份一下,要保证更新的时候只用上一次迭代的结果,last里面存储的就是我上一次迭代的结果 for (int j = 0; j < m; j ++ ) { auto e = edges[j]; dist[e.b] = min(dist[e.b], last[e.a] + e.c); } } } int main() { scanf("%d%d%d", &n, &m, &k); for (int i = 0; i < m; i ++ ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); edges[i] = {a, b, c}; } bellman_ford(); if (dist[n] > 0x3f3f3f3f / 2) puts("impossible"); else printf("%d\n", dist[n]); return 0; }
SPFA算法(对上一个算法进行优化)
求最短路
int n; // 总点数 int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边 int dist[N]; // 存储每个点到1号点的最短距离 bool st[N]; // 存储每个点是否在队列中 // 求1号点到n号点的最短路距离,如果从1号点无法走到n号点则返回-1 int spfa() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; queue<int> q; q.push(1); st[1] = true; while (q.size()) { auto t = q.front(); q.pop(); st[t] = false; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i])//只有当距离变小之后才会更新 { dist[j] = dist[t] + w[i]; if (!st[j]) // 如果队列中已存在j,则不需要将j重复插入 { q.push(j); st[j] = true; } } } } if (dist[n] == 0x3f3f3f3f) return -1; return dist[n]; }
是否存在负环
最坏时间复杂度是 O(nm), n 表示点数,m 表示边数
int n; // 总点数 int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边 int dist[N], cnt[N]; // dist[x]存储1号点到x的最短距离,cnt[x]存储1到x的最短路中经过的点数 bool st[N]; // 存储每个点是否在队列中 // 如果存在负环,则返回true,否则返回false。 bool spfa() { // 不需要初始化dist数组 // 原理:如果某条最短路径上有n个点(除了自己),那么加上自己之后一共有n+1个点,由抽屉原理一定有两个点相同,所以存在环。 queue<int> q; for (int i = 1; i <= n; i ++ )//因为负环不一定是从1开始的,所以要将所有的点都放进去 { q.push(i); st[i] = true; } while (q.size()) { auto t = q.front(); q.pop(); st[t] = false; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; cnt[j] = cnt[t] + 1; if (cnt[j] >= n) return true; // 如果从1号点到x的最短路中包含至少n个点(不包括自己),则说明存在环 if (!st[j]) { q.push(j); st[j] = true; } } } } return false; }
Floyd算法-求最短路
//时间复杂度是 O(n^3), n 表示点数 //初始化: for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) if (i == j) d[i][j] = 0; else d[i][j] = INF; // 算法结束后,d[a][b]表示a到b的最短距离 //(k,i,j)表示从i点只经过从1到k这些中间点,到达点j点的最短距离 void floyd() { for (int k = 1; k <= n; k ++ ) for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); }
#include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 210, INF = 1e9; int n, m, Q; int d[N][N]; void floyd() { for (int k = 1; k <= n; k ++ ) for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } int main() { scanf("%d%d%d", &n, &m, &Q); for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) if (i == j) d[i][j] = 0;//相当于将自环删掉 else d[i][j] = INF; while (m -- ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); d[a][b] = min(d[a][b], c); } floyd(); while (Q -- ) { int a, b; scanf("%d%d", &a, &b); int t = d[a][b]; if (t > INF / 2) puts("impossible"); else printf("%d\n", t); } return 0; }
最小生成树
普利姆算法
朴素普利姆算法(稠密图)-O(n^2)
···
int n; // n表示点数
int g[N][N]; // 邻接矩阵,存储所有边
int dist[N]; // 存储其他点到当前最小生成树的距离
bool st[N]; // 存储每个点是否已经在生成树中
// 如果图不连通,则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim()
{
memset(dist, 0x3f, sizeof dist);
int res = 0; for (int i = 0; i < n; i ++ ) { int t = -1; for (int j = 1; j <= n; j ++ ) if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j; if (i && dist[t] == INF) return INF; if (i) res += dist[t]; st[t] = true; for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]); } return res;
}
···
#include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 510, INF = 0x3f3f3f3f; int n, m; int g[N][N]; int dist[N]; bool st[N]; int prim() { memset(dist, 0x3f, sizeof dist); int res = 0; for (int i = 0; i < n; i ++ ) { int t = -1; for (int j = 1; j <= n; j ++ ) if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j; if (i && dist[t] == INF) return INF; if (i) res += dist[t]; st[t] = true; for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]); } return res; } int main() { scanf("%d%d", &n, &m); memset(g, 0x3f, sizeof g); while (m -- ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); g[a][b] = g[b][a] = min(g[a][b], c); } int t = prim(); if (t == INF) puts("impossible"); else printf("%d\n", t); return 0; }
堆优化普利姆算法(稀疏图)-O(mlogn)
克鲁斯卡尔算法(稀疏图)-O(mlogm)
int n, m; // n是点数,m是边数 int p[N]; // 并查集的父节点数组 struct Edge // 存储边 { int a, b, w; bool operator< (const Edge &W)const { return w < W.w; } }edges[M]; int find(int x) // 并查集核心操作 { if (p[x] != x) p[x] = find(p[x]); return p[x]; } int kruskal() { sort(edges, edges + m); for (int i = 1; i <= n; i ++ ) p[i] = i; // 初始化并查集 int res = 0, cnt = 0; for (int i = 0; i < m; i ++ ) { int a = edges[i].a, b = edges[i].b, w = edges[i].w; a = find(a), b = find(b); if (a != b) // 如果两个连通块不连通,则将这两个连通块合并 { p[a] = b; res += w;//存储最小生成树的边权值 cnt ++ ;//存储最小生成树的边数 } } if (cnt < n - 1) return INF; return res; }
二分图
染色法(判别一个图是不是二分图)-O(m+n)
一个图是二分图,当且仅当图中不含奇数环(环中边的数量是奇数)
int n; // n表示点数 int h[N], e[M], ne[M], idx; // 邻接表存储图 int color[N]; // 表示每个点的颜色,-1表示未染色,0表示白色,1表示黑色 // 参数:u表示当前节点,c表示当前点的颜***ool dfs(int u, int c) { color[u] = c; for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (color[j] == -1) { if (!dfs(j, !c)) return false; } else if (color[j] == c) return false; } return true; } bool check() { memset(color, -1, sizeof color); bool flag = true; for (int i = 1; i <= n; i ++ ) if (color[i] == -1) if (!dfs(i, 0)) { flag = false; break; } return flag; }
匈牙利算法(求二分图的最大匹配)-最坏是O(mn),实际运行时间一般远小于O(mn)
返回二分图中成功匹配的边的最大数,成功匹配是指不存在两条边共用一个顶点
int n1, n2; // n1表示第一个集合中的点数,n2表示第二个集合中的点数 int h[N], e[M], ne[M], idx; // 邻接表存储所有边,匈牙利算法中只会用到从第一个集合指向第二个集合的边,所以这里只用存一个方向的边 int match[N]; // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个 bool st[N]; // 表示第二个集合中的每个点是否已经被遍历过 void add(int a,int b){ e[idx] = b,ne[idx]=h[a],h[a]=idx++; } bool find(int x) { for (int i = h[x]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) { st[j] = true; if (match[j] == 0 || find(match[j]))//该女生没有被匹配或者已经匹配的男生可以找到下家 { match[j] = x; return true; } } } return false; } // 求最大匹配数,依次枚举第一个集合中的每个点能否匹配第二个集合中的点 int res = 0; for (int i = 1; i <= n1; i ++ ) { memset(st, false, sizeof st); if (find(i)) res ++ ; }