数据结构-图的遍历

1、遍历图形，深度优先搜索，宽度优先搜索，遍历图形，摘要和任务，回顾，课堂练习，审查-图形的存储结构，审查-图形的存储结构，审查-图形的存储结构，审查-图形的存储结构，审查-图形的存储结构，审查-图形的存储结构，审查-图形的存储结构可以使用UDN交叉表的相邻矩阵dg和DN相邻多连接表可以用于udg和UDN的范围、复盖范围、存储结构比较、相邻矩阵3360 n N2相邻表可以用于DG和dn: n e或n 2e。 UDG和udn: n 2e交叉链路表： n e相邻多链路表： n e，第二，存储空间，存储结构比较，第三，作业支持，1，顶点访问，LocateVex(G，u)；/u的位置，返回GetVex(G

2、，v)。/v的值。将值指定给PutVex(/u)。比较存储结构，2，插入和删除存储顶点阵列元素，修改相邻矩阵和相邻矩阵，将新顶点v添加到InsertVex(/地物g)。DeleteVex(/g)删除顶点v和相关圆弧。比较存储结构，3，插入和删除圆弧，InsertArc(，DeleteArc(，存储结构比较，相邻矩阵：修改边(和)相邻表：无图，修改两个顶点的连接表；修改具有一个或两个顶点的连接列表交叉列表：包含两个连接列表多个相邻列表：包含两个连接列表，比较存储结构，4，相邻点，第一个adjvex (g，v)；/返回v的“第一个相邻点”。如果相应的顶点/g没有相邻点，则返回“空”。NextAdj

3、Vex(G，v，w)；/v的(相对于w)返回“下一个相邻/点”。如果w是v的最后一个相邻点，则返回/null。存储结构比较，相邻矩阵：v行相邻列表：v行相交列表：v行相交列表：v行相邻列表：v行相邻列表：v行相邻列表，存储结构比较，相邻矩阵：v行相邻列表：v行相邻列表：v行相邻列表：v行相邻列表：v行相邻列表，4，相邻角，v行相邻列表/将第一个相邻点的位置返回为-1，没有相邻点。NextAdjVex(G，v，w)；/w返回相邻点的位置。实现相邻点函数，int first adjvex (algragh g，int v)p=g . vertices v . firstarc；/v的第一个相邻点i

4、f(！p)return-1；/无相邻点return p-adj vex；实现相邻点函数，int next adjvex (algragh g，int v，int w)p=g . vertices v . firstarc；/v的第一个相邻点while(p，c语言中存储结构说明，1，插图中的两个参数：顶点数、边数(圆弧数)、vertices、vexnum、Edge(arc)、arc，用途：解决方案的连接性、拓扑排序和关键路径查找等算法的基础。深度优先搜索，宽度优先搜索，分类：深度优先搜索，W1、W2和W3都是v的相邻点，SG1、SG2和SG3分别是包含顶点W1、W2和W3的子图形。深度优先搜索，

5、访问顶点v；如果未访问For (W1、W2、W3)相邻点Wi，则将从该点开始深入搜索日历。深度优先搜索-连接图形，深度遍历序列：v1 v2 V8 V5，V6 v3 V7，v1，v2，v4，V5，v3，V7，V6，3、搜索过程中通过的边和所有顶点构成地物的一个延伸树。如何知道4，v的相邻点是否被访问？为每个顶点设置访问符号visitedw。深度优先搜索-连接图形，void DFS(Graph G，int v) /顶点v开始，深度优先搜索通过连接图形G visitedv=TRUEFor(w=FirstAdjVex(G，v)；w=0；W=NextAdjVex(G，v，w)if(！Visitedw)

6、DFS(G，w)；/v未访问的相邻顶点w DFS /DFS递归调用，深度优先搜索-连接图，void从DFS(Graph G，int v) /顶点v开始，深度优先搜索遍历连接图G visitedv=TRUEFor(w=FirstAdjVex(G，v)；w=0；W=NextAdjVex(G，v，w)if(！Visitedw) DFS(G，w)；/v尚未访问的相邻顶点w包括DFS /DFS、深度优先搜索-连接图、v1、v2、v3、v4、V5、v1、v2、V8、V5、V5Visited=FALSE/所有顶点尚未访问Push(S，v)。While(！empty(S)Pop(S，u)；If(！Visitedu) visit (u)，visitedu=trueFor(w=FirstAdjVex(G，u)；w=0；W=NextAdjVex(G，u，w)if(！Visiitedw) push (g，w)/将未访问的相邻点堆叠DestroyS