北京邮电大学计算机学院05级数据结构7图.ppt

数据结构---第7章 图 第七章 图 7.1 图的基本概念 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路径 本章学习要点 习题与上机作业 7.1 图的基本概念 非线性结构，数据元素之间呈多对多的关系。 7.1.1 图的定义 Graph=(V,VR) V：顶点(数据元素)的有穷非空集合。 VR：弧(关系)的有穷集合。 7.1.2 图的相关术语 顶点 数据元素所构成的结点。 有向图 弧的顶点偶对是有序的。对弧 vi, vj 而言， vi是弧尾/初始点； vj是弧头/终端点。 无向图 弧的顶点偶对是无序的。 (vi, vj)和(vj, vi)代表同一条边(i?j)。 (无向)完全图 每个顶点与其余顶点都有边的无向图。 顶点数为n时，边数 e=n(n-1)/2 有向完全图 每个顶点与其余顶点都有弧的有向图。 顶点数为n时，弧数 e=n(n-1) 稀疏图 有很少边或弧的图。（enlogn） 稠密图 有较多边或弧的图。 权 图中的边或弧具有一定的大小的概念。 网 边/弧带权的图。 邻接 有边/弧相连的两个顶点之间的关系。 存在(vi, vj)，则称vi和vj互为邻接点； 存在vi, vj，则称vi邻接到vj， vj邻接于vi 关联(依附) 边/弧与顶点之间的关系。 存在(vi, vj)/ vi, vj， 则称该边/弧关联于vi和vj 顶点的度 与该顶点相关联的边的数目，记为D(v)。 入度ID(v)：有向图中，以该顶点为弧头的弧数目。 出度OD(v)：有向图中，以该顶点为弧尾的弧数目。 顶点数n、边数e和度数之间的关系： 路径 接续的边构成的顶点序列。 路径长度 路径上边或弧的数目/权值之和。 回路(环) 第一个顶点和最后一个顶点相同的路径。 简单路径 序列中顶点均不相同的路径。 简单回路(简单环) 除路径起点和终点相同外，其余顶 点均不相同的路径。 连通图 无向图中，任何一对顶点间都存在路径。 连通分量 无向图中的极大连通子图。 强连通图 有向图中，任何一对顶点间都存在路径。 强连通分量 有向图中的极大连通子图。 7.1.3 图的基本操作 (1)图的生成 CreatGraph(G, V,VR) (2)销毁图 DestroyGraph(G) (3)顶点定位 LocateVex(G,value) (4)取顶点数据 Getvex(G,v) (5)对顶点赋值 Putvex(G, v, value) (6)求第一个邻接顶点 FirstAdjVex(G,v) (7)求下一个邻接顶点 NextAdjVex(G,v,w) (8)插入顶点 InsertVex(G,v) (9)删除顶点 DeleteVex(G,v) (10)插入边/弧 InsertArc(G,v,w) (11)删除边/弧 DeleteArc(G,v,w) (12)图的遍历 Traverse(G) [算法示例] 建立无向网的数组型存储结构 步骤: [存储结构定义] #define MAX_VERTEX_NUM 20 // 最大顶点个数 typedef enum{DG, DN, UDG, UDN} GraphKind; // 四种图类型 typedef struct ArcNode { int adjvex; // 该弧所指向的顶点的位置 struct ArcNode * nextarc ; //指向下一条弧的指针 int weight； InfoType