第7章数据结构 图

1、第1，7章图，本章的主要内容7.1基本概念和术语7.2图的存储结构7.3图的横向图应用7.4最小成本生成树7.5拓扑排序，关键路径7.6最短路径，2，7.1基本术语，图由顶点集和边集组成的二进制组G=，E的每条边在v到一对顶点(u，v)之间的连接完全图形、密集和稀疏图形、子图形相邻点和关联边相邻点：边上的两个顶点与相邻点相关联。如果边e=(v，u)，则顶点v，u关联边e网络：图形中每个边或圆弧具有特定权重，具有这些权重的图形称为网。3，7.1基本术语(续)，与顶点度、粒度和出图顶点V的度=V相关联的边数位于转向图中。顶点v的打印=从v开始的起始边数顶点v的输入=从v结束的边数顶点v的角度=v的

2、打印v的输入角度G的顶点数n，E地物中所有顶点的角度数=2*e(每个边对地物的所有顶点的角度和“贡献”2度)，4，7.1基本术语(续如果V=u，则序列称为循环。简单路径，简单循环如果除了一条路径上的起点和终点外，其他顶点不同，则该路径称为简单路径。由简单路径组成的回路称为简单回路。例如，在上面的无向图中，V0、V1、V2和V3不是简单路径V0、V1、V2、V4和V1不是简单路径。在上图中，V0、V2、V3、V0是简单回路。5，7.1基本术语(续)，连接图，无(存在)方向图G=中的两个顶点u，v均具有从u到v的路径，则G为连接图(强连接图)。(b)非连接图形，(c)强连接图形，(a)连接图形，V

3、0，V3，V2，V1，V4，V5，(无(有)图形的最大连接子图形包含图形的连接分量(强连接分量)、非连接图形、两个连接分量、非强连接图形、两个强连接分量、7，7.1基本术语(续)、生成树一个连接图形的生成树包含图形的所有顶点，但n-1足以构成一棵树，(a)连接图G1、(b)连接图G1的生成树，8，7.1基本术语(续):无向图及其生成树，无向图G、9，7.1基本术语(续) 实例4各种流程图(例如，产品的生产流程图顶点：工序边缘：每个工序之间的顺序关系，12，7.2图表的存储结构，图表的存储结构必须至少有两种类型的信息：1)顶点的数据2)顶点之间的关系，G=是，V=v0，V1 ，typedefst

4、ructvertexteypevexsmaxvnum；/顶点向量AdjMatrixarcs/相邻矩阵intvexnum，arcnum/图形的当前顶点和边数GraphGraphG，15，1)全向图的邻接矩阵是对称矩阵，相同的边显示两次。2)顶点v的度：等于二维阵列中相应行(或列)中值为1的元素数。3)确定两个顶点v、u是否为相邻点。也就是说，您只需要确定二维阵列的相应组件是否为14。顶点保持不变，在图中添加和删除边。您只需将1或0分配给二维阵列中的相应组件。5)图形的顶点数为n，用具有n个元素的一维数组存储图形的顶点，用相邻矩阵表示边，则g为n n2占用的存储空间。图中存储空间的占用与顶点数相关

5、，与边数无关。适合密集边图；7.2.1(续)阵列表示的性质，16，0)具有方向图的相邻矩阵不一定是对称的；1)顶点v的输出：等于二维数组对应行中值为1的元素数。2)输入顶点v:等于二维阵列的相应列中值1的元素数。7.2.1(续)阵列表示的特征，17，7.2.1(续)网络的阵列表示，18，7.2.2图表的相邻表存储结构，相邻表表示的顶点：通常与一维阵列相关联的同一顶点的边上按编号顺序存储顶点数据：表示边(V0，V1)的线性，19，7.2.2(续)网络的相邻列表为20，7.2.2(续)相邻列表的类型定义，typedefstructVertexTypedataArcNode * firstarcAd

6、jListMaxVnum，typedefstructArcNodeintadjvexDoubleweightStructArcNode * nextarcArcNode，21，7.2.2(续)图的相邻表为typedefstructVertexTypedataArcNode * firstarcAdjListMaxVnum，typedefstructArcNodeintadjvexDoubleweightStructArcNode * nextarcArcNode，typedefstructintvexnum，arcnumAdjListverticesAGraph，AGraphG，22，7.2.

7、2(续)直接图形的相邻表表示顶点，例如相邻表表示中的顶点。通常，在一维阵列中以相同顶点开始的圆弧上按编号顺序存储顶点数据。另存为线性链接表，显示为具有23，7.2.2(续)直接图形的反向相邻表，示例，在反向相邻表显示中的顶点：在圆弧(通常在一维阵列中以相同顶点结束)中按编号顺序保存顶点数据：另存为线性链接表，在具有24，7.2.3方向图的交叉链接十字光标列表中，弧节点，具有25，7.2.3(续)方向图的交叉连结表格表现法，v 0，v1，v3，0，0，1，2，3，1，0，2，2，0，3，0，0，在十字光标列表中，顶点节点存储数据元素，圆弧节点存储圆弧及其信息。具有26，7.2.3(续)方向图的交

8、叉链接表表示法，v 0，v1，v3，0，0，0，1，2，3，1，1，0，2，0，3，1，3，2，在十字光标列表中，顶点节点存储数据元素，圆弧节点存储圆弧及其信息。，27，7.2.4全向图的相邻多表表示在全向图的相邻多表表示中，每个边只显示一次。v0、v1、v2、v3、0、1、2、3、0、1、0、3、(v0、v1)。图的遍历操作是解决图的连接问题、拓扑排序等问题的基础。遍历方法：深度优先遍历和宽度优先遍历，30，7.3.1深度优先搜索(DFS)，DFS遍历顶点v1，v1，v2，v4，V5，V8，v3，V6，直到连接到图形和v的路径的顶点被访问；(3)此时，如果尚未访问地物上的顶点，则从未访问的顶点开始，再次执行深度优先遍历，直到地物上的所有顶点都被访问为止。32，7.3.1(续)深度优