家具网站php源码,小网站推荐一个,响应式布局模板网站免费下载,浙江省城乡住房建设网站算法基础第三章 1、dfs(深度搜索)1.1、 递归回溯1.2、递归剪枝#xff08;剪枝就是判断接下来的递归都不会满足条件#xff0c;直接回溯#xff0c;不再继续往下无意义的递归#xff09; 2、bfs(广度搜索)2.1、最优路径#xff08;只适合于边权都相等的题#xff09; 3、… 算法基础第三章 1、dfs(深度搜索)1.1、 递归回溯1.2、递归剪枝剪枝就是判断接下来的递归都不会满足条件直接回溯不再继续往下无意义的递归 2、bfs(广度搜索)2.1、最优路径只适合于边权都相等的题 3、邻接表存储树和图(邻接表就是单链表 3.1、深度优先遍历特殊的深搜3.2、宽度优先遍历特殊的宽搜3.3、有向图的拓扑序列(有环的有向图不可能是拓扑序列) 4、最短路4.1、单源最短路4.1.1、所有边权都是整数4.1.2、存在负权边 4.2、多源汇最短路 5、最小生成树5.1、prim算法5.2、Kruskal算法稀疏图 6、二分图6.1、染色法6.2、匈牙利算法 1、dfs(深度搜索)
1.1、 递归回溯
解析下图为123三个数的全排列过程从0层开始一直往下递归直到数的个数用完每次使用了一个数需要将这个数标记为已使用过回溯的时候再恢复为未使用过。 题目链接一个数的全排列代码
#include iostream
#includestdio.h//加了这个头文件时间快了1msusing namespace std;const int N 7;
bool use[N];//这个数被用过的话则记为true排列的时候位置上只能放没被用过的
int path[N],n;
void dfs(int num)
{if(num n)//输入3,怎有3个空位排列填满之后就输出{for(int i 0; i n; i){printf(%d ,path[i]);}puts();return;}for(int i 1; i n; i){if(!use[i]){path[num] i;use[i] true;dfs(num 1);use[i] false;}}
}int main() {cin n;dfs(0);//从0开始return 0;
}1.2、递归剪枝剪枝就是判断接下来的递归都不会满足条件直接回溯不再继续往下无意义的递归
解析题目链接n皇后问题代码代码并没有全a路过的大佬可以给个补充
#include iostream
using namespace std;const int N 20;
int n;
bool col[N],dg[N],udg[N];
long long ret;void dfs(int num)
{if(num n){ret;return;}for(int i 0; i n; i){if(!col[i] !dg[inum] !udg[n-numi]){col[i] dg[inum] udg[n-numi] true;dfs(num1);col[i] dg[inum] udg[i-numn] false;}}
}
int main() {scanf(%d,n);dfs(0);printf(%lld,ret);
}2、bfs(广度搜索)
//基本框架伪代码
queue_init;
while(!queue.empty())
{t queue.pop();//弹出队头元素queue.push(t.child-node);//这里包括左右子节点
}2.1、最优路径只适合于边权都相等的题
解析题目链接走迷宫代码
#include iostream
#include algorithm
#include cstringusing namespace std;typedef pairint,int PII;const int N 1010;
char g[N][N];//存储地图数据
int d[N][N];//存储距离
int n,m,posx1,posy1,posx2,posy2;//传入的行和列数以及起始终止点的位置
PII q[N*N];//数组模拟队列需要开元素的个数的大小int bfs(int posx2,int posy2)
{int hh0,tt0;//队头和队尾指针q[0] {posx1-1,posy1-1};//队列初始化放入起始位置的坐标memset(d,-1,sizeof d);//d初始化为-1-1表示这个位置还未经过sizeof(d) N*N*4,int是个字节所以乘4d[posx1-1][posy1-1] 0;//起始位置与自己的距离是0int dx[4] {-1,0,1,0},dy[4] {0,1,0,-1};//四个方向的移动x和y的坐标的变化while(hh tt)//队列非空{auto t q[hh];//弹出队头元素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] . d[x][y] -1)//这个点未走过且在边界内且无障碍物{d[x][y] d[t.first][t.second] 1;//这个点与起始位置的点的距离在上一个点的距离上加1q[tt] {x,y};//从队尾压入新的位置的坐标}if(d[posx2-1][posy2-1] ! -1)//表示到达终止点返回{return d[posx2-1][posy2-1];}}}return -1;
}
int main()
{scanf(%d%d%d%d%d%d,n,m,posx1,posy1,posx2,posy2);getchar();for(int i 0; i n; i){for(int j 0; j m; j){scanf(%c,g[i][j]);}getchar();//读取换行符}printf(%d,bfs(posx2,posy2));return 0;
}3、邻接表存储树和图(邻接表就是单链表
树是特殊的有向图是无环连通图无向图也是一种特殊的有向图是双向的邻接表的存储代码
#includecstring
#includeiostream
#includealgorithmusing namespace std;const int N 100010,M N*2;
int h[N],e[M],ne[M],idx;/* a被插入的节点* b新插入的节点之后有a指向b的边*/
void add(int a,int b)
{e[idx] b, ne[idx] h[a],h[a] idx;
}
int main()
{memset(h,-1,sizeof h);//h数组是图里面的节点初始都是指向-1也就是相当于nullptr
}3.1、深度优先遍历特殊的深搜
解析有向图的遍历深度遍历逮住一个起点一直往下递归每个点只遍历一次直到结束再回溯再递归一直遍历完所有的点 题目链接未找到对应的题目贴上acwing原题 题目解析图中的无向图可以看到左图删除节点1有三个连通域大小分别是341最大值为4我们只需要遍历节点1 的子节点就能得到三个大小。右图删除节点4三个连通域大小分别为521上面连通域的大小我们只要求出节点4的子节点数用总数减去就能得到。那对应的每删除一个节点都有相应的连通域要求出这些连通域中最大值中的最小值。 代码解析下面的代码初看是有点绕的图中举了一个较短的例子遍历可以先把数组的内容全都列出来假设从1节点开始1dfs(1)ih[1]2je[2]32dfs(3)ih[3]3je[3]1continue3ine[3]-14ine[2]0je[0]25dfs(2)ih[2]6je[6]56dfs(5)ih[5]7je[7]2continue7ine[7]-18ine[6]4je[4]49dfs(4)ih[4]5je[5]2continue10ine[5]-111ine[4]1je[1]1continue12ine[1]-1结束。遍历的顺序是1-3--1再返回1接着1-2-5--1再返回2接着2-4--1再返回22再返回11--1结束遍历。可以看到3的ne保存这到2路径也就是直接从1到2中间省去了1。 代码acwing源码
#include cstdio
#include cstring
#include iostream
#include algorithmusing namespace std;const int N 100010, M N * 2;//因为需要建立两份边所以 M 2 * N;int n;
int h[N], e[M], ne[M], idx;
int ans N;
bool st[N];
//添加边的模板要求熟练的默写这部分的解释在 链表 专题中
void add(int a, int b)
{e[idx] b, ne[idx] h[a], h[a] idx ;
}
//返回以u为根的子树中节点的个数包括u节点
int dfs(int u)
{st[u] true;int size 0, sum 0;//size存储的是以u为根的数的一个子儿子的节点数的最大值//sun存储以u为根的树的节点数, 包括ufor (int i h[u]; i ! -1; i ne[i]){int j e[i];if (st[j]) continue;int s dfs(j); //s存储的就是以 j 为根的子树的节点数包括 jsize max(size, s); //每次找出最大的子图的节点数sum s; //以j为根的树的节点数}size max(size, n - sum - 1); //求 dfs 遍历的所有子树中最大的节点数的个数和 dfs 未遍历的那棵树的节点数的最大值ans min(ans, size);return sum 1; //这里返回的个数加上根节点
}int main()
{scanf(%d, n);memset(h, -1, sizeof h);for (int i 0; i n - 1; i ){int a, b;scanf(%d%d, a, b);add(a, b), add(b, a); //处理无向图的添边方式}dfs(1); //可以选择任意一个点开始进行 dfs又u n且 n 的最小值为1所以只能从 1 开始//当然本题数据是从 5 开始的所以对于本题写 dfs (1 ~ 5)均可ACprintf(%d\n, ans);return 0;
}
3.2、宽度优先遍历特殊的宽搜
解析套用宽度优先搜索的模板逮住一个点开始遍历所有的节点看保存的节点个数是否和输入的相等相等的话则是全连通的否则不是题目链接宽度优先遍历代码
#include iostream
#includecstring
#includealgorithmusing namespace std;const int N 1010,M N * 2;//因为无向图需要建立两份边所以 M 2 * N;
int e[M],ne[M],h[N];
int n,m,idx;int bfs()//广度优先遍历
{int hh0,tt0;//队头和队尾指针int q[N];//数组模拟队列bool st[N];//是否遍历过标记q[0] 1;//队列初始化模板步骤st[1] true;//这个元素被遍历过了int ret 0;//保存节点数while(hh tt)//队列不为空{int t q[hh];//弹出队头for(int i h[t]; i ! -1; i ne[i])//按照边去遍历{int j e[i];if(st[j])continue;elsest[j] true,ret,q[tt] j;//该节点未被遍历过则压进队尾标记被遍历节点数加1}}return ret1;//因为开始的节点本身没被算进去需要加1
}
void add(int x,int y)//无向图的建立前面已经解释过了
{e[idx] y,ne[idx] h[x],h[x] idx;
}int main() {memset(h,-1,sizeof h);while(cin n m){if(!n !m)break;while(m--){int x,y;cin x y;add(x,y),add(y,x);//建立双边}if(bfs()n){cout YES endl;memset(h,-1,sizeof h);//因为输入是有很多图的处理完一个无序图需要重新清空准备处理下一个无序图memset(e,0,sizeof e);memset(ne,0,sizeof ne);idx 0;}else{cout NO endl;memset(h,-1,sizeof h);memset(e,0,sizeof e);memset(ne,0,sizeof ne);idx 0;}}
}3.3、有向图的拓扑序列(有环的有向图不可能是拓扑序列)
入度一个点有多少指向自己的边出度一个点有多少边从自己这出去解析当一个图按拓扑序排好之后起点一定是在终点的前面如图中所示当按123排序就是一个拓扑序列所有边的起点都在终点的前面。当求解一个有向图是否能够组成拓扑排序的时候也就是看看能否将所有的节点的入度都处理为0能的话就能拓扑排序否则就不能 题目连接拓扑排序代码
#include iostream
#includecstring
#includealgorithmusing namespace std;const int N 200010;int e[N],ne[N],h[N];
int d[N];
int n,m,idx;
int q[N];//宽搜的模板队列void add(int x,int y)//图的构建
{e[idx] y,ne[idx] h[x],h[x] idx;
}bool tuposort()//拓扑排序
{int hh 0,tt -1;for(int i 1; i n; i){if(!d[i])q[tt] i;//首先把所有入度为0的点压入队列}while(hh tt)//宽搜模板{int t q[hh];//弹出队头元素还在数组里面只是用了头尾指针来表示弹出与压入for(int i h[t]; i ! -1; i ne[i])//宽搜遍历这个是有向图不会重复遍历{int j e[i];d[j]--;//该节点的入度减1if(d[j] 0)q[tt] j;//该节点入度变为0之后就压入队列}}return tt n-1;//所有的点都能够被入队说明是一个有向无环图即能构成拓扑排序
}int main() {memset(h,-1,sizeof h);scanf(%d%d,n,m);while(m--){int x,y;cin x y;add(x,y);d[y];//保存这个点的入度}if(tuposort()){for(int i 0; i n; i){if(i!n-1)printf(%d ,q[i]);else printf(%d,q[i]);//答案最后有一个数不能有空格有空格提交不成功}}else {printf(%d,-1);//无拓扑排序输出-1}
}4、最短路
4.1、单源最短路
求一个点到其他所有点的最短路
4.1.1、所有边权都是整数
朴素Dijkstra稠密图邻接矩阵m(边数)~n^2(点数) 模板 1.dist[1] 0dist[i] 正无穷2.for i 1~n(迭代) t-不在s中的距离最近的点s-t//s是当前已确定最短距离的点用t更新其他点的距离 题目链接Dijkstra求最短路径代码
class Solution {
public:int networkDelayTime(vectorvectorint times, int n, int k) {const int inf INT_MAX/2;//构建邻接矩阵int g[n][n];memset(g,0x3f3f3f3f,sizeof g);//这里初始化后的值不等于inffor(auto t:times){int x t[0]-1,y t[1]-1;g[x][y] min(g[x][y],t[2]);}
-
- //存储距离的数组初始化为g数组一样的最大值vectorintdist(n,0x3f3f3f3f);//保存距离dist[k-1] 0;//k是出发点将出发点的距离设为0数组中的坐标与节点值是-1的关系vectorint st(n,0);//保存是否遍历过的标记for(int i 0; i n;i)//这个循环是遍历n个节点{int t -1;for(int j 0; j n; j)//这个循环是找到出发点{if(!st[j] (t -1 || dist[j] dist[t])){t j;}}st[t] true;//标记这个点被遍历了for(int j 0; j n; j)//这个循环是计算出出发点最到他点的最短距离{dist[j] min(dist[j],dist[t] g[t][j]);}}int ans *max_element(dist.begin(),dist.end());return ans 0x3f3f3f3f ? -1 : ans;}
};堆优化版的Dijkstra算法稀疏图邻接表m(边数)~n(点数) 解析堆优化版的改进是在朴素版的基础上在for循环找到目标最近点用堆来替代从而减小时间复杂度题意中可以看到n和m的数量级是相等的因此是稀疏图用邻接表来做题目链接未找到acwing原题 代码
#include iostream
#include algorithm
#include cstring
#includevector
#includequeueusing namespace std;typedef pairint,intPII;const int N 1e610;int n,m;
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_queuePII, vectorPII, greaterPII heap;//优先队列定义一个小根堆heap.push({0,1});//整个代码就是邻接表加宽搜模板初始化队列while(heap.size()){auto t heap.top();//取出队头heap.pop();//弹出队头int ver t.second,distance t.first;if(st[ver])continue;//是否已经遍历过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);//添加有向边}printf(%d\n,dijkstra());return 0;
}4.1.2、存在负权边
Bellman-Ford算法 模板 for n 次 for 所有边abw dist[b] min(dist[b],dist[a]w) 题目链接bellman-ford模板算法代码
class Solution {
public:int findCheapestPrice(int n, vectorvectorint flights, int src, int dst, int k) {int m flights.size();//写成int m flights.size()10; int dist[m],backup[m];会报错int dist[m10],backup[m10];//为了防止超出数组界限所以在长度上加10memset(dist,0x3f,sizeof dist);dist[src] 0;//从哪个点开始那个点起始的距离为0for(int i 0; i k1; i)//这里k是中转站点而不是边数所以是k1因为得加上起点{memcpy(backup,dist,sizeof dist);//加备份防止出现串联for(int j 0; j m; j){auto t flights[j];dist[t[1]] min(dist[t[1]],backup[t[0]] t[2]);//防止串联因为要满足k的限制所以必须保证不能用这次的更新去更新后面的距离}}if(dist[dst] 0x3f3f3f3f/2) return -1;else return dist[dst];}
};SPFA算法 使用宽搜的队列对Dellman-Ford算法的改进使用SPFA判断负环也能用于Dijkstra算法解决的最短路径问题 题目链接判断负环
#include iostream
#include queue
#include cstringusing namespace std;const int N 210,M 2010;
int n,m,a,b,c;
int h[N],e[M],ne[M],w[M],idx;
int dist[N],cnt[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;
}bool spfa()
{queueintq;memset(dist,0x3f,sizeof dist);dist[1] 0;//因为能到达的话是输出从1号点到n号点的距离所以1号点的距离初始化为0for(int i 1; i n; i){st[i] true;q.push(i);//先把所有的点入队列}while(q.size()){int 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;//cnt里面存的是边数如果边数大等于n那么点数大等于n1因为只有n个点所以一定是有环的if(!st[j]){q.push(j);st[j] true;}}}}return false;
}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);}if(spfa())puts(circle);else{if(dist[n] 0x3f3f3f3f) puts(cant arrive!);elsecout dist[n];}
}4.2、多源汇最短路
源起点汇终点任选两个点求这两个点之间的最短路Floyd算法 模板用邻接矩阵存储边 d[i,j] for(k1;kn;k) for(i1; im; i) for(j1; jn; j) d[i,j] min(d[i,j],d[i,j] d[k,j]);//使用了动态规划的原理 题目链接Floyd算法代码
在这里插入代码片5、最小生成树
5.1、prim算法 朴素版稠密图 模板 dist[i]-inffor(i0;in;i) t-找到集合外距离最近的点用t更新其他点到集合的距离st[t] true; 解析起始每个点存储的距离初始化都是inf随后随便找到一个点开始图中从1开始用1到其他点的距离去更新各个点存储的距离然后1被放入集合 堆优化版一般不用
5.2、Kruskal算法稀疏图
6、二分图
6.1、染色法
6.2、匈牙利算法
