1. Toy模板网首页
  2. > Toy博客

算法基础课-搜索与图论

5月前 作者：向来痴_ 分类：Toy博客 阅读(39) 违法举报

这篇具有很好参考价值的文章主要介绍了算法基础课-搜索与图论。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

DFS

题目链接：842. 排列数字 - AcWing题库
思路：写的很好的题解AcWing 842. 排列数字--深度优先遍历代码+注释 - AcWing

#include<bits/stdc++.h>

using namespace std;
int n;
int st[10];
vector<int> a;
void dfs(){
    if(a.size() == n){
        for(int i=0;i<n;i++){
            cout<<a[i]<<" ";
        }
        cout<<endl;
    }
    for(int i=1;i<=n;i++){
        if(!st[i]){
            
            a.push_back(i);
            st[i] = true;
            dfs();
            a.pop_back();
            st[i] = false;
            
        }
    }
}

int main()
{
    cin>>n;
    dfs();
    
    return 0;
}

也可以考虑使用c++自带的next_permutation函数直接秒了：

#include<bits/stdc++.h>
using namespace std;
vector<int> a;
int n;
int st[10];

int main(){
	cin>>n;
	for(int i=0;i<n;i++) st[i] = i+1;
	do{
		for(int i=0;i<n;i++) cout<<st[i]<<" ";
		cout<<endl;
	}while(next_permutation(st,st+n));
	return 0;
}

BFS

题目链接：844. 走迷宫 - AcWing题库

思路：由于bfs是一层一层扩展，所以能保证走到终点时，走过的距离最短，所以不需要取min。可以在bfs中判断一下，走到终点直接输出终点的distance。

算法基础课-搜索与图论,算法,图论,数据结构

算法基础课-搜索与图论,算法,图论,数据结构

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
int n,m;
const int N = 110;
int g[N][N];
int dist[N][N];
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
// int st[N][N];
void bfs(int x,int y){
    queue<PII> q;
    q.push({x,y});
    dist[0][0] = 0;
    // st[x][y] = true;
    while(q.size()){
        auto t = q.front();
        q.pop();
        int x = t.x,y = t.y;
        for(int i=0;i<4;i++){
            int tx = x + dx[i];
            int ty = y + dy[i];
            if(g[tx][ty] == 1) continue;
            if(tx<0||tx>=n||ty<0||ty>=m) continue;
            // if(st[tx][ty]) continue;
            // st[tx][ty] = true;
            g[tx][ty] = 1;
            dist[tx][ty] = min(dist[tx][ty],dist[x][y]+1);
            q.push({tx,ty});
            // cout<<tx<<" "<<ty<<endl;
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++) cin>>g[i][j];
    }
    memset(dist,0x3f,sizeof dist);
    bfs(0,0);
    cout<<dist[n-1][m-1];
    return 0;
}

树与图的深度优先遍历

题目链接：1207. 大臣的旅费 - AcWing题库

思路：题意是求树的直径（树中两个最远结点的距离），可以随机找一个点0，走到距离0点最远的点1，再从这个点1走到距离点1最远的点2，此时点1距离点2的距离就是树的直径。

图的存储与遍历参考：B02 图的存储_哔哩哔哩_bilibili

#include<bits/stdc++.h>
#define x first 
#define y second 

using namespace std;
const int N = 100010;
typedef pair<int,int> PII;
vector<PII> h[N];
int dist[N];
void dfs(int u,int father,int distance){
    dist[u] = distance;
    
    for(auto t:h[u]){
        if(t.x!=father){
            dfs(t.x,u,distance+t.y);
        }
    }
    
}

int main(){
    int n ;
    cin>>n;
    for(int i=0;i<n-1;i++){
        int x,y,d;
        cin>>x>>y>>d;
        h[x].push_back({y,d});
        h[y].push_back({x,d});
    }
    
    dfs(1,-1,0);
    int u = 1;
    for(int i=1;i<=n;i++){
        if(dist[i]>dist[u]){
            u = i;
        }
    }
    dfs(u,-1,0);
    for(int i=1;i<=n;i++){
        if(dist[i]>dist[u]){
            u = i;
        }
    }
    
    int s = dist[u];

    printf("%lld\n", s * 10 + s * (s + 1ll) / 2);

    return 0;
}

树与图的广度优先遍历

题目链接：847. 图中点的层次 - AcWing题库

思路：h数组表示邻接表，下标表示结点编号，每个vector存储的是每个结点能到达的节点。

这个老师讲的超级好。B02 图的存储_哔哩哔哩_bilibili

#include<bits/stdc++.h>

