图的遍历 BFS，广度优先遍历。(无向图)

接上面的DFS遍历，这里另一种遍历方式：

BFS:

广度优先遍历的主要思想：

1、 首先以一个未被访问过的顶点作为起始顶点，访问其所有相邻的顶点

2、然后对每一个相邻的顶点，再访问他们相邻的未被访问的顶点，直到所有的顶点都被访问过，遍历结束

// bfs_graph.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>
#include<queue>

using namespace std;

#define MAX 101

queue<int> Que;//队列

int book[MAX];//记录那些顶点已经被访问

int m;//m个边
int n;//顶点的总个数
int map[MAX][MAX];//图的边 邻接矩阵

int sum = 0;//记录已经访问的顶点数



void bfs(int point)//cur是当前所在的顶点编号
{
	Que.push(point);
	int cur;
	while (!Que.empty())
	{//while
		cur = Que.front();
		sum++;
		Que.pop();

		if (sum != m)
		{
			cout << cur << " ";
		}
		else
		{
			cout << cur << endl;
		}

		for (int i = 1; i <= n; i++)
		{//for
			//判断当前顶点cur到顶点i是否有边，并判断顶点i是否已经访问过
			if (map[cur][i] == 1 && book[i] == 0)
			{
				book[i] = 1;//标记顶点i已经访问过
				Que.push(i);
			}

		}//for
	}//while

	return ;
}



int _tmain(int argc, _TCHAR* argv[])
{
	
	//请输入边数，和顶点数
	cout << "请输入顶点数和边数" << endl;
	cin >> n >> m;

	//初始化二维矩阵 n个顶点
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			map[i][j] = 0;
		}
	}

	//读入顶点之间的边
	int x, y;//x行，y列   x,y点
	cout << "请输入有边的相邻顶点" << endl;
	for (int i = 1; i <= m; i++)
	{
		cin >> x >> y;
		map[x][y] = 1;
		map[y][x] = 1;
	}

	//从1号城市出发
	book[1] = 1;//标记1号顶点已经访问
	cout << "bfs搜索" << endl;
	bfs(1);//从1号顶点开始遍历

	system("pause");

	return 0;
}