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

由于图中的任何顶点都可能和其余所有的顶点相邻接，极有可能沿着某条路径搜索后，又回到原顶点，而有些顶点可能还没有遍历到。因此，我们需要在遍历图的过程中把访问过的顶点打上标记，以免多次访问同一个顶点。具体办法是设置一个访问数组 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 &lt; vertext_size; ++j)
{
	// 访问与 i 邻接的顶点
	if (visited[j] == false &amp;&amp; (edges[i][j] &gt; 0 &amp;&amp; edges[i][j] &lt; 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 &lt; 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&lt;size_t&gt; help_queue;
// 广度优先遍历开始
for (int i = 0; i &lt; vertext_size; ++i)
{
if (visited[i])
{
continue;
}
// 标记顶点已访问
visited[i] = true;
cout &amp;lt;&amp;lt; vertex[i] &amp;lt;&amp;lt; &amp;quot; &amp;quot;;

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

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

	// 访问与该顶点有边的所有顶点
	for (int j = 0; j &amp;lt; vertext_size; ++j)
	{
		if (visited[j] == false &amp;amp;&amp;amp; (edges[vid][j] &amp;gt; 0 &amp;amp;&amp;amp; edges[vid][j] &amp;lt; M))
		{
			visited[j] = true;
			cout &amp;lt;&amp;lt; vertex[j] &amp;lt;&amp;lt; &amp;quot; &amp;quot;;
			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