哈喽~大家好呀,上篇呢我们将了排序算法(一),后台有小伙伴私信说,追呀,啥时候更新下一篇呀?这不今天它来了,(它来了,它来了,它穿着大裤衩走来了),那么这篇呢我们来看最有趣的算法(二)。

 个人主页:个人主页​​​​​        

 系列专栏:【算法】​​​​​​      

与这篇算法相关的文章:

恭喜你~遇到了最有趣的排序算法(一)恭喜你~遇到了最有趣的排序算法(一)_一个名叫追的程序猿的博客-CSDN博客
客官,520到来之际,HTML 表白biu~代码何不来看看?客官,520到来之际,HTML 表白biu~代码何不来看看?_一个名叫追的程序猿的博客-CSDN博客
关于汇编语言入门的几个案例关于汇编语言入门的几个案例_一个名叫追的程序猿的博客-CSDN博客

目录

一、深度优先搜索

实际问题

二、广度优先搜索

实际问题

三、prim 算法

实际题目

四、Kruskal算法

实际题目

五、小结


一、深度优先搜索

深度优先搜索(DFS)又叫深搜,我们可以这么理解,DFS 像一个很固执的一个人(不撞南墙不回头,不见黄河不死心),只要你这里有路我就一定会去走,而且一条路走到底的那种(燕子~没你我怎么活呀,开玩笑了)。

我们先来看看效果图。(对了,上次有小伙伴问,你这效果图是怎么实现的呀,我是在这个网站上绘制效果图的)

看完效果图后感觉是不是挺通俗易懂的?好,我们来看看 DFS 的模板。

dfs(int u){if(找到了||走不下去了){return;}开始下一个情况(dfs(u+1));}

实际问题

我们来看看一个经典的问题——n皇后问题。我们先来看看题目。

给定一个n*n的棋盘,棋盘中有一些位置不能放皇后。
现在要向棋盘中放入n个黑皇后和n个白皇后,使任意的两个黑皇后都不在同一行、同一列或同一条对角线上
任意的两个白皇后都不在同一行、同一列或同一条对角线上。

我们来看看代码

#include #include using namespace std;typedef long long ll;const int N = 20;int n;char g[N][N];int l[N],ug[N],ng[N];void dfs(int u){if(u == n){for(int i = 0; i < n; i ++){cout << g[i] << endl;}cout << endl;return ;}for(int i = 0; i > n;for(int i = 0; i < n; i ++){for(int j = 0; j < n; j ++) {g[i][j] = '.';}}dfs(0);return 0;}

二、广度优先搜索

广度优先搜索(BFS)又叫广搜,它像一个有远见的人,它是一层一层来实现搜索的,也挺像下楼梯的。

思路:

  1.先初始化队列 q;
  2.从起点开始访问,并且改变他的状态为已经访问;
  3.如果他的队列非空,取出首个元素,将它弹出!
  4.如果u == 目标状态,然后对所以与 u 邻近的点进入队列;
  5.标记它已经被访问!

我们先来看看效果图

我们来看看模板

queue q;st[0] = true; // 表示1号点已经被遍历过q.push(0);while (q.size()){int t = q.front();q.pop();for (int i = h[t]; i != -1; i = ne[i]){int j = e[i];if (!s[j]){st[j] = true; // 表示点j已经被遍历过q.push(j);}}}

实际问题

来看看代码

#include #include #define x first#define y secondusing namespace std;const int N = 1000 + 10;int n;typedef pair PII;PII q[N * N];bool st[N][N];char g[N][N];int dx[4] = {-1, 0, 1, 0},dy[4] = {0, 1, 0, -1};void bfs(int sx, int sy, int &tl, int &bd){int tt = 0,hh = 0;st[sx][sy] = true;q[0] = {sx, sy};while(hh <= tt){PII t = q[hh ++];tl ++;bool is_bd = false;for(int i = 0; i < 4; i ++){int x = t.x + dx[i],y = t.y + dy[i];if(x = n || y = n || st[x][y]) continue;if(g[x][y] == '.'){is_bd = true;continue;}st[x][y] = true;q[++ tt] = {x, y};}if(is_bd) bd++;}}int main(){ cin >> n;for(int i = 0;i > g[i]; int cnt= 0; for(int i = 0;i < n;i++)for(int j = 0;j < n;j++){if(!st[i][j] && g[i][j] == '#'){int tl = 0,bd = 0;bfs(i, j, tl, bd);if(tl == bd) cnt ++;}}cout << cnt << endl;return 0;}

