数据结构 第七章-图2

2020/5/22，1，第7章图，这是一个多对多的结构关系，每个元素可以有零个或更多的直接前因；零个或多个直接继任者。图的两种遍历方法：定义遍历、深度优先搜索遍历和广度优先搜索遍历算法。利用图的遍历算法判断图的连通性，找到图的生成树；Prim和Kruskal算法用于寻找图的最小生成树。Dijkstra算法用于求解单源最短路径问题。Floyd算法用于寻找所有顶点之间的最短路径。AOV网络拓扑排序；利用AOE网络寻找关键路径问题；掌握:掌握图纸的定义和术语；图的各种存储结构、构造算法及其在实际问题中的求解效率。图的遍历，7.3，3和7.3:从图的一个顶点开始，图中的所有顶点都被访问，每个顶点只被访问一次。(1)在图结构中，没有“自然”的头节点，并且图中的任何顶点都可以是被访问的第一个节点。(2)在非连通图中，从一个顶点开始，只有它所在的连通分量上的所有顶点可以被访问。因此，还需要考虑如何选择下一个起始点来访问图中剩余的连接组件。(3)在一个图结构中，如果有一个循环，那么在访问一个顶点之后，有可能沿着循环返回到该顶点，并考虑如何避免重复访问。(4)在图结构中，一个顶点可以与其他顶点相邻。当这些顶点被访问时，考虑如何选择下一个要访问的顶点，4.图的遍历方法包括深度优先遍历和广度优先遍历。7.3.1深度优先搜索，方法：(1)从图的顶点V0开始，访问该顶点；(2)从V0的未访问的相邻点开始，深度优先遍历图形，直到图形中与V0通信的所有顶点都被访问。如果此时图中仍有未被访问的顶点，请在图中选择另一个未被访问的顶点作为起点，并重复上述过程，直到图中的所有顶点都已被访问。如果图的存储结构是邻接表，则访问邻接点的顺序不是唯一的，并且深度优先序列不是唯一的，v0，v1，v3，v4，v7，v2，V5，V6，从V0开始查找图g的深度优先序列(将存储结构设置为邻接矩阵)，6，空隙图(GraphG，intv)/*从第五个顶点开始，递归深度优先遍历图g */* v是顶点在一维数组中的位置，假设g不是空图Visit(v)；/*访问第五个顶点*/为(w=FirstAdjVex(G，v)；w；w=NextAdjVex(G，v，w)如果(！访问了西部)；/*递归调用DFS*/，辅助数组：在V的未访问相邻顶点W上插入最大顶点数；访问标志数组，全局变量，所有组件开头都是0，访问过的v=1表示顶点v已经被访问过。已访问，深度优先遍历算法：7.3图的遍历。7，7.3图的遍历，深度优先搜索：图G*/inti存储在邻接表存储结构上的邻接表中的voidfstraversal(algrapg)/*深度优先遍历；对于(I=0；iadjvex/*w是序列号*/if(！访问了西部；/*如果没有访问W，递归调用DFS */* DFSAL */，遍历7.3图，9。在遍历过程中，对图中的每个顶点最多调用一次DFS函数，因为一旦一个顶点被标记为被访问，就不会从它开始搜索。因此，遍历一个图的过程本质上是一个为每个顶点寻找其相邻点的过程。所需时间取决于所使用的存储结构。当使用邻接矩阵作为图的存储结构时，找到每个顶点的邻接点所需的时间是O(n2)，其中N是图中的顶点数。当邻接矩阵用作存储结构时，深度优先搜索遍历图的时间复杂度为0(N2 n)。当图的存储结构由邻接表组成时，找到邻接点所需的时间是O(e)，其中E是无向图的边数或有向图的弧数。因此，当邻接表用作存储结构时，深度优先搜索遍历图的时间复杂度为0(n e)。，7.3图的遍历，10，从图中的顶点V开始：1)访问顶点V；2)所有未接入的相邻点w1、w2，通路v的wk；3)依次从这些相邻点开始，访问其所有未接入的相邻点；依此类推，直到图中所有被访问顶点的相邻点被访问；7.3.2广度优