using namespace std;
const int N = 100010;
vector<int> h[N];
bool st[N];
int dist[N];
int n,m;
void bfs(int u){
    queue<int> q;
    q.push(u);
    st[u] = true;
    dist[u] = 0;
    while(q.size()){
        int t = q.front();
        q.pop();
        if(t == n){
            cout<<dist[t];
            return;
        }
        for(int i=0;i<h[t].size();i++){
            int ne = h[t][i];
            if(st[ne]) continue;
            
            st[ne] = true;
            q.push(ne);
            dist[ne] = dist[t] + 1;
        }
    }
    cout<<-1<<endl;
    return;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        h[a].push_back(b);
    }
    memset(dist,-1,sizeof dist);
    bfs(1);
    return 0;
}

拓扑排序

题目链接：848. 有向图的拓扑序列 - AcWing题库
思路：跟bfs有些相似，先找入度为零的点加入到队列当中，再枚举当前结点出边，减少出边元素的入度，当入度为0时加入到拓扑序列中，这里是当出队的时候加入到序列中，跟bfs更像了。

这个老师讲的可好D01 拓扑排序_哔哩哔哩_bilibili。

算法基础课-搜索与图论,算法,图论,数据结构

#include<bits/stdc++.h>

using namespace std;
const int N = 100010;
vector<int> e[N],tp;
int din[N];

int n,m;
bool topsort(){
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(din[i] == 0) q.push(i);
    }
    while(q.size()){
        auto t = q.front();
        q.pop();
        tp.push_back(t);
        for(auto y : e[t]){
            din[y]--;
            if(!din[y]) q.push(y);
        } 
    }
    return tp.size() == n;
}

int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        e[a].push_back(b);
        din[b]++;
    }
    if(topsort()){
        for(int i = 0;i<n;i++){
            cout<<tp[i]<<" ";
        }
    }else cout<<-1<<endl;
    
    return 0;
}

Dijkstra

朴素版

题目链接：849. Dijkstra求最短路 I - AcWing题库
思路：采取贪心的策略，对当前能到达的路径最短的点，使用其进行更新距离操作。

D02 最短路 Dijkstra 算法_哔哩哔哩_bilibili

算法基础课-搜索与图论,算法,图论,数据结构

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 510;
const int M = 1e5+10;
vector<PII> e[N];
int dist[N];
int n,m;
bool st[N];
void dijkstra(int s){
    dist[s] = 0;
    
    for(int i=1;i<n;i++){
        int u = 0;
        for(int i=1;i<=n;i++){
            if(!st[i]&&(dist[i]<dist[u] || u == 0)) u = i;
        }
        // cout<<u<<endl;
        st[u] = true;
        for(auto pr : e[u]){
            int v = pr.x, w = pr.y;
            if(dist[v]>dist[u]+w){
                dist[v] = dist[u] + w;
            }
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b,w;
        cin>>a>>b>>w;
        e[a].push_back({b,w});
    }
    memset(dist,0x3f,sizeof dist);
    dijkstra(1);
    if(dist[n] == 0x3f3f3f3f) cout<<-1<<endl;
    else cout<<dist[n]<<endl;
    return 0;
}

堆优化版本

题目链接：850. Dijkstra求最短路 II - AcWing题库

思路：每次选秀选出当前最小的点，朴素版需要遍历寻找，堆优化版使用优先队列维护当前没有遍历到的距离最小的点，将每次选秀的遍历替换成取队列头部元素，从而降低时间复杂度。

需要注意的是为了维护优先队列中的顺序，存储的距离为负数。

D02 最短路 Dijkstra 算法_哔哩哔哩_bilibili

算法基础课-搜索与图论,算法,图论,数据结构

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
int n,m;
typedef pair<int,int> PII;
const int N = 150010, M = 150010;
int dist[N];
priority_queue<PII> q;
vector<PII> h[N];
bool st[N];
void dijkstra(int s){
    dist[s] = 0;
    q.push({0,s});
    while(q.size()){
        PII p = q.top();
        int u = p.y;
        q.pop();
        if(st[u]) continue;
        st[u] = true;
        for(auto t : h[u]){
            int v = t.x, w = t.y;
            if(dist[v]>dist[u] + w){
                dist[v] = dist[u] + w;  //忘记更新距离
                q.push({-(dist[u]+w),v});
            }
        }
        
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        h[a].push_back({b,c});
    }
    memset(dist,0x3f,sizeof dist);
    dijkstra(1);
    if(dist[n] == 0x3f3f3f3f) cout<<-1<<endl;
    else cout<<dist[n]<<endl;
    return 0;
}

bellman-ford

spfa

Floyd

题目链接：854. Floyd求最短路 - AcWing题库

思路：D04 最短路 Floyd 算法_哔哩哔哩_bilibili
算法基础课-搜索与图论,算法,图论,数据结构

#include<bits/stdc++.h>
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(){
	cin>>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;
		cin>>a>>b>>c;
		d[a][b] = min(d[a][b],c);
	}
	floyd();
	while(Q--){
		int a,b;
		cin>>a>>b;
		int t = d[a][b];
		if(t>INF/2) cout<<"impossible"<<endl;
		else cout<<t<<endl;
	}
	return 0;
}

