它经过的边(vi, vp1)、(vp1, vp2)、.、(vpm, vj)应当是属于E的边 。
,路径长度：,非带权图的路径长度是指此路径上边的条数； 带权图的路径长度是指路径上各边的权之和 。
,图的术语（续）,图是一种数据元素间存在多对多关系的数据结构加上一组基本操作构成的抽象数据类型 。
,ADT Graph（参见教材P156-257） 数据对象 。

8、：V是具有相同特性的数据元素的集 合 ， 称为顶点集 。
数据关系：R = E E= | v, wV 且 P(v, w), 顶点对 称为边或弧 ， P(v,w) 定义了 的意义或信息 ,图的抽象数据类型,12,基本操作：,初始化操作 CreateGraph(操作结果：构造一个顶点数为num ， 边数为0的图 。
,销毁操作 DestroyGraph(初始条件：图 G 存在 。
操作结果：销毁图 G 。
,引用型操作,FirstAdjVex(G, v);
初始条件：图 G 存在 ， v 是 G 中某个顶点 。
操作结果：返回 v 的第一个邻接点 。
若该顶点在 G 中没有邻接点 ， 则返回“空” 。
,若G ， 则称 w 为 v 的邻接点 ， 若(v 。

9、,w)G ， 则称 w 和 v 互为邻接点 。
,NextAdjVex(G, v, w);
初始条件:图G存在,v是G中某个顶点,w是v的邻接顶点 。
操作结果:返回 v 的（相对于 w 的）下一个邻接点 。
若 w是 v 的最后一个邻接点 ， 则返回“空” 。
,若 v 有多个邻接点 ， 则在图的存储结构建立之后 ， 其邻接点之间的相对次序也就自然形成了 。
,14,加工型操作,InsertEdge(初始条件：图 G 存在 ， v 和 w 是 G 中两个顶点 。
操作结果：在 G 中增添以v, w为顶点的边,DeleteEdge(初始条件：图 G 存在 ， v 和 w 是 G 中两个顶点 。
操作结果：在 G 中删除以v, w为顶点的边 。
,。

10、ADT Graph,15,16,7.2 图的存储结构,图的特点：,链式存储结构：,顺序存储结构：,难！,（多个顶点 ， 无序 ， 仅用顶点坐标无法表达相互关系）,可用多重链表,邻接矩阵(数组)表示法 邻接表(链式)表示法 十字链表表示法 邻接多重表表示法,但可用数组描述元素间关系 。
,非线性结构（m :n）,邻接矩阵,邻接表 十字链表 邻接多重表,各种表示法成立的原则：存入电脑后能惟一复原,17, 建立一个顶点表和一个邻接矩阵 。
,1. 邻接矩阵（数组）表示法,例1：,邻接矩阵：,A.Edge =,（v1 v2 v3 v4 v5),v1 v2 v3 v4 v5,分析1：无向图的邻接矩阵是对称的； 分析2： 。

11、顶点i 的度第 i 行 (列) 中1 的个数； 特别：完全图的邻接矩阵中 ， 对角元素为0 ， 其余全1 。
,顶点表：,下面无向图的邻接矩阵如何表示？,记录各个顶点信息,表示各个顶点之间关系, 设图 A = (V, E) 有 n 个顶点 ， 则图的邻接矩阵是一个二维数组 A.Edgenn ， 定义为：,0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0,18,例2 ：下面有向图的邻接矩阵如何表示？,分析1：有向图的邻接矩阵可能是不对称的 。
分析2：顶点vi的出度=第i行元素之和 ， OD(vi )= jA.Edge i j 顶点vi的入度=第i列元素之和 。
ID(vi。

12、)= iA.Edge j i 顶点的度=第i行元素之和+第i列元素之和, 即：TD( vi ) = OD( vi ) + ID( vi ),邻接矩阵：,A.Edge =,( v1 v2 v3 v4 ),v1 v2 v3 v4,注：在有向图的邻接矩阵中 ，第i行含义：以结点vi为尾的弧(即出度边）； 第i列含义：以结点vi为头的弧(即入度边） 。
,顶点表：,0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0,19,容易实现图的操作 ， 如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等 。
n个顶点需要n*n个单元存储边(弧);
空间效率为O(n2) 。
,例3 ： 有权图（即网络） 。

13、的邻接矩阵如何表示？,定义：,以有向网为例：,邻接矩阵：,N.Edge =,( v1 v2 v3 v4 v5 v6 ),邻接矩阵法优点：,邻接矩阵法缺点：,顶点表：, 5 7 4 8 9 5 6 5 3 1 ,v1 v2 v3 v4 v5 v6,对稀疏图而言尤其浪费空间 。
,20,注：用两个数组分别存储顶点表和邻接矩阵 #define INFINITY INT_MAX /最大值 #define MAX_VERTEX_NUM 20 /假设的最大顶点数 Typedef enum DG, DN, UG, UN GraphKind;
/有向/无向图 ， 有向/无向网,图的邻接矩阵在机内如何表示？ （参见教材 。

14、P161）,对于n个顶点的图或网 ， 空间效率=O(n2),Typedef struct ArcCell /弧（边）结点的定义 VRType adj;
/顶点间关系 ， 无权图取1或0；有权图取权值类型 InfoType *info;
/该弧相关信息的指针 ArcCell, AdjMatrix MAX_VERTEX_NUM MAX_VERTEX_NUM ;
,Typedef struct /图的定义 VertexType vexs MAX_VERTEX_NUM ;
/顶点表 ， 用一维向量即可(n) AdjMatrix arcs;
/邻接矩阵n*n Int Vernum, arcnum;
/顶点总数n ， 弧（ 。

15、边）总数e GraphKind kind;

来源：(未知)

【学习资料】网址：/a/2021/0330/0021813749.html

标题：[计算机软件及应用]数据结构图A( 二 )