数据结构第7章 图3

第7章，7.1度类型定义，7.2度存储结构，7.3度导航，7.4最小生成树，7.5非循环图及其应用，7.6最短路径，通过7.3图，遍历地物：在地物的一个顶点处导航地物，访问地物的其他顶点，然后仅访问地物的每个顶点一次的过程。通过访问图中的部分顶点，可以返回到已沿其他边访问的顶点。要确保每个顶点只访问一次，必须标记这些顶点。通常，当顶点VI未访问时辅助阵列visit0.使用n-1作为顶点标记。visiti的值为0。访问Vi时，visiti的值为1。通常有两种导航图路径：深度优先搜索和宽度优先搜索，适用于全向图和有向图。地物的两种横向方法：1。深度优先搜索图的深度优先导航类似于树的第一根遍历。使用的搜索方法的特点是尽可能先纵向搜索。这种搜索方法称为深度优先搜索(Depth-FirstSearch)。因此，使用此方法遍历图表称为图的深度优先遍历。2.广度优先搜索宽度类似于树的分层遍历。使用的搜索方法称为Breadth-FirstSearch，因为它尽可能先执行水平搜索。相应的巡回称为宽度优先巡回。1 .深度优先搜索DFS，基本思路：从图的(强)连接组件之一的顶点选择v出发：访问顶点v并将访问标记设置为访问，即visitedv=1；(2)从v未访问的相邻点开始，直到连接的(强)组件和路径连接的v顶点都被访问，然后继续图形的深度优先遍历。如果图形中有尚未访问的顶点，请选择其馀(强)连接组件中未访问的顶点作为起点，然后重复此过程，直到图形中的所有顶点都已访问为止。(强)连接元件的横向：W1、W2和W3均为v的相邻点。SG1是W1可以访问的一组顶点。SG2是W2可以访问的一组顶点。SG3是W3可以访问的一组顶点。访问顺序：SG1到SG2到SG3。交集部分只能访问一次。t、t、t、t、t、t、t、t、a、c、h、d、k、f、e、b、g、a、c、h、voiddfstraverse (graphg) /深度优先遍历for(v=1；V=G.vexnumv)visitedv=FALSE；/初始化访问标志数组for(v=1；v=0；W=NextAdjVex(G，v，w)if(！Visitedw)DFS(G，w，Visit)；/DFS，深度优先导航的递归算法，示例1:深度优先遍历图g和深度优先遍历序列的创建。序列1: v1、v2、v4、V8、V5、v3、V6、V7序列2: v1、v2、V5、V8、v4、v3、V7、V6，注意，示例2:深度首先遍历图形g，深度优先创建遍历序列。深度优先遍历序列：v1，v2，v4，V8，V5，V6，v3，V7，v1，v2，V5，V8，v4，V6，v3，V7，深度优先级遍历序列对图进行深度优先级划分时，按访问顶点的顺序获得的顶点序列称为该图的深度优先级遍历序列或DFS序列。图形的DFS序列可能不是唯一的。 n源和存储结构的内容都已确定的图的DFS序列是唯一的。930；如果相邻矩阵表示的图形确定源点，则DFS序列是唯一的。只有给出邻居表的内容和初始起点，DFS序列才能得到唯一确认。示例3:已知图形的相邻表查找从顶点0开始的深度的优先遍历序列。深度优先遍历序列：0，1，2，3，4，深度优先遍历序列：0，1，2，3，40，1，2，4，30，2，3，2，1，40，示例4:查找已知图的相邻矩阵，从顶点0开始的深度优先遍历序列。深度优先遍历序列：0，1，3，4，2，5，6。示例5:已知图形的相邻表查找从顶点0开始的深度优先遍历序列。，深度优先遍历序列：0，1，2，3，2 .宽度首先搜索BFS，选择其中一个连接的组件(强)。VI出发： 33访问顶点VI，访问访问标记(visitedVI=1；访问VI的所有未访问的邻近点w1、w2、wk；(3)从相邻点开始访问所有未访问的相邻点，直到连接组件中的所有顶点都被访问(强)。重复以上步骤，直到访问了图中的所有顶点。对于连接的图形，从开始v到其馀顶点之间必须存在路径。其中vw1、vw2和vw5的路径长度为1。vw3、vw6和vw8的路径长度为2；V到w4、V到w7的路径长度为3，每个顶点和起点之间存在“近”关系。以“从近处到远处”的顺序巡回。v