图论算法——图的遍历

图论算法——图的遍历图的基本应用——图的遍历,从具体的题目着手,学习图的遍历方式及代码形式。

图论算法也是非常基础且重要的算法(ps:好像没有不重要的……)

图的基本应用——图的遍历,从具体的题目着手,学习图的遍历方式及代码形式

我们先来看一下题目,然后再具体分析图的遍历方式。


 题目选自洛谷P5318

题目描述

小K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个(也有可能没有)参考文献的链接指向别的博客文章。小K 求知欲旺盛,如果他看了某篇文章,那么他一定会去看这篇文章的参考文献(如果他之前已经看过这篇参考文献的话就不用再看它了)。

假设洛谷博客里面一共有 n(n≤105) 篇文章(编号为 1 到 n)以及 m(m≤10^6) 条参考文献引用关系。目前小 K 已经打开了编号为 1 的一篇文章,请帮助小 K 设计一种方法,使小 K 可以不重复、不遗漏的看完所有他能看到的文章。

这边是已经整理好的参考文献关系图,其中,文献 X → Y 表示文章 X 有参考文献 Y。不保证编号为 1 的文章没有被其他文章引用。

图论算法——图的遍历

请对这个图分别进行 DFS 和 BFS,并输出遍历结果。如果有很多篇文章可以参阅,请先看编号较小的那篇(因此你可能需要先排序)。

输入格式

输出格式

输入输出样例

输入 1

8 9
1 2
1 3
1 4
2 5
2 6
3 7
4 7
4 8
7 8

输出 1

1 2 5 6 3 7 8 4 
1 2 3 4 5 6 7 8 

 

在之前的学习中已经接触到深度优先搜索DFS和广度优先搜索BFS。

深度优先遍历可以被看作在图中的深度优先搜索

广度优先遍历可以被看作在图中的广度优先搜索

可以比较一下,有助于更好理解和更快解题。 

相信在座的各位应该知道图是个啥玩意,应该也知道“遍历”是啥:所谓“遍历”,就是把图上的每个顶点都找一遍呗!但是要找可不能瞎找,要不会把自己找晕,咱这里就有两种“防晕”的好方法!正所谓“举例是理解的试金石”,咱就拿样例来说!

戳我看样例

 首先看方式一

深度优先遍历

咱们可以一步一步向前去走:

从1出发,先去最小的2

然后从2出发,沿路到5

再从5出发……咦?没路了?好吧那就回去到2吧

出发点又到了2,这时候5已经到过啦,那就去6

6又没路了,好办!回到2,由于2通往的5和6都来过了,所以再回去到1,这时候1的路中2已经走过了,没走过的最前一个是3,那就在走到3

……..

就这样一步一步走过去,可以得到顺序:

1 2 5 6 3 7 8 4

这种方法就是一步一步去尝试,先从一条路走到黑,走完了就回去找另一条,总结成7个字就是“不撞南墙不回头”,有没有发现跟我们的“深度优先搜索”迷之相似???所以,我们叫它“图的深度优先遍历

下面给出实例代码:(DFS版)

