图论的基础（水题）

目录

注意：

A. 图的dfs遍历

B. 图的bfs遍历

C. 欧拉路

温馨提示：

注意：

这一篇的题在上一篇——图论的基础，也是有的。但是，这个有题目，可以加深理解！

A. 图的dfs遍历

题目描述：

一个有 n 个结点的无向连通图，这些结点以编号：1，2…n 进行编号，现给出结点间的连接关系。

请以结点 1 为起点，按dfs（深度优先搜索）、优先访问小编号结点的顺序遍历并输出该图。

输入：

第一行为两整数，n 和 e ，表示 n 个顶点，e 条边。（ 2≤n,e≤10 ）

以下 e 行每行两个数，表示两个结点是连通的。

输出：

只有一行，为按照优先访问小编号结点的dfs的结果。

样例：

输入：

5 7
1 2
1 3
1 4
2 4
2 5
3 5
4 5

输出：

1 2 4 5 3

 基本思想：——仿树的先序遍历过程。

步骤：

（1）访问起始点 v ；

（2）若 v 的第 1 个邻接点没访问过，深度遍历此邻接点；

（3）若当前邻接点已访问，再找 v 的第 2 个邻接点重新遍历；

代码如下：

#include<bits/stdc++.h>
using namespace std;
int a[20][20];
int n,e;
bool f[20];
void dfs(int x){
	f[x]=1;
	cout<<x<<' ';
	for(int i=1;i<=n;i++){
		if(a[x][i]==1&&!f[i]) dfs(i);
	}
}
int main(){
	cin>>n>>e;
	int x,y;
	for(int i=1;i<=e;i++){
		cin>>x>>y;
		a[x][y]=1;
		a[y][x]=1;
	}
	dfs(1);
	return 0;
}

B. 图的bfs遍历

题目描述：

一个有 n 个结点的无向连通图，这些结点以编号：1,2…n 进行编号，现给出结点间的连接关系。

请以结点 1 为起点，按广度优先搜索（bfs）、优先访问小编号结点的顺序遍历并输出该图。

输入：

第一行为两整数，n 和 e ，表示 n 个顶点，e 条边。（ 2≤n,e≤10 ）

以下 e 行每行两个数，表示两个结点是连通的。

输出：

只有一行，为节点按照广度优先、小编号结点优先访问的结果。

样例：

输入：

5 7
1 2
1 3
1 4
2 4
2 5
3 5
4 5

输出：

1 2 3 4 5

基本思想：——仿树的层次遍历过程。

步骤：

（1）在访问了起始点 v 之后，依次访问 v 的邻接点；

（2）然后再依次访问这些顶点中未被访问过的邻接点；

（3）直到所有顶点都被访问过为止；

注意：广度优先搜索是一种分层的搜索过程，每向前走一步都可能访问一批顶点，不想深度优先搜索那样有回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归算法。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int a[20][20];
int q[20];
int h,t;
int n,e;
bool f[20];
int main(){
	cin>>n>>e;
	int x,y;
	for(int i=1;i<=e;i++){
		cin>>x>>y;
		a[x][y]=1;
		a[y][x]=1;
	}
	h=1;
	t=1;
	q[1]=1;
	f[1]=1;
	cout<<1<<' ';
	while(h<=t){
		for(int i=1;i<=n;i++){
			if(a[q[h]][i]==1&&!f[i]){
				cout<<i<<' ';
				t++;
				q[t]=i;
				f[i]=1;
			}
		}
		h++;
	}
	return 0;
}

C. 欧拉路

题目描述：

有一个无向图，图中要么有两个奇点要么0奇点，如果是欧拉回路请从第一个点（1号点）为起点开始遍历，如果有两个奇点，则以字典序大的为起点开始遍历，在遍历的过程中，字典序小结点的先遍历。

请输出满足条件的欧拉路或者欧拉回路。

输入：

第一行两个整数，n和e，表示有n个结点（结点编号为1~n），e条边。（5<=n<=20,5<=e<=15）

接下来e行，每行有2个数，代表这两个结点之间有一条边。（本题数据保证两个结点之间最多只有1条边，确保本题存在欧拉路或者欧拉回路）

输出：

只有一行，为满足条件的欧拉路或欧拉回路。

样例：

输入：

5 5
1 2
2 3
3 4
4 5
5 1

输出：

1 2 3 4 5 1

思路：

使用 DFS 寻找欧拉路的基本思想如下：

1 . DFS 寻找到第一个无边可走的结点，则这个结点必定为终点。

由于是 DFS 递归结束的时候记录的，那么该边是走完欧拉道路的最后的那条边，层层返回后最开始的也是最开始的出发地。

2 . 接下来由于 DFS 的递归回溯，会退回终点的上一个结点，继续往下搜索，直到寻找到第二个无边可走的结点，则这个接点必定是欧拉路中终点前最后访问的结点。

3 . 当通过 DFS 遍历完整张图之后，就可以倒序储存下整个欧拉路（因为是递归）。

如图：

注意：防止是循环的方法是将走过的边都拆掉！

代码如下：

#include<bits/stdc++.h>
using namespace std;
int a[30][30];
int n,e;
int d[30];
int r[50];
int k;
void dfs(int x){
	for(int i=1;i<=n;i++){
		if(a[x][i]==1){
			a[x][i]=0;
			a[i][x]=0;
			dfs(i);
		}
	}
	k++;
	r[k]=x;
}
int main(){
	cin>>n>>e;
	int x,y;
	for(int i=1;i<=e;i++){
		cin>>x>>y;
		a[x][y]=1;
		a[y][x]=1;
		d[x]++;
		d[y]++;
	}
	int s=1;
	for(int i=n;i>=1;i--){
		if(d[i]%2==1){
			s=i;
			break;
		}
	}
	dfs(s);
	for(int i=k;i>=1;i--){
		cout<<r[i]<<' ';
	}
	return 0;
}

温馨提示：

这些"水题"的题目是作者复制的，代码是作者自己做的，看官们请自己做一遍，锻炼锻炼自己的写代码能力，还有！不了解并查集的请看——并查集概述呦！！！

还有，

本作者希望看官们能多多评论，谢谢啦！！！

最后的最后：

制作不易，点个赞吧！！！

制作不易，点个赞吧！！！

制作不易，点个赞吧！！！