Prim

题目链接：858. Prim算法求最小生成树 - AcWing题库

思路：D07 最小生成树 Prim 算法_哔哩哔哩_bilibili

和dijkstra一样，n次循环，每次选取最近的点来更新距离。

算法基础课-搜索与图论,算法,图论,数据结构

#include<bits/stdc++.h>
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(){
	cin>>n>>m;
	memset(g,0x3f,sizeof g);
	while(m--){
		int a,b,c;
		cin>>a>>b>>c;
		g[a][b] = g[b][a] = min(g[a][b],c);
	}
	int t = prim();
	if(t==INF) cout<<"impossible"<<endl;
	else cout<<t<<endl;
	return 0;
}

Kruskal

题目链接：859. Kruskal算法求最小生成树 - AcWing题库

思路：Kruskal算法是根据边求取最小生成树，先按边权排序，依次取权重最小的边，查看边的起点和终点是否在同一集合中（使用并查集），若不在同一集合，则将边加入到答案中，若在同一集合则继续循环。D08 最小生成树 Kruskal 算法_哔哩哔哩_bilibili

需要注意的是重载小于号的操作要记一下。

#include<bits/stdc++.h>
// #define x first
// #define y second
using namespace std;
// typedef pair<int,int> PII;
int n,m;
const int N = 1e5+10,M = 2e5+10;
struct edge{
    int u;int v;int w;
    bool operator<(const edge &t)const{
        return w<t.w;
    }
}e[M];
// vector<edge> e;
int fa[N];
int find(int x){
    if(x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        e[i] = {a,b,c};
    }
    int ans = 0;
    int cnt = 0;
    sort(e,e+m);
    for(int i=1;i<=n;i++) fa[i] = i;
    for(int i=0;i<m;i++){
        int u = e[i].u;
        int v = e[i].v;
        int w = e[i].w;
        if(find(u)!=find(v)){
            ans += w;   
            fa[find(u)] = find(v);
            cnt++;
        }
    }
    if(cnt == n-1) cout<<ans<<endl;
    else cout<<"impossible"<<endl;
    
    return 0;
}

染色法判定二分图

题目链接：860. 染色法判定二分图 - AcWing题库
思路：二分图的意思是看是否有能将所有节点分成两块，每块的节点中不能直接相连这样的情况存在。如下图中的1,4和2,3,5。根据定理：二分图中不存在奇环，我们可以由此判别一个图是否是二分图。D24 二分图判定 染色法_哔哩哔哩_bilibili

算法基础课-搜索与图论,算法,图论,数据结构

老师使用的是链式前向星存储的图结构，具体思路如下。感觉直接用邻接表存储更好想，也更简便。

算法基础课-搜索与图论,算法,图论,数据结构文章来源地址https://www.toymoban.com/news/detail-851752.html

#include<bits/stdc++.h>

using namespace std;
int n,m;
const int N = 100010,M = 100010;
vector<int> h[N];
int color[N];
bool dfs(int u,int c){
    color[u] = c;
    for(auto t : h[u]){
        if(!color[t]){
            if(dfs(t,3-c)) return 1;
        }else if(color[t] == c) return 1;
    }
    return 0;
}

int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        h[a].push_back(b);
        h[b].push_back(a);
    }
    bool flag = false;
    for(int i =1;i<=n;i++){
        if(!color[i]){
            if(dfs(i,1)){
                flag = 1;
                break;
            }
        }
    }
    if(flag) puts("No");
    else puts("Yes");
    return 0;
    
}

匈牙利算法

