DS09_图1.ppt

图的存储结构 四、无向图的邻接多重表表示法 例 a e c b d 1 2 3 4 a c d b 5 e 1 2 1 4 3 4 3 2 3 5 5 2 ^ ^ ^ ^ ^ 与邻接表区别：后者同一条边，只需一个链结点表示 data firstedge mark ivex ilink jvex jlink 小结 图的基本概念 图、顶点、边（弧） 有关术语： 度、子图、路径、连通图、生成树 图的基本操作与储存表示 访问、修改 4种表示法 邻接矩阵 邻接表 十字链表 邻接多重表 作业：网络教室 下次课程预告 图2 图的遍历 最小生成树 * * 北京理工大学 / 1 内容提要 图的基本概念 定义、术语 常见操作 图的储存结构 图的遍历 图的最小生成树 线性表中结点之间的关系是一对一的，除头结点和尾结点外，每个结点仅有一个前驱和一个后继； 树是按分层关系组织的结构，树结构中结点之间关系是一对多，一个双亲可以有多个孩子，每个孩子结点仅有一个双亲； 图结构中，顶点之间的关联是任意的，图中每个顶点都可以和其它顶点相关联，即数据元素之间存在多对多的关系。 图的引入 图的应用举例 例1、交通图（公路、铁路） 顶点：地点 边：连接地点的路 例2、电路图 顶点：元件 边：连接元件之间的线路 例3、通讯线路图（互联网） 顶点：地点 边：地点间的连线 例4、各种流程图 如产品的生产流程图。 顶点：工序 边：各道工序之间的顺序关系 研究热点：复杂网络研究 图的基本概念 图(Graph)——图G是由两个集合V(G)和E(G)组成的，记为G=(V，E) 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或有序对。 图的分类 有向图 无向图 图的基本概念 有向图——有向图G是由两个集合V(G)和E(G)组成的。 其中：V(G)是顶点的非空有限集。 E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为v,w，v,w是顶点，v为弧尾，w为弧头。 图的基本概念 例如： G1 = V1,E1 V1 = { A, B, C, D, E } E1 = {A,B, A,E, B,C, C,D, D,B, D,A, E,C } E A C B D 图的基本概念 无向图——无向图G是由两个集合V(G)和E(G)组成的。 其中：V(G)是顶点的非空有限集。 E(G)是边的有限集合，边是顶点的无序对，记为 (v,w) 或 (w,v)，并且(v,w)=(w,v)。 图的基本概念 例如： G2 = (V2,E2) V2 = { v0 ,v1,v2,v3,v4 } E2 = { (v0,v1), (v0,v3), (v1,v2), (v1,v4),  (v2,v3), (v2,v4) } V0 V4 V3 V1 V2 图的基本概念 例如： G2 = V2,E2 V2 = { v0，v1，v2，v3 } E2 = { v0,v1 , v0,v2 , v2,v3 , v3,v0 } 例 2 4 5 1 3 6 G1 图G1中：V(G1) = { 1 , 2 , 3 , 4 , 5, 6 } E(G1) = { 1,2 , 2,1 , 2,3 , 2,4 , 3,5 , 5,6 , 6,3 } V0 V1 V2 V3 图的基本概念 1 完全图、稀疏图、稠密图 e=边数，n=顶点数 完全图：e=n(n-1)/2(无向) ； e=n(n-1) (有向) 稀疏图：e较少；稠密图： e较多 2 顶点的度、入度、出度 顶点V的度 = 与V相关联的边的数目 在有向图中： 顶点V的出度 = 以V为起点有向边数 顶点V的入度 = 以V为终点有向边数 顶点V的度 = V的出度+V的入度 设图G 的顶点数为 n，边数为 e 图的所有顶点的度数和 = 2*e （每条边对图的所有顶点的度数和“贡献”2度） V0 V4 V3 V1 V2 e V0 V1 V2 V3 图的基本概念 路径、回路 无向图 G =（V，E）中的顶点序列v1, v2, …