【算法笔记】有关图的搜索

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【算法笔记】有关图的搜索，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5796字，纯文字阅读大概需要9分钟。

内容图文

1、广度优先搜索

【BFS】广度优先搜索算法

广度优先搜索BFS（Breadth First Search）也称为宽度优先搜索，它是一种先生成的结点先扩展的策略。
在广度优先搜索算法中，解答树上结点的扩展是按它们在树中的层次进行的。首先生成第一层结点，同时检查目标结点是否在所生成的结点中，如果不在，则将所有的第一层结点逐一扩展，得到第二层结点，并检查第二层结点是否包含目标结点，……，对层次为n+1的任一结点进行扩展之前，必须先考虑层次完层次为n的结点的每种可能的状态。因此，对于同一层结点来说，求解问题的价值是相同的，可以按任意顺序来扩展它们。通常采用的原则是先生成的结点先扩展。
为了便于进行搜索，要设置一个表存储所有的结点。由于在广度优先搜索算法中，要满足先生成的结点先扩展的原则，所以存储结点的表一般采用队列这种数据结构。

1.1 广搜之【SPFA】

算法优点：
1.时间复杂度比普通的Dijkstra和Ford低。
2.能够计算负权图问题。
3.能够判断是否有负环 (即：每跑一圈，路径会减小，所以会一直循环跑下去)。
算法思想：
我们采取的方法是动态逼近法：
1.设立一个先进先出的队列用来保存待优化的结点。
2.优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。
3.这样不断从队列中取出结点来进行松弛操作，直至队列空为止 期望的时间复杂度O(ke)， 其中k为所有顶点进队的平均次数，可以证明k一般小于等于2。

例题：洛谷 P1144 最短路计数

【题解】
这道题可以用spfa模板，只需要记录有多少个相同的到该点的最短路就OK啦

void SPFA(int x) {
	q.push(x);
	memset(vis, 0, sizeof(vis));
	memset(dis, 0x7f7f7f, sizeof(dis));
	dis[x] = 0;
	ans[x] = 1;//注意这里是1，自己到自己的路线有1条
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		vis[u] = 0;
		for (int icnt = frist[u]; icnt; icnt = road[icnt].nextt) {
			int v = road[icnt].to;
			if (dis[v] > dis[u] + 1) {
				dis[v] = dis[u] + 1, ans[v] = ans[u];
				if (!vis[v])
					q.push(v),vis[v]=1;
			}
			else if (dis[v] == dis[u] + 1)//即之前已经更新过，且与现在的线路步数一致
				ans[v] = (ans[v] + ans[u]) % mod;
		}
	}
}

优化：其实完全可以用BFS做。
大佬说：我们可以利用bfs来求每个点的深度。因为在所有边边权为1的时候，点的深度就是点的最短距离；这样在写法上便少了队列优化SPFA中退栈时还要把标记抹除这一操作，会大大提高算法速度；
在bfs的时候，我们不仅仅要从一个点的父亲继承最短路，还要继承方案数；大佬题解链接
所以可以优化为：
（其实就是省去了spfa重复入队的步骤，由于每个边权为1，bfs搜的时候已经是最优步数，不存在再次更新最短路的情况）

void BFS(int x) {
	memset(vis, 0, sizeof(vis));
	memset(ans, 0, sizeof(ans));
	memset(dis,0x7f7f7f7f, sizeof(dis));
	q.push(x);
	dis[x] = 0;
	vis[x] = 1;
	ans[x] = 1;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = frist[u]; i != -1; i = road[i].nextt) {
			int v = road[i].to;
			if (dis[v] == dis[u] + 1)
				ans[v] = (ans[v] + ans[u]) %mod;
			if (vis[v])continue;
			dis[v] = dis[u] + 1;
			vis[v] = 1;
			ans[v]=ans[u]% mod;
			q.push(v);
		}
	}
}

【 Dijkstra算法】