到了这里，关于算法基础课-搜索与图论的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 算法基础课——基础算法（模板整理）

     快速排序 快速排序 第K个数 归并排序   归并排序 逆序对的数量 二分   数的范围 数的三次方根 高精度   高精度加法 Python一行就可以解决 高精度减法 高精度乘法 高精度除法 前缀和与差分 前缀和 子矩阵的和 差分 差分矩阵 双指针算法 最长连续不重复子序列 数组元素的目

    2024年02月12日
    浏览(28)
  • 搜索与图论（acwing算法基础）

    搜索与图论（acwing算法基础）

    排列数字 n皇后 走迷宫 单链表 点击跳转至例题 idx存的是指针 树与图的深度优先搜索 树的重心 每个节点都是一个单链表 模拟队列 hh = 0 , tt = -1 有向图的拓扑序列 都是从前指向后,即有向无环图（不能有环） 所有入度为0的点，都能排在前面的位置 删掉t-j的边，仅仅是j的入度

    2024年02月08日
    浏览(31)
  • ACWing算法基础课

    ACWing算法基础课

    y总说 java不能用Scanner读入，要用Buffer.read();快十倍二十倍； y总19年5月的视频，牛13！ 包括排序、二分、高精度、前缀和与差分、双指针算法、位运算、离散化、区间合并等内容。 一定要先移动end（就是把大数移到右边），后移动start； 否则 先找小数，会出现end start重合位置

    2024年02月13日
    浏览(31)
  • 【算法基础：搜索与图论】3.3 拓扑排序

    【算法基础：搜索与图论】3.3 拓扑排序

    https://oi-wiki.org/graph/topo/ 本文主要学习拓扑排序相关知识。 拓扑排序的英文名是 Topological sorting。 拓扑排序要解决的问题是给一个 有向无环图 的 所有节点排序 。 我们可以拿大学每学期排课的例子来描述这个过程，比如学习大学课程中有：程序设计，算法语言，高等数学，

    2024年02月16日
    浏览(34)

  • acwing算法基础之搜索与图论--kruskal算法

    kruskal算法的关键步骤为： 将所有边按照权重从小到大排序。 定义集合S，表示生成树。 枚举每条边(a,b,c)，起点a，终点b，边长c。如果结点a和结点b不连通（用并查集来维护），则将这条边加入到集合S中。 kruskal算法的时间复杂度为O(mlogm)，它用来解决稀疏图的最小生成树问题

    2024年02月05日
    浏览(33)
  • 算法基础课第五讲 动态规划

    算法基础课第五讲 动态规划

    时间复杂度：状态数量 转移的计算量 * 总体概述：给一堆物品，有体积有价值。有一个背包，在背包能装下的前提下最终能装下多少（背包不一定要装满） DP问题：一般需要从两方面考虑：状态表示以及状态计算 状态表示：f(i,j) 从两个方面考虑：集合（所有选法的集合）（

    2024年02月01日
    浏览(29)
  • Acwing-基础算法课笔记之搜索与图论

    Acwing-基础算法课笔记之搜索与图论

    bellman-ford算法适用于负权边的图，求 1 到 n 的最多经过k条边的最短距离。 如图所示： 1 2 3 dist 0 ∞ infty ∞ ∞ infty ∞ ⇓ Downarrow ⇓ 1 2 3 dist 0 1 ∞ infty ∞ ⇓ Downarrow ⇓ 1 2 3 dist 0 1 2 此过程中出现了串联的结果，所以是错误的，此时需要进行备份操作。 备份操作如下： 为了

    2024年01月20日
    浏览(38)
  • 【算法基础：搜索与图论】3.2 树与图的dfs和bfs

    【算法基础：搜索与图论】3.2 树与图的dfs和bfs

    要学会建树、建图的通用方法。 dfs 和 bfs 的代码框架。 https://www.acwing.com/problem/content/848/ 在 dfs 的过程中，统计各个节点作为断点时的连通块最大值。 https://www.acwing.com/problem/content/849/ 看到最短距离就可以想到使用宽搜。 注意！ ：题目中说明了 a 和 b 表示存在一条从 a 走到

    2024年02月16日
    浏览(28)
  • 【algorithm】算法基础课---二分查找算法（附笔记 | 建议收藏）

    【algorithm】算法基础课---二分查找算法（附笔记 | 建议收藏）

    🚀write in front🚀 📝个人主页：认真写博客的夏目浅石. 🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝 📣系列专栏：AcWing算法学习笔记 💬总结：希望你看完之后，能对你有所帮助，不足请指正！共同学习交流 🖊 ✉️ 如果无聊的话，就来逛逛我的博客栈吧 stack-frame.cn 关于我

    2024年01月18日
    浏览(27)
  • 【AcWing算法基础课】第五章 动态规划（未完待续）

    【AcWing算法基础课】第五章 动态规划（未完待续）

    本专栏文章为本人AcWing算法基础课的学习笔记，课程地址在这。如有侵权，立即删除。 dp问题的优化 ：在基本形式dp上作等价变形。 dp问题的解题方法 ： 1）状态表示 集合 属性：最大值/最小值/数量。 2）状态计算 集合划分（不重不漏） 题目链接： 2. 01背包问题 - AcWing题库

    2024年02月12日
    浏览(33)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包