『原创』算法#4 广度优先搜索（BFS）+路径打印

/*
 * @file				BFS.cpp
 * @brief				implementing BFS
 * @author				taoxiaoxiao/XMU
 * @date				11-20-2013
 * @version				v1
*/

#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define INF 0x3f3f3f3f
#define NIL -1
#define MAXN 101

int graph[MAXN][MAXN], dist[MAXN];
int pre[MAXN], color[MAXN]; 
int n;

void BFS(int s)
{
	int i;
	for (i = 0; i < n; ++i)
	{
		color[i] = WHITE;
		dist[i]= INF;
		pre[i] = NIL;
	}
	color[s] = GRAY;
	dist[s] = 0;
	pre[s] = NIL;

	queue<int> q;
	q.push(s);
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		for (i = 0; i < n; ++i)
		{
			if (graph[u][i] != 0 && color[i] == WHITE)
			{
				color[i] = GRAY;
				dist[i] = dist[u] + 1;
				pre[i] = u;
				q.push(i);
			}
		}
		color[u] = BLACK;
	}
}

void showpath(int s, int dest)
{
	if (s == dest)
	{
		cout << s;
		return;
	}
	else if (pre[dest] == NIL)
		cout << "No Path From " << s << " to " << dest << endl;
	else
	{
		showpath(s, pre[dest]);
		cout << " " << dest;
	}

}
int main()
{	
	int i, j;
	ifstream infile("data.txt");
	if (infile.is_open())
		cout << "open file successful." << endl;
	else
	{
		cout << "open file error"<< endl;
		return 0;
	}
	cout << "*************************************\n";
	while (!infile.eof())
	{
		infile >> n;
		for (i = 0; i < n; ++i)
			for (j = 0; j < n; ++j)
				infile >> graph[i][j];
		BFS(2);
		for (i = 0; i < n; ++i)
		{
		cout << "从s点（顶点2）到" << i << " 路径为:";
		showpath(2, i);
		cout << endl;
		cout << "经历的边数为:" << dist[i] << endl;
		cout << "*************************************\n";
		}
	}
	infile.close();

	return 0;
}