看到这里感觉这么样?对 dfs 与 bfs 有了更新的认识吗?我们接下来再来看看两大算法。

扩展:什么是最小生成树?

给定一个无向图,如果它的某个子图中任意两个顶点都互相连通并且是一棵树,那么这棵树就叫生成树。如果边上有权值,那么使得边权和最小的生成树叫做最小生成树(MST,Minimum Spanning Tree)。

那么下面我们要讲的两大算法就是与最小生成树有关的。

三、prim 算法

prim 算法也像一个有远见的人,他选择一个节点(假设这个节点上有 n 条边),直接来找这 n 条边上最小的边,然后选择这条最小的边选完之后剩下(n – 1)。再选择连接的最小的边的节点(假设这个节点上有 m 条边)(在 m + n – 1 条边是哪个选择)。选完之后剩下(m + n – 2),依次类推。我们来看看效果图。

 算法模板

int prim(){memset(dist, 0x3f, sizeof dist);int res = 0;dist[1] = 0;for(int i = 0; i < n; i ++){int t = -1;for(int j = 1; j <= n; j ++)if(!st[j] && (t == -1 || dist[j] < dist[t])) t = j; st[t] = true; res += dist[t];for(int j = 1; j  g[t][j] && !st[i]){dist[j] = g[t][j];pre[j] = t;}}return res;}

实际题目

给定一个n个点m条边的无向图,图中可能存在重边和自环,边权可能为负数。

求最小生成树的树边权重之和,如果最小生成树不存在则输出 impossible。

给定一张边带权的无向图G=(V, E),其中V表示图中点的集合,E表示图中边的集合,n=|V|,m=|E|。

由V中的全部n个顶点和E中n-1条边构成的无向连通子图被称为G的一棵生成树,其中边的权值之和最小的生成树被称为无向图G的最小生成树。

这里我们看到上面的效果图,我们可以构成一组数据,如果这组数据没有输出 impossible,那么它存在最小生成树。

9 160 1 80 2 121 4 91 3 251 2 132 6 212 3 142 6 123 5 83 7 123 8 164 5 194 3 205 7 117 8 66 8 11

四、Kruskal算法

Kruskal算法它很像一个比较莽撞的人,它直接选择最短的边,只要它满足最小生成树的条件,那么这条边就可行。 我们先来看看效果图。

思路:

①将所有边按权重从小到大排序

②枚举每条边 a,b,权重是c

if a,b不连通 

​    将这条边加入集合

实际题目

同样是上面的题目与数据

给定一个n个点m条边的无向图,图中可能存在重边和自环,边权可能为负数。

求最小生成树的树边权重之和,如果最小生成树不存在则输出 impossible。

给定一张边带权的无向图G=(V, E),其中V表示图中点的集合,E表示图中边的集合,n=|V|,m=|E|。

由V中的全部n个顶点和E中n-1条边构成的无向连通子图被称为G的一棵生成树,其中边的权值之和最小的生成树被称为无向图G的最小生成树。

我们来看看代码是如何实现的。

#includeusing namespace std;const int N = 2e5+5;int n,m;struct Edge{int u, v, w;bool operator<(const Edge &a) const{return w

 用同样的数据,不同的算法得到相同的结果,没毛病。

五、小结

我们来看看时间复杂度的分析

BFS的复杂度分析
最坏的情况下,空间复杂度为O(v)。

每个顶点均需搜索一次,时间复杂度T1=O(v),每条边至少访问1次,时间复杂度为O(E),算法总的时间复 度为O(|V|+|E|)。

查找每个顶点的邻接点所需时间为O(V),即该节点所在的该行该列。又有n个顶点,故算总的时间复杂度为O(|V|^2)。

DFS复杂度分析
它的空问复杂度为O(V)。

查找所有顶点的邻接点所需时间为O(E),访问顶点的邻接点所花时间为O(V),此时,总的时间复杂度为O(V+E)。

查找每个顶点的邻接点所需时间为O(V),要查找整个矩阵,故总的时间度为O(V^2)。 

注意: v为图的顶点数,E为边数。

快期末了,接下来的时间会比较紧,更新频率可能会比以前低了,见谅解。

(求关注)持续更新中……