清华大学朱明方数据结构5.ppt

1、第5章图，5.1图的基本概念1。地物的定义2。顶点的程度3。连接路径和5.2图的存储结构1。相邻矩阵2。相邻表3。边集阵列4。相邻多表5.3插图中的遍历1。深度优先巡回2。宽度优先遍历5.4最短距离问题，允许5.1图基本集集合中元素之间的任意前后关系。也就是说，数据元素之间存在多对多连接。每个元素形成一个顶点。图的二进制组定义为G=(V，E) V顶点集，EV的二进制关系。例如，插图：G1=(v (G1)，e (G1) v (G1)=a，b，c e (G1)=a，b，a，c，b(vs插图的定义E(G1)，E(G2)为边(根据具有方向的边或图形的二进位群组定义，G=(V，E)为：图形由顶点集V和边

2、集E组成。图G1中的边是直接边方向图。图G2的边缘是无香边无香图。满足图G=(V，E)和图G=(V，E):V(G)V(G)，E(G) E(G)称为G的子图形。例如，图G:图G: G是G的子图，5.1图的基本概念，2 .顶点的角度无方向图：边(Vi，Vj)、结束Vi、Vj徐璐相邻。顶点的角度顶点连接的边数D(Vi)在图中两个顶点之间的边总数为最大n(n-1)/2的情况下直接图：边Vi，VjVi的出口，Vj的入口边；起点ViVj的传入边相邻点；结束VjVi的离开边相邻点。顶点入口顶点连接的入口边数；D-(Vi)顶点径流顶点连接的径流数；D (Vi)顶点的度=顶点粒度顶点出度。将顶点I的度设定为D(

3、Vi)，图形中有N个顶点，其边数M为m=交握清理。推论：图中奇数的顶点是偶数。A B D E F，例如，A B C D，无路径和连接方向vin-1、vin、Vin、vq、顶点序列(vp、vi1、Vin、vq)是从VP到VQ的路径。路径长度路径中所有面的数目。顶点VI-VJ具有路径VI-VJ连接。在无方向图中，两个顶点都与连接图相关联。非常大的连接子图形连接组件。在直接图形中，两个顶点都连接强大的连接图。非常大的强连接子图强连接组件。(c)强连接图(d)强连接组件，(a)连接图(b)连接组件，a b c，d e，a b d c，a b c d边缘具有权利例如，(a)权限无向度(b)权限有向度、a

4、 b e d、5 10 3，2 15、c、5.2图形的存储结构，使用相邻矩阵(二维阵列)表示顶点的相邻性。图G中有N个顶点，序列号分别为1，2，N，阵列D(13360N)存储顶点信息。二维阵列A(1:n，1:n)存储n个顶点的相邻关系相邻矩阵(例如图：相邻矩阵：1 2 3、b、A、c、)例如，图：相邻矩阵：20，1 2 3，b，a，c，1 2 3，1 2 3，1 2 3，1 2 3，5.2图的存储结构，1。相邻矩阵表示相邻矩阵，以查找与任意顶点相邻的点。确定任意顶点的角度。例如：查找的时间复杂性O(n)，N顶点数N2的存储空间利用率低。5.2图片的存储结构，2 .相邻表格显示方式：(1)将每个

5、相邻标头指标储存为单一连结表格顶点相邻表格(2)一个向量，该向量为图形中每个顶点建立相邻关系。相邻表节点(边节点):表头节点：如果没有地物，则表节点没有值。范例：插图：相邻表格：边相邻关系、反转相邻表格：为每个顶点建立连接相邻点的单一连结表格。例如，您可以很容易地找到图：反折表：反折表：任何顶点的口才或口才的权利。寻找任何顶点的进入边相邻点、进入度。，边集阵列表示：将顶点信息保存为一维阵列使用一个阵列存储图形中所有边、阵列元素数图形中的边数。阵列中的每个元素按任意顺序存储边的开始、结束和权重。无方向图，可以任意选择边缘起点。未授权的图片，跳过保存权重。例如，图：排列边集：拟合：按顺序处理边的操

6、作。5.2图片的存储结构，4 .相邻多表表达(无方向)方法：地物中的每条边显示为一个存储节点，其中一个端点连接在一起的边。边(I，j)节点：顶点节点：例如，图：相邻多表：拟合：对指定边起作用。、5.3度遍历、遍历问题：可以有多个路径到达同一顶点。解决方法：在访问的顶点上标记(显示为辅助数组)。遍历方法：深度优先搜索遍历，宽度优先搜索遍历。1.深度优先搜索遍历(纵向优先搜索遍历)思考：类似于树的第一个根遍历。方法：访问顶点VI，然后将其标记为已访问。从Vi未访问的相邻点执行深度优先扫描遍历当Vi的所有相邻点都被访问时，返回到前一个顶点vk，从vk的另一个未访问的相邻点开始深度优先遍历。显然：这是

7、递归过程。5.3图遍历、深度优先搜索遍历(例如，图：从顶点1开始(初始顶点)、深度优先遍历的过程是为v1(节点值A)、标记v1、深度优先遍历而取v2的过程)。访问V2(B)，显示V2，使用V5作为深度优先遍历。访问V5(E)，标记V5，并采取V6进行深度优先遍历。V6(F)访问，V6标记，V5 v2回滚，5.3图遍历，深度优先搜索遍历(如图：访问v7(G)，标记v7，深度优先遍历的v3)。访问V3(C)，显示V3，回滚V7，使用v4作为深度优先遍历。V4(D)访问、V4标记、V7 v2 v1回滚过程结束。巡回结果：A、B、E、F、G、C、D 1。深度优先遍历的迭代算法说明，5.3度的遍历，深度

8、优先搜索遍历1。深度优先遍历的迭代算法说明遍历算法说明与存储方法有关。例如，图：相邻矩阵定义阵列段宜恩(1:n)以记录N个顶点的访问标志时：定义阵列MARK(13360N，1:N)以表示图形的相邻矩阵。，5.3图遍历，深度优先搜索遍历1。深度优先遍历的迭代算法VI(顶点I)为初始顶点时，深度优先搜索遍历算法：输入：顶点阵列V(1:n)，相邻矩阵A(13360n，13360n初始顶点编号I输出：深度优先遍历序列PROCEDURE DFS1(A)深度优先遍历迭代算法相邻表表示图形时，相邻表：例如，图：V LINK顶点存储节点空间定义为V(1:n)和链接(1:n)，角节点存储空间定义为NUM(1:2

9、m)和NEXT(1:2m)，()、I)process(v)mark(I)1p link(I)在深度优先遍历迭代算法权重的情况下，在算法DFS1中，对于未连接的图，对于图中未访问的每个顶点，只需对初始顶点调用DFS1或DFS2。例如，for I=1 to n do if mark(I)=0 then call DFS 1(a，v，mark，n，I)可以对相邻矩阵表示中的未连接图形进行深度优先搜索跟踪。剩下的类比。事故：算法DFS1，DFS2的c语言说明？5.3图遍历，1，深度优先搜索遍历2。深度优先遍历的非迭代算法基本思想：设置记录刚访问的顶点I的边节点(相邻点)的堆栈。从访问的相邻点返回到顶点

10、I时，堆栈顶部会弹出角点锁定(相邻点)。然后，从堆栈的边节点(相邻点)开始，沿单个链表(矩阵I行)查找并处理下一个相邻点。具体的算法说明可能因存储方式而异。以下是基于邻接矩阵和相邻表存储方法的算法的基本思想。5.3图遍历，1，深度优先搜索遍历2。深度优先遍历的非迭代算法相邻表存储方法，算法的基本思路：将顶点表存储空间设置为V(1:n)和链接(13360N)，将角节点存储空间设置为NUM(133602m)堆栈S，堆栈顶部指针顶部，初始堆栈为空(1)访问和显示初始顶点I，获取边节点的节点号p=link (I)。(2) P0: j=NUM(p)(如果未访问)，则访问顶点j并显示：PUSH(S，p，t

11、op)，p=LINK(j)，rotation(如果访问了两个顶点j，则p=NUM)(3)如果p=0，则：如果为top0，则为POP(S，p，top)；p=下一个(p)，旋转(2)；如果Top=0，遍历过程将终止。5.3图遍历，1，深度优先搜索遍历2。深度优先遍历的非迭代算法相邻矩阵存储方法，算法的基本思路：将相邻矩阵设置为A (1:N，1:N)堆栈S(13360n，1:2)，堆栈顶部指针top，初始堆栈null (top=0)存取和显示初始顶点I，J1。(1) j n: A(i，j)=1，如果未访问顶点j，则为j，PUSH(S，I，j，top)，ij，J1，旋转(1)；否则，j j j j 1，旋转(1)；如果是Jn，则旋转(2)；(2) top0，pop (s，I，j，top)，jjj1，旋转(1)；如果Top=0，遍