图的遍历：宽度优先遍历

/*
	图的遍历：宽度优先遍历
	队列
	2014-4-3 09:14:41
*/

/*
	测试数据
9 12
5 8 29
6 1 12
8 3 11
1 2 4
3 1 22
4 3 17
7 4 25
6 5 9
8 7 7
1 6 9
3 2 19
6 7 4

*/

#include <iostream>
#include <cstdlib>
#define MAX 10000
using namespace std;

int head[MAX]; //存储节点数组中起点为i的位置,0为结束标记
struct Node{
	int to, w, next; //起点，权值，下一点
};
Node Edges[MAX];

bool s[MAX];
int queue[MAX];

/*void DFS(int x){
	s[x] = true; //标记当前点已被访问
	printf("%d\n", x);
	int i;
	//对于每个未被访问的相邻节点，使用DFS。遍历返回后尝试其他支路
	for(i = head[x]; i != 0; i = Edges[i].next){
		if(s[Edges[i].to] == false) DFS(Edges[i].to);
	}
}*/

void BFS(int x){
	int iq = 0;
	queue[iq++] = x;	
	int i, k;
	for(i = 0; i < iq; ++i){
		//每次从队头取节点，一定是下一个待扩展节点
		printf("%d\n", queue[i]);
		s[queue[i]] = 1;
		//遍历与当前节点相连的节点，如果没有被访问，入队
		for(k = head[queue[i]]; k; k = Edges[k].next){
			if(!s[Edges[k].to]){
				queue[iq++] = Edges[k].to;
			}
		}
	}
}


int main(){
	int n, m; //n个点，m条边
	int to, from, w;
	
	//存储
	cin >> n >> m;
	for(int i = 0; i < m; ++i){
		cin >> from >> to >> w;
		Edges[i].to = to;
		Edges[i].w = w;
		Edges[i].next = head[from];
		head[from] = i; //更新
	}
	
	/*//遍历
	for(int i = 1; i <= n; ++i){
		for(int j = head[i]; j != 0; j = Edges[j].next)
			cout << i << ‘ ‘ << Edges[j].to << ‘ ‘ << Edges[j].w << endl;
	}*/
	
	/*//DFS
	DFS(1);*/
	BFS(1);
	system("pause");
	return 0;
}

图的遍历：宽度优先遍历,布布扣,bubuko.com

图的遍历：宽度优先遍历

原文：http://blog.csdn.net/chang_mu/article/details/22897791