int n,m;
vector<int> p[100005]; //使用邻接表来存储图
bool book[100005]; //记录某个点是否被访问过
void solve(int x){
	cout<<x<<" ";
	for(int i=0,sz=p[x].size();i<sz;i++){ //邻接表的dfs方式
		if(!book[p[x][i]]){
			book[p[x][i]] = true;
			solve(p[x][i]);
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){ //邻接表的存储方式
		int x,y;
		cin>>x>>y;
		p[x].push_back(y);
	}
	book[1] = true;
	solve(1);
	return 0;
}

然后看方式二

广度优先遍历

想用这种方法,你需要掌握一项技能——分身术

还是从1出发,咱先把能走的都走一遍,依次到达2,3.4

1的走完了,咱就从下一个没往下走的地点开始,也就是从2出发,到达5,6

2的也走完了,目前最靠前的还没往下走过的点是3,好的,从3到达7,8

然后下一个没往下“扩展”的地点是4,哇,这时候7,8都已经走过了呢,那就走完啦

所以我们可以得到顺序:

1 2 3 4 5 6 7 8

总之就是把每个没有向下走过的地方都走一遍,如果你看懂了,你可以发现这个方法和“广度优先搜索”算法很像,我们就叫它“图的广度优先遍历

下面给出实例代码:(BFS版)

int n,m;
vector<int> p[100005]; //使用邻接表来存储图
queue<int> q; //使用BFS当然得要队列了
bool book[100005]; //记录某个点是否被访问过
void bfs(){ //邻接表的bfs方式
	book[1]=true;
	q.push(1);
	while(!q.empty()){
		int x = q.front();
		cout<<x<<" ";
		for(int i=0,sz=p[x].size();i<sz;i++){
			if(!book[p[x][i]]){
				book[p[x][i]] = true;
				q.push(p[x][i]);
			}
		}
		q.pop();
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		p[x].push_back(y); //将图保存到邻接表中
	}
	bfs();
	return 0;
}

两种遍历方法都讲完了,接下来咱们考虑的就只有细节问题了,首先,这个题数据范围那么大,用邻接矩阵存肯定是会爆的,那咱们就用一种新的方法。

首先,我们用一个结构体vector(为了节省空间,咱用vector来存)存储每个边的起点和终点,然后用一个二维vector(也就是一个vector数组)存储边的信息

这个存储方法可能有点难理解,不过其实也没那么难:我们用e[a][b]=c,来表示顶点a的第b条边是c号边。咱举个栗子,还是拿样例说吧:

8 9
1 2 //0号边(由于vector的下标是从0开始的,咱就“入乡随俗”,从0开始)
1 3 //1号边
1 4 //2号边
2 5 //3号边
2 6 //4号边
3 7 //5号边
4 7 //6号边
4 8 //7号边
7 8 //8号边

最后二维vector中的存储会如下所示:

0 1 2 //1号顶点连着0、1、2号边
3 4	//2号顶点连着3、4号边
5	//3号顶点连着5号边
6 7 //4号顶点连着6、7号边
	//5号顶点没有边
	//6号顶点没有边
8	//7号顶点连着8号边
	//8号顶点没有边

看是不是对上号了?这个方法比较好懂,又节省空间,是个好方法。


别着急,我们题目还没解决呢。

回归到题目

别忘了题目要求:“如果有很多篇文章可以参阅,请先看编号较小的那篇

那就排序呗!咱们按照题目要求,按照终点从小到大排列,如果终点相同按起点从小到大排列 注意我们说的第几号边是指排序后的序号

解题代码:

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int MAXN = 100010;

vector<int> G[MAXN];
int n, m;
bool visited[MAXN];
queue<int> q;

void dfs(int x, int cur) {
	visited[x] = true;
	cout << x << " ";
	if (cur == n) return ;
	for (int i=0; i<(int)G[x].size(); i++)
		if (!visited[G[x][i]]) dfs(G[x][i], cur+1);
}
void bfs(int x) {
	memset(visited, false, sizeof(visited));//记得一定要清空
	visited[x] = true;
	q.push(x);
	while (!q.empty()) {
		int v = q.front();
		cout << v << " ";//输出
		for (int i=0; i<(int)G[v].size(); i++) 
			if (!visited[G[v][i]]) {
				visited[G[v][i]] = true;
				q.push(G[v][i]);
			}
		q.pop();
	}
}

int main() {
	cin >> n >> m;
	for (int i=1; i<=m; i++) {
		int u, v;
		cin >> u >> v;
		G[u].push_back(v);//邻接表保存图
	}
	for (int i=1; i<=n; i++) sort(G[i].begin(), G[i].end());//标准vector排序
	dfs(1, 0);
	cout << endl;
	bfs(1);
	cout << endl;
	return 0;
}

今天的文章图论算法——图的遍历分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/11898.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注