算法研究：图的深度优先遍历

图的遍历和树的遍历类似，我们希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程 就叫做图的遍历（Traverse Graph)。

图的遍历方法一般有两种，第一种是深度优先遍历（Depth First Search),也 有称为深度优先搜索，简称为DFS。第二种是《广度优先遍历（Breadth  First Search)》，也有称为广度优先搜索， 简称为BFS。我们在《堆栈与深度优先搜索》中已经较为详细地讲述了深度优先搜索的策略，这里不再赘述。我们也可以把 图当作一个迷宫，设定一个起始点，走遍所有图的顶点并打上标记，直到访问遍所有的顶点为止。如图7-5-2所示，需要注 意的是结点I 是在从A->H，H->回溯->D，D->I 的时候被访问到的，而且我们是从A开始递归进入下面的路径， 所以会一直回溯到原点A为止表示遍历结束。

下面只给出邻接矩阵和邻接表存储方式时的图的深度优先遍历的算法代码，没有给出整体可供测试运行的代码，其 实只需要再写一个创建图的函数就可以进行整体测试了，可以参考《邻接矩阵创建图》和《邻接表创建图》

一、如 果我们使用的是邻接矩阵的方式，则代码如下：

typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */

#define MAXSIZE 9 /* 存储空间初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9

typedef struct
{
    VertexType vexs[MAXVEX]; /* 顶点表 */
    EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵，可看作边表 */
    int numVertexes, numEdges; /* 图中当前的顶点数和边数 */
} MGraph;

bool visited[MAXVEX];/* 访问标志的数组 */
/* 邻接矩阵的深度优先递归算法 */
void DFS(MGraph MG, int i)
{
    int j;
    visited[i] = true;
    cout << MG.vexs[i] << ' '; /* 打印顶点，也可以其它操作 */
    for (j = 0; j < MG.numVertexes; j++)
        if (MG.arc[i][j] == 1 && !visited[j])
            DFS(MG, j);/* 对为访问的邻接顶点递归调用 */
}
/* 邻接矩阵的深度遍历操作 */
void DFSTraverse(MGraph MG)
{
    int i;
    for (i = 0; i < MG.numVertexes; i++)
        visited[i] = false;/* 初始所有顶点状态都是未访问过状态 */
    for (i = 0; i < MG.numVertexes; i++)
        if (!visited[i])
            DFS(MG, i);/* 对未访问过的顶点调用DFS，若是连通图,只会执行一次*/
}

遍历结果为： A B C D E F G H I (上图所示的图结构）

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索算法
， 遍历
， 递归
， 广度优先搜索
， 矩阵
， 图的遍历
， 深度
， 顶点
， 无向图的深度遍历
， 深度图
， 图的深度遍历
， 算法 八数码 优先搜索
， 矩阵dfs算法
优先
，以便于您获取更多的相关知识。