《数据结构、算法与应用 —— C++语言描述》学习笔记 — 图 — 遍历

• 一、广度优先搜索
• 二、深度优先搜索
• 三、路径查找

广度优先搜索是：将顶点分为待搜索顶点集合和已搜索顶点集合。对于每个已搜索顶点集合中的顶点，遍历与之邻接的顶点，将所有属于待搜索顶点集合的顶点加入已搜索顶点集合中，直到所有的顶点都被加入有已搜索顶点集合中。这种搜索方法可以用队列实现。同时，我们注意到，这种遍历方式所需要的所有接口都在抽象类 Graph 中提供。因此我们可以直接在 Graph 中实现此方法，而不必在各子类中实现：

template
inline void Graph::bfs(int startVertex)
{
	using namespace std;

	vector vecLabels(numberOfVertices());
	queue queueVertices;
	queueVertices.push(startVertex);
	while (!queueVertices.empty())
	{
		int currentVertex = queueVertices.front();
		queueVertices.pop();

		auto iter = iterator(currentVertex);
		while ((currentVertex = iter->next()) != -1)
		{
			if (vecLabels[currentVertex] == false)
			{
				queueVertices.push(currentVertex);
				vecLabels[currentVertex] = true;
			}
		}
	}
}

深度优先搜索是：从一个顶点 v 出发，首先将 v 标记为已到达的顶点，然后选额一个邻接于 v 的尚未到达的顶点 u。如果这样的 u 不存在，则搜索停止；否则，从 u 开始新的DFS。当这种搜索结束时，在选择另一个邻接于 v 的尚未到达的顶点。如此循环往复：

template
inline void Graph::dfs(int startVertex)
{
	std::vector labels(numberOfVertices());
	doDfs(startVertex, labels);
}

template
inline void Graph::doDfs(int startVertex, std::vector& labels)
{
	int currentVertex = 0;
	auto iter = iterator(startVertex);
	labels[startVertex] = true;
	while ((currentVertex = iter->next()) != -1)
	{
		if (labels[currentVertex] == false)
		{
			doDfs(currentVertex, labels);
		}
	}
}

用广度优先搜索或深度优先搜索，寻找一条从源点 theSource 到终点 theDestination 的路径，搜索从 theSource 开始，到达顶点 theDestination 结束。要实际地得到这条路径，需要记住从一个顶点到下一个顶点的边。在深度优先搜索中，路径的边集已隐含在递归过程中，因此利用深度优先策略设计一个寻找路径的程序是比较容易的。在完成顶点 theDestination 的标记之后，把递归过程扩展，可以反向建立起从 theDestination 到 theSource 路径。

在深度优先搜索过程中，我们可以使用栈来保存路径的结果。因为只有查找路径结果为真时，我们才能把当前节点放到容器中。即后找到的节点一定是先被放到容器中的：

template
inline std::vector Graph::findPath(int srcVertex, int dstVertex)
{
	using namespace std;
	vector labels(numberOfVertices());
	stack path;

	auto find = doFindPath(srcVertex, dstVertex, labels, path);
	if (find)
	{
		vector ret;
		while (!path.empty())
		{
			ret.push_back(path.top());
			path.pop();
		}

		return ret;
	}
	
	return vector();
}

template
inline bool Graph::doFindPath(int srcVertex, int dstVertex, std::vector& labels, std::stack& path)
{
	if (srcVertex == dstVertex)
	{
		path.push(srcVertex);
		return true;
	}

	int currentVertex = 0;
	auto iter = iterator(srcVertex);
	labels[srcVertex] = true;
	while ((currentVertex = iter->next()) != -1)
	{
		if (labels[currentVertex] == false)
		{
			if (doFindPath(currentVertex, dstVertex, labels, path))
			{
				path.push(srcVertex);
				return true;
			}
		}
	}

	return false;
}