文章目录1、定义2、方法1、深度优先排线2、广度优先排线3、实现1、有向图或强连通有向排线2、非连通排线结语附录
另一方面，定义为从某个图中任意指定的顶点(称为初始点)出发，根据一些搜索方法沿图的边缘访问图中的所有顶点，每个顶点仅访问一次。 这个过程称为图的扫描。 如果给定的图是连通的有向图，或强连通的有向图，遍历过程一次就完成了，按照访问的优先级得到一个由该图的所有顶点组成的序列。
二、方法遍历过程中，从图的初始点到达图中各顶点可能存在多条路径。 可以沿图中的一个路径访问顶点，然后沿另一个路径返回顶点。 也就是说，存在循环。 必须设置访问标记数组visited，以避免重复访问同一顶点。 当访问顶点I时，数组中的元素visited[i]设置为1，否则设置为0。
图的扫描过程实际上是搜索过程，根据搜索方法的不同，图的扫描方法有深度优先扫描和宽度优先扫描两种。
1、深度优先遍历深度优先遍历的过程是：从图中的某个初始点v出发，首先访问初始点v，然后选择与顶点v相邻且未访问的顶点w，以w为初始顶点，再从该处出发，图中与顶点v相邻的所有顶点都被访问很明显，这是一个递归的过程。
以下为示例。
该图以a为初始点，从左向右通过深度优先遍历得到序列： ABDHECFG，当然从右向左通过深度优先遍历得到序列：如果取ACGFBEHD，则可知通过深度优先遍历得到的序列不唯一当用头插入法插入各顶点的邻接顶点时，之后，用深度优先横移进行横移得到序列ACGFBEHD，当各顶点的邻接顶点通过末尾插值法插入时，之后用深度优先横移进行横移得到序列ABDHECFG
看看深度优先遍历的代码
//深度优先访问： g:图v:初始点visited:标记数组voidDFS(graphlnk*g，int v，bool visited[] )//顶点，获取值，然后单击printf (% ) //在访问的顶点上标记intw=getfirstneighbor(g，GetVertexValue(g ) g，v ) )； //获取第一个相邻顶点while(w！=-1 () /相邻顶点未访问时if (！ 已查看[ w ] (DFS (g，w，已查看)； //以该顶点为开始顶点进行深度优先遍历}/*完成第一个相邻顶点的深度优先遍历，获取下一个相邻顶点的位置(如果该顶点未被访问，则在下一个倒圆角中将该顶点作为开始顶点进行深度优先遍历) ()/w=) 2、宽度优先扫描宽度优先扫描过程，首先访问初始点v，然后访问顶点v所有未访问的相邻点v1、v2、v3、…、vt，然后依次访问各顶点的未访问的相邻点v1、v2、v3、…、vt，以此类推，图中
以下为示例。
该图以a为初始点，从左向右通过宽度优先遍历得到序列： ABCDEFGH，当然从右向左通过宽度优先遍历得到序列：如果取ACBGFEDH，则可知通过宽度优先遍历得到的序列也不唯一
看看广度优先的导线
//广度优先遍历： g:图v:初始点visited:标记数组voidBFS(graphlnk*g，int v，bool visited[] () ) printf(%c-- '，getveveted 链路队列q； //创建链接团队initqueue(q )//初始化//enqueue(q，v )//将开始顶点入队int w； while (！ Empty(q ) )//如果团队中存在顶点(Gethead ) q，v )； //取得队伍最前面存在的顶点vdequeue(q )； //退出团队//获取第一个相邻顶点w=getfirstneighbor(g，GetVertexValue(g ) g，v )； while(w=-1(//有相邻顶点) if (！ visited[w](/如果此相邻顶点未被访问，则打印值printf('%c-- '，GetVertexValue(g ) g，w )； 可视[ w ]=true； //被访问的EnQueue(Q (标记为q (q，w )； //对该顶点进行排队，之后获取访问该顶点的邻接顶点的下一个邻接顶点}//顶点v的下一个邻接顶点(其邻接顶点的顺序为上一个访问邻接顶点w之后) w=getnextneighbor(g，GetVertexValue(g
ertexValue(g,w));}}} 三、实现有了上面的理论基础，下面将基于图的邻接表存储来实现图的遍历，如果大家对图的邻接表存储方式还不太理解，那么可以先阅读图之邻接表详解（C语言版）此篇文章之后，再接着往下阅读。
1、无向图或强连通有向图遍历如果给定图是连通的无向图或者是强连通的有向图，则遍历过程一次就能完成，并可按访问的先后顺序得到由该图的所有顶点组成的一个序列。
深度优先遍历实现
//深度优先遍历：给出遍历的图g和起始顶点vertexvoid DFS(GraphLnk *g, T vertex){int n = g->NumVertices;//获取顶点个数//根据顶点数建立辅助数组空间：用来标记哪些顶点已经访问过，哪些顶点没有访问bool *visited = (bool*)malloc(sizeof(bool) * n);assert(visited != NULL);for(int i=0; i<n; ++i)//初始化标记数组{visited[i] = false;}//获取起始节点在邻接表中的位置int v = GetVertexPos(g,vertex);DFS(g,v,visited);//遍历free(visited);//释放辅助空间}广度优先遍历实现
//广度优先遍历：给出遍历的图g和起始顶点vertexvoid BFS(GraphLnk *g, T vertex){int n = g->NumVertices;//获取顶点个数//根据顶点数建立辅助数组空间：用来标记哪些顶点已经访问过，哪些顶点没有访问bool *visited = (bool*)malloc(sizeof(bool) * n);assert(visited != NULL);for(int i=0; i<n; ++i)//初始化标记数组{visited[i] = false;}//获取起始顶点在邻接表中的位置int v = GetVertexPos(g,vertex);BFS(g,v,visited);//遍历free(visited);} 2、非连通图遍历如果给定图是非连通图，则只能访问到初始点所在分量中的所有顶点，其他连通分量中的顶点是不可能访问到的，为此需要从其他每个连通分量中选择初始点，分别进行遍历，这样才能够访问到图中的所有顶点。
深度优先遍历实现
//非连通图的深度优先遍历方式void NonUnicomDFS(GraphLnk *g){int n = g->NumVertices;//获取顶点个数//根据顶点数建立辅助数组空间：用来标记哪些顶点已经访问过，哪些顶点没有访问bool *visited = (bool*)malloc(sizeof(bool) * n);assert(visited != NULL);for(int i=0; i<n; ++i)//初始化标记数组{visited[i] = false;}for(i=0; i<n; ++i) //遍历非连通图的顶点{if(!visited[i])//以没有访问的顶点为起始顶点进行深度优先遍历DFS(g,i,visited);}free(visited);}广度优先遍历实现
//非连通图的广度优先遍历方式void NonUnicomBFS(GraphLnk *g){int n = g->NumVertices;//获取顶点个数//根据顶点数建立辅助数组空间：用来标记哪些顶点已经访问过，哪些顶点没有访问bool *visited = (bool*)malloc(sizeof(bool) * n);assert(visited != NULL);for(int i=0; i<n; ++i)//初始化标记数组{visited[i] = false;}for(i=0; i<n; ++i) //遍历非连通图的顶点{if(!visited[i])//以没有访问的顶点为起始顶点进行广度优先遍历BFS(g,i,visited);}free(visited);} 结语对图遍历的介绍就到这里啦，希望这篇文章能给予你一些帮助，感谢各位人才的：点赞、收藏和评论，我们下次见。
附录测试代码：图遍历详解（C语言版）