C/C++无向图的遍历(bfs和dfs)

描述

简单介绍一下图，图就是由一些小圆点（称为顶点）和连接这些小圆点的直线（称为边）组成的。例如下图的由五个顶点（编号1、2、3、4、5）和五条边（1-2、1-3、1-5、2-4、3-5）组成。

要求：

第一行输入节点数n和边的条数m
第一行以后的m行输入节点之间的边，i和j
输出遍历路径进过的节点

示例输入

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

bfs理论结果为

1 2 3 5 4

dfs理论结果为

1 2 4 3 5

思路

现在咱们从1号节点开始遍历这个图，如果是广度优先bfs算法，1遍历到2了以后，继续找1相连的边（即3和5），于是开始找节点2的边，最后找到4。
如果是深度优先dfs算法,1遍历到2了以后，得继续找到2的所有边，不撞南墙不死心嘛！（即4），2撞了南墙，回头继续把3的所有边撞到南墙，最后找到5

bfs代码如下：

#include<iostream>
using namespace std;

int main(){    //  数组队列实现  bfs遍历无向图 
    int i,j,a,b,n,m,cur,book[101]={0},e[101][101];
    int que[10001],head,tail;
    cin>>n>>m;
    for(i=1;i<=n;i++)
    	for(j=1;j<=n;j++)
    		if(i==j) e[i][j]=0;
    		else e[i][j]=99999999;
    for(i=1;i<=m;i++){
    	cin>>a>>b;
    	e[a][b]=1;
    	e[b][a]=1;
	}
	head=1;tail=1; 
	que[tail++]=1;
	book[1]=1;
	while(head<tail && tail<=n){
		cur=que[head];
		for(i=1;i<=n;i++){
			if(book[i]==0 && e[cur][i]==1){
				que[tail++]=i;
				book[i]=1;
			}
			if(tail>n) break;
		}
		head++;
	}
	for(i=1;i<tail;i++) cout<<que[i]<<" ";
	return 0;
}

dfs代码如下：

#include<iostream>
using namespace std;

int sum=0,n,m,book[101]={0},e[101][101];
void dfs(int cur){
	if(sum==n) return;
	cout<<cur<<" ";
	sum++;
	for(int i=1;i<=n;i++){
		if(book[i]==0 && e[cur][i]==1){
			book[i]=1;
			dfs(i);
			//这里是无向图，不需要回溯 
		}
	}
	return;
}
int main(){    //  递归实现  dfs遍历无向图 
    int i,j,a,b;
    cin>>n>>m;
    for(i=1;i<=n;i++)
    	for(j=1;j<=n;j++)
    		if(i==j) e[i][j]=0;
    		else e[i][j]=99999999;
    for(i=1;i<=m;i++){
    	cin>>a>>b;
    	e[a][b]=1;
    	e[b][a]=1;
	}
	book[1]=1;
	dfs(1);
	return 0;
}