第15讲 图及定义及存储结构.ppt

第15讲 图的定义与存储结构 主讲人：陈红丽 基本概念 G = (V, E) V是顶点集，E是顶点间二元关系的集合。 与树的区别： ①树有特殊的根结点； ②树的结点和关系能分成互不相交的若干子集 不予讨论的图: (总能转换为简单图) 常见应用 ①信息的组织：家庭照片管理…… ②运输问题：最短路径问题、最优乘车路线问题…… ③网络规划：小区设店问题、区域连通的规划问题…… ④进度组织：工程进度管理…… 图的分类 存储结构的选择 图的分解 顶点的参数 有关路径 着眼点：顶点间的联系 有关连通 着眼点：将不连通图简化为连通图 生成树 着眼点：将图简化为树 图的存储结构 图的数组表示法 图的数组表示法 数组表示法的特点 网的数组表示法 图的邻接表存储结构 网的邻接表表示 图的邻接表表示 有向图的十字链表表示 有向图的十字链表表示 有向图的十字链表表示 无向图的邻接多重表表示 无向图的邻接多重表表示 根据邻接表绘制逆邻接表 已知某图的出边表如下所示，请写出该图的入边表。 * 第七章 图 * 数据结构 无向图 有向图 边：二元关系是无序的。 弧：二元关系是有序的。 (vi,vj)：vi,vj互为邻接点 vi,vj：弧头vj、弧尾vi G1=(V1,E1) V1={v1,v2,v3,v4} E1={(v1,v2),(v1,v3), (v1,v4),(v2,v3), (v2,v4),(v3,v4)} G2=(V2,E2) V2={v1,v2,v3,v4} E2={v1,v2, v2,v1, v2,v3, v4,v3} 基本操作 InsertArc、DeleteArc、GetArc、SetArc 对弧/边的操作 InsertVex、DeleteVex、GetVex、SetVex 对顶点的操作 深度遍历DFSTraverse、 广度遍历BFSTraverse 对整体的操作 (遍历) 边或顶点带权值 带权图 边数≈顶点数2 稠密图 边数≈顶点数 稀疏图 弧数：n*(n-1) 有向完全图 边数：n*(n-1)/2 无向完全图 V(B)∈V(A)，E(B)∈E(A)，称图B是图A的子图 子图 5 4 6 1 3 2 4 15 10 2 15 20 30 4 10 10 有向图中，以某顶点为弧头的弧数 入度 有向图中，以某顶点为弧尾的弧数 出度 无向图中，依附于某顶点的边数 度 度的应用：以下哪个图能够一笔画完成？为什么？ 一笔画问题的本质：图结构中的边遍历问题。 应用领域：车间/厂房布置、行走路线的安排、交通设计… 除起点和终点外，其余顶点各不相同 简单回路 路径中，起点和终点是同一顶点。 回路 路径中所有顶点各不相同。 简单路径 路径上边/弧的数目。 路径长度 若从Vi到Vj有路径，称Vi到Vj是连通的 顶点间连通 Vi,……,Vj 顶点间路径 有向图的极大强连通子图。 有向图的 强连通分量 有向图中,任意二个顶点之间存在来往路径。 强连通图 无向图的极大连通子图。 无向图的 连通分量 无向图中,任意二个顶点之间是连通的 连通图 V0 V1 V2 V3 非强连通图 V0 V1 V2 V3 有两个强连通分量 非强连通的有向图中，各强连通分量的生成树的集合。 生成森林 强连通有向图中，n个顶点和n-1条弧，构成的单向连通子图(vi、vj间存在一条路径) 一个顶点入度为０，其余顶点入度为１。 生成树 有向图 不连通的无向图中，各连通分量的生成树的集合。 生成森林 连通无向图中，n个顶点和n-1条边，构成的连通子图。（原连通图的极小连通子图） 生成树 无向图 图的存储结构至少要保存两类信息： 1)顶点的数据 2)顶点间的关系（边或弧） 3)权的信息（可以没有） 如何表示顶点间的关系？ V0 V4 V3 V1 V2 V0 V1 V2 V3 图的抽象数据类型的定义（自学） 在数组表示法中，顶点存储在连续的存储空间（数组）中，用邻接矩阵表示顶点间的关系。 #define MaxVnum 50 typedef VertexType Vexs[MaxVnum]; typedef double AdjMatrix[MaxVnum][MaxVnum]; typedef struct { int vexnum,arcnum; //图的当前顶点数和边数 Vexs vexs; //顶点数组 AdjMatrix arcs; //邻接矩阵 }Graph; arcs[i][j]= 1 顶点vi与vj间有边(弧) 0 顶点vi与vj间无边(弧) 0