/*
深度优先搜索
从vertex开始遍历，visit是遍历顶点的函数指针
*/
void Graph::dfs(int vertex, void (*visit)(int))
{
	stack<int> s;
	//visited[i]用于标记顶点i是否被访问过
	bool *visited = new bool[numV];
	//count用于统计已遍历过的顶点数
	int i, count;
	for (i = 0; i < numV; i++)
		visited[i] = false;
	count = 0;
	while (count < numV)
	{
		visit(vertex);
		visited[vertex] = true;
		s.push(vertex);
		count++;
		if (count == numV)
			break;
		while (visited[vertex])
		{
			for (i = 0; i < numV
				&& (visited[i] 
				|| matrix[vertex][i] == 0 || matrix[vertex][i] == MAXWEIGHT); i++);
			if (i == numV)  //当前顶点vertex的所有邻接点都已访问完了
			{
				if (!s.empty())
				{
					s.pop();   //此时vertex正是栈顶，应先出栈
					if (!s.empty())
					{
						vertex = s.top();
						s.pop();
					}
					else  //若栈已空，则需从头开始寻找新的、未访问过的顶点
					{
						for (vertex = 0; vertex < numV && visited[vertex]; vertex++);
					}
				}
				else  //若栈已空，则需从头开始寻找新的、未访问过的顶点
				{
					for (vertex = 0; vertex < numV && visited[vertex]; vertex++);
				}
			}
			else  //找到新的顶点应更新当前访问的顶点vertex
				vertex = i;
		}
	}
	delete[]visited;
}

1. 先访问完当前顶点的所有邻接点。(应该看得出广度的意思)
2. 先访问顶点的邻接点先于后访问顶点的邻接点被访问。

/*
广度优先搜索
从vertex开始遍历，visit是遍历顶点的函数指针
*/
void Graph::bfs(int vertex, void(*visit)(int))
{
	//使用队列
	queue<int> q;
	//visited[i]用于标记顶点i是否被访问过
	bool *visited = new bool[numV];
	//count用于统计已遍历过的顶点数
	int i, count;
	for (i = 0; i < numV; i++)
		visited[i] = false;
	q.push(vertex);
	visit(vertex);
	visited[vertex] = true;
	count = 1;
	while (count < numV)
	{
		if (!q.empty())
		{
			vertex = q.front();
			q.pop();
		}
		else
		{
			for (vertex = 0; vertex < numV && visited[vertex]; vertex++);
			visit(vertex);
			visited[vertex] = true;
			count++;
			if (count == numV)
				return;
			q.push(vertex);
		}
		//代码走到这里，vertex是已经访问过的顶点
		for (int i = 0; i < numV; i++)
		{
			if (!visited[i] && matrix[vertex][i] > 0 && matrix[vertex][i] < MAXWEIGHT)
			{
				visit(i);
				visited[i] = true;
				count ++;
				if (count == numV)
					return;
				q.push(i);
			}
		}
	}
	delete[]visited;
}

void visit(int vertex)
{
	cout << setw(4) << vertex;
}
int main()
{
	cout << "******图的遍历：深度优先、广度优先***by David***" << endl;
	bool isDirected, isWeighted;
	int numV;
	cout << "建图" << endl;
	cout << "输入顶点数 ";
	cin >> numV;
	cout << "边是否带权值，0(不带) or 1(带) ";
	cin >> isWeighted;
	cout << "是否是有向图，0(无向) or 1(有向) ";
	cin >> isDirected;
	Graph graph(numV, isWeighted, isDirected);
	cout << "这是一个";
	isDirected ? cout << "有向、" : cout << "无向、";
	isWeighted ? cout << "有权图" << endl : cout << "无权图" << endl;
	graph.createGraph();
	cout << "打印邻接矩阵" << endl;
	graph.printAdjacentMatrix();
	cout << endl;
	cout << "深度遍历" << endl;
	for (int i = 0; i < numV; i++)
	{
		graph.dfs(i, visit);
		cout << endl;
	}
	cout << endl;
	cout << "广度遍历" << endl;
	for (int i = 0; i < numV; i++)
	{
		graph.bfs(i, visit);
		cout << endl;
	}
	system("pause");
	return 0;
}