图的遍历和树的遍历类似，从图中某一顶点出发访问遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程叫做图的遍历。

由于图中的任何顶点都可能和其余所有的顶点相邻接，极有可能沿着某条路径搜索后，又回到原顶点，而有些顶点可能还没有遍历到。因此，我们需要在遍历图的过程中把访问过的顶点打上标记，以免多次访问同一个顶点。具体办法是设置一个访问数组 visited[n]，n 是图中顶点的个数。

对于图的遍历，如何避免因回路陷入死循环，就需要科学地设计遍历方案，通常有两种遍历次序方案：

1. 深度优先遍历
2. 广度优先遍历

#define M 65535


// 定义顶点
int vertext_size = 6;
int vertex[] = { 1, 2, 3, 4, 5, 6 };

// 定义边
int edges[][6] = {
	{ 0,  7,  9,  M,  M, 14},
	{ 7,  0,  10, 15, M, M},
	{ 9,  10, 0,  11, M, 2},
	{ M,  15, 11, 0,  6, M},
	{ M,  M,  M,  6,  0, 9},
	{14,  M,  2,  M,  9, 0}
};

1. 深度优先遍历 {#title-0} ====================

深度优先遍历（Depth First Search）,也可以称为深度优先搜索，简称DFS. 算法思路：

1. 首先选择任意顶点作为起始顶点；
2. 访问该顶点，并将该顶点 visited 设置为 true；
3. 查找当前顶点是否有邻接顶点，如果有的话，递归访问；
4. 这一条访问路径上的顶点访问完毕，则选择下一个未访问过的顶点继续深度优先访问。

示例代码：

#include <iostream>
using namespace std;

#define M 65535


// 定义顶点
int vertext_size = 6;
int vertex[] = { 1, 2, 3, 4, 5, 6 };

// 定义边
int edges[][6] = {
	{ 0,  7,  9,  M,  M, 14},
	{ 7,  0,  10, 15, M, M},
	{ 9,  10, 0,  11, M, 2},
	{ M,  15, 11, 0,  6, M},
	{ M,  M,  M,  6,  0, 9},
	{14,  M,  2,  M,  9, 0}
};

// 访问顶点
void visit_vertex(int i, bool *visited)
{
	visited[i] = true;
	cout << vertex[i] << " ";

	for (int j = 0; j < vertext_size; ++j)
	{
		// 访问与 i 邻接的顶点
		if (visited[j] == false && (edges[i][j] > 0 && edges[i][j] < M))
		{
			visit_vertex(j, visited);
		}
	}
}


void depth_first_search()
{
	// 初始化辅助 visited 数组
	bool* visited = new bool[vertext_size];
	for (int i = 0; i < vertext_size; ++i)
	{
		visited[i] = false;
	}

	// 从任意顶点开始深度优先访问
	for (int i = 0; i < vertext_size; ++i)
	{
		if (visited[i] == false)
		{
			visit_vertex(i, visited);
		}
	}

	// 销毁 visited 辅助数组
	if (visited != nullptr)
	{
		delete[] visited;
		visited = nullptr;
	}
}


int main()
{
	depth_first_search();
	return 0;
}

程序执行结果：

1 2 3 4 5 6

2. 广度优先遍历 {#title-1} ====================

广度优先遍历类似于二叉树的层序遍历，其实现需要借助队列容器的辅助。算法思路：

1. 先选择任意顶点作为开始顶点，并访问该结点，将其标记为已访问，并将其加入到队列中；
2. 从队列中取出已访问的结点，并搜索与其关联的顶点，打印输出，同理，将访问过的顶点存储到队列中；
3. 循环该过程，直到所有的顶点都遍历一遍。

示例代码：

#include <iostream>
#include <queue>
using namespace std;

#define M 65535


// 定义顶点
int vertext_size = 6;
int vertex[] = { 1, 2, 3, 4, 5, 6 };

// 定义边
int edges[][6] = {
	{ 0,  7,  9,  M,  M, 14},
	{ 7,  0,  10, 15, M, M},
	{ 9,  10, 0,  11, M, 2},
	{ M,  15, 11, 0,  6, M},
	{ M,  M,  M,  6,  0, 9},
	{14,  M,  2,  M,  9, 0}
};


void breadth_first_search()
{
	// 初始化辅助 visited 数组
	bool* visited = new bool[vertext_size];
	for (int i = 0; i < vertext_size; ++i)
	{
		visited[i] = false;
	}

	queue<size_t> help_queue;

	// 广度优先遍历开始
	for (int i = 0; i < vertext_size; ++i)
	{
		if (visited[i])
		{
			continue;
		}

		// 标记顶点已访问
		visited[i] = true;
		cout << vertex[i] << " ";

		// 将 i 顶点加入队列
		help_queue.push(i);

		// 搜索与已访问顶点有边的顶点
		while (!help_queue.empty())
		{	
			// 获得队头顶点
			size_t vid = help_queue.front();
			help_queue.pop();

			// 访问与该顶点有边的所有顶点
			for (int j = 0; j < vertext_size; ++j)
			{
				if (visited[j] == false && (edges[vid][j] > 0 && edges[vid][j] < M))
				{
					visited[j] = true;
					cout << vertex[j] << " ";
					help_queue.push(j);
				}
			}
		}

	}

	// 销毁 visited 辅助数组
	if (visited != nullptr)
	{
		delete[] visited;
		visited = nullptr;
	}
}


int main()
{
	breadth_first_search();
	return 0;
}

程序执行结果：

1 2 3 6 4 5