Dijkstra算法算是贪心思想实现的，首先把起点到所有点的距离存下来找个最短的，然后松弛一次再找出最短的，所谓的松弛操作就是，遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近，如果更近了就更新距离，这样把所有的点找遍之后就存下了起点到其他所有点的最短距离（已确定是最短的点便不用当做终点站）。参考博客：点我
Dijkstra处理的是带正权值的有权图
模板：

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
using namespace std;
#define Inf 0x3f3f3f
#define N 1005
int map[N][N],vis[N],dis[N];
int n, m;
void Init() {
	memset(map, Inf, sizeof(map));
	for (int i = 1; i <= n; i++)
		map[i][i] = 0;
}
void Getmap() {//邻接表存图
	int u, v, w;
	for (int t = 1; t <= m; t++) {
		cin >> u >> v >> w;
		if (map[u][v] > w) {
			map[u][v] = w;
			map[v][u] = w;
		}
	}
}
void Dijkstra(int u) {
	memset(vis, 0, sizeof(vis));
	for (int t = 1; t <= n; t++) {
		dis[t] = map[u][t];
	}
	vis[u] = 1;
	for (int t = 1; t < n; t++) {
		int minn = Inf, temp;
		for (int i = 1; i <= n; i++) {
			if (!vis[i] && dis[i] < minn) {//求出最小路径
				minn = dis[i];
				temp = i;
			}
		}
		vis[temp] = 1;
		for (int i = 1; i <= n; i++) {
			if (vis[temp])continue;
			if (map[temp][i] + dis[temp] < dis[i])
				dis[i] = map[temp][i] + dis[temp];
		}
	}
}
int main() {
	cin >> n >> m;
	Init();
	Getmap();
	Dijkstra(1);
	cout << dis[n];
	return 0;
}

2、[DFS]深度优先搜索

深度优先搜索是暴力搜索的一种，其核心思想是递归。
注：bfs是浪费空间节省时间，dfs是浪费时间节省空间。
找最短路的时候可以用bfs,因为bfs找到的第一个解一定是最优的，这个时候可以直接return
有关例题：洛谷 P1706 全排列问题
（一直往下深搜的思想，和回溯的思想。）
AC代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
#define N 10
int n;
int visit[N] = {0};//数没用过标0，数用过标1
int path[N];
//每一次递归搜索的是第 depth 个箱子中可以放什么数字 我是这么理解的。
void dfs(int depth) {
//假设有n个字符要排列，把他们依次放到n个箱子中

//先要检查数字是否被用过，手中还有什么数字，把他们放进并标记。

//放完一次要恢复初始状态，当到n+1个箱子时，一次排列已经结束

	if (depth == n+1)//判断边界
	{
		for (int i = 0; i < n; i++)
			printf("%5d", path[i]);
		cout << endl;
		return;
	}
	for (int i = 1; i <=n; i++) {//遍历查找 第depth个箱子中 ，能放什么数字
		if (visit[i] == 0)//若数字没有被用过
		{
		    path[depth-1] = i;//则可以往箱子里放这个数
			visit[i]= 1;//放完数后数字要标记为已用过
			dfs(depth + 1);//继续搜索下一个箱子
			visit[i] = 0;//回溯 数字用过后要回到没用过状态
		}
	}
}
int main() {

	cin >> n;
	dfs(1);//从第一个箱子开始
	return 0;
}

2、题目：洛谷 P1219 [USACO1.5]八皇后
题解：只是判断困难了一点。以后要记住：主对角线上各数组下标之差相等；斜对角线上各数组下标之和相等。
AC代码：

#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;
#define N 17
bool col[N], tx[N], ty[N];
int path[N] = { 0 };
int n,ans=0;
void dfs(int depth) {
	if (depth >n) {
		ans++;
		if (ans <= 3)
		{
			for (int i = 1; i < n ; i++)
				cout << path[i] << " ";
			cout << path[n] << endl;
		}
		return;
	}
	for (int i = 1; i <= n; i++) {//试图把数字放在（depth,i）
		if (col[i] || tx[depth - i + n] || ty[depth + i])
			continue;
		else
		{
			path[depth] = i;
			col[i] = 1, tx[depth - i + n] = 1, ty[depth + i] = 1;
			dfs(depth + 1);
			col[i] = 0, tx[depth - i + n] = 0, ty[depth + i] = 0;
		}
	}
}
int main() {
	cin >> n;
	dfs(1);
	cout << ans;
	return 0;
}

内容总结

以上是互联网集市为您收集整理的【算法笔记】有关图的搜索全部内容，希望文章能够帮你解决【算法笔记】有关图的搜索所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---