@图的基本操作 (1) CreateGraph(G):图的创建操作。 初始条件:无。 操作结果:生成一个没有顶点的空图G 8(2) Locatevex(G,v):顶点定位函数。 初始条件:G已经存在,v是一个顶点。 操作结果:返回v在G中的位置,若G中无此顶点,则返回“空”。 (3) FirstAdj(Gv):求第一个邻接点函数。 初始条件:G已经存在,v是G中某个顶点。 操作结果:返回v的第一个邻接点,若v在G中无邻接点,则返回 空 意(4) NextAdj(g,v,w):求下一个邻接点函数。 初始条件:G已经存在,v是G中某个顶点,w是v的一个邻接点。 操作结果:返回v的邻接点中w之后的下一个邻接点,若无下 邻接点,则返回“空”。 计算机教研宦 第11页 2021/2/19
Data Structure 数 据 结 构—— 第 7 章 图 和 广 义 表 胡建华 2021/2/19 计算机教研室 第11页 图的基本操作 (1) CreateGraph(G)：图的创建操作。 初始条件：无。 操作结果：生成一个没有顶点的空图G。 (2) LocateVex(G,v)：顶点定位函数。 初始条件：G已经存在，v是一个顶点。 操作结果：返回v在G中的位置，若G中无此顶点，则返回“空” 。 (3) FirstAdj(G,v)：求第一个邻接点函数。 初始条件：G已经存在，v是G中某个顶点。 操作结果：返回v的第一个邻接点，若v在G中无邻接点，则返回 “空” 。 (4) NextAdj(G,v,w)：求下一个邻接点函数。 初始条件：G已经存在，v是G中某个顶点，w是v的一个邻接点。 操作结果：返回v的邻接点中w之后的下一个邻接点，若无下 一邻接点，则返回“空”
(5) getVex Val(G,v):取顶点元素值函数 初始条件:G已经存在,V是G中某个顶点。 操作结果:返回v的值。 (6) Updatevex(G,v,e):修改顶点元素操作。 初始条件:G已经存在,v是G中某个顶点 操作结果:将v的元素值改为e。 (7) Addvex(G,v):增加顶点操作。 初始条件:G已经存在,且G中不存在顶点v。 操作结果:在G中增加一个新顶点v。 7(8) deletevex(G,v):删除顶点操作。 初始条件:G已经存在,V是G中某个顶点。 操作结果:从G中删除顶点ⅴ以及与v相关的弧或边。 计算机教研宦 第12页 2021/2/19
Data Structure 数 据 结 构—— 第 7 章 图 和 广 义 表 胡建华 2021/2/19 计算机教研室 第12页 (5) getVexVal(G,v)：取顶点元素值函数。 初始条件：G已经存在，v是G中某个顶点。 操作结果：返回v的值。 (6) Updatevex(G,v,e)：修改顶点元素操作。 初始条件：G已经存在，v是G中某个顶点。 操作结果：将v的元素值改为e。 (7) AddVex(G,v)：增加顶点操作。 初始条件：G已经存在，且G中不存在顶点v。 操作结果：在G中增加一个新顶点v。 (8) deletevex(G,v)：删除顶点操作。 初始条件：G已经存在，v是G中某个顶点。 操作结果：从G中删除顶点v以及与v相关的弧或边
(9) AddArc(G,arc):增加弧(或边)操作, 初始条件:G已经存在,arc是一条弧(或边) 操作结果:在G中增加一条弧(或边)arc。 (10) deleteR(G,v,w):删除弧(或边)操作 初始条件:G已经存在,v,w是G中的两个顶点。 操作结果:从G中删除弧v,W>,若G为无向图,则删除边(v,w) (11) destory(G):撤消图操作。 初始条件:G已经存在 操作结果:将图G清除。 7(12) TraverseGraph(G,v):遍历图操作。 初始条件:G已经存在,V是指定的起始顶点。 操作结果:按照某种规则将图G的每个顶点进行遍历。 计算机教研宦 第13页 2021/2/19
Data Structure 数 据 结 构—— 第 7 章 图 和 广 义 表 胡建华 2021/2/19 计算机教研室 第13页 (9) AddArc(G,arc)：增加弧（或边）操作。 初始条件：G已经存在，arc是一条弧（或边）。 操作结果：在G中增加一条弧（或边）arc。 (10) deleteArc(G,v,w): 删除弧（或边）操作。 初始条件：G已经存在，v,w是G中的两个顶点。 操作结果：从G中删除弧<v,w>，若G为无向图，则删除边(v,w)。 (11) destoryG(G)：撤消图操作。 初始条件：G已经存在。 操作结果：将图G清除。 (12) TraverseGraph (G，v)：遍历图操作。 初始条件：G已经存在，v是指定的起始顶点。 操作结果：按照某种规则将图G的每个顶点进行遍历
72图的存储结构 计算机教研宦 第14页 2021/2/19
Data Structure 数据结构—— 第7章图和广义表 胡建华 2021/2/19 计算机教研室 第14 页 7.2 图的存储结构
7.2.1图的数组(邻接矩阵)存储表示 邻接矩阵—表示顶点间相联关系的矩阵 定义:设G=(V,E)是有n≥1个顶点的图,G的邻接矩阵A是具有以下性 质的n阶方阵 A[i,小 ,若(v,v)<v1,v1>∈BG) 0,其它 ①「0110 例 2 ② 000 000 0 例① ④①② 01010 0101 ③010 00 G2 计算机教研宦 第15页 ⑤o1100 2021/2/19
Data Structure 数 据 结 构—— 第 7 章 图 和 广 义 表 胡建华 2021/2/19 计算机教研室 第15页 7.2.1 图的数组(邻接矩阵)存储表示 邻接矩阵——表示顶点间相联关系的矩阵 定义：设G=(V,E)是有n1个顶点的图，G的邻接矩阵A是具有以下性 质的n阶方阵 = 0，其它 1,若(v , v )或 v , v E(G) [ , ] i j i j A i j 例 G1 2 4 1 3 例 1 5 3 2 4 G2 0 1 1 0 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0