图的基本操作如下 (1) creatgraph(&g)创建一个图的存储结构 (2) insertvertex(&g,ν)在图g中增加一个顶 点v (3) deletevertex(&g,)在图g中删除顶点v及 所有和顶点相关联的边或弧。 (4) insertedge(&g,,u)在图g中增加一条从 顶点V到顶点u的边或弧。 (5) deleteedge(&g,v,u)在图g中删除一条从 顶点V顶点u的边或弧
图的基本操作如下： （1）creatgraph（&g） 创建一个图的存储结构。 （2）insertvertex（&g，v） 在图g中增加一个顶 点v。 （3）deletevertex（&g，v） 在图g中删除顶点v及 所有和顶点v相关联的边或弧。 （4）insertedge（&g，v，u） 在图g中增加一条从 顶点v到顶点u的边或弧。 （5）deleteedge（&g，v，u） 在图g中删除一条从 顶点v到顶点u的边或弧
(6 trave(g) 遍历图g (7) locatevertex(g,v)求顶点v在图g中的位 序 (8) fiirstvertey(g,V)求图g中顶点v的第一个 邻接点 (9)degree(g,V 求图g中顶点v的度数 (10) nextvertex(g,V,W)求图g中与顶点v相 邻接的顶点w的下一个邻接点。即求图g中顶点v的 某个邻接点,它的存储顺序排在邻接点w的存储位 置之后。 3 ADT Graph
（6）trave（g） 遍历图g。 （7）locatevertex（g，v） 求顶点v在图g中的位 序。 （8）fiirstvertex（g，v） 求图g中顶点v的第一个 邻接点。 （9）degree（g，v） 求图g中顶点v的度数。 （10）nextvertex（g，v，w） 求图g中与顶点v相 邻接的顶点w的下一个邻接点。即求图g中顶点v的 某个邻接点，它的存储顺序排在邻接点w的存储位 置之后。 } ADT Graph
8.3图的基本存储结构 VO V2 V3 V4 V3 图的存储结构至少要保存两类信 1)顶点的数据 如何表示顶点间的关系? 2)顶点间的关系 约定: G=<VE>是图,V={o,V1,V2,…Vn1}设顶点的 角标为它的编号
8.3图的基本存储结构 图的存储结构至少要保存两类信息： 1)顶点的数据 2)顶点间的关系 约定: G=<V, E>是图, V={v0 ,v1 ,v2 , … vn-1 },设顶点的 角标为它的编号 如何表示顶点间的关系？ V0 V3 V4 V1 V2 V0 V1 V2 V3
83.1邻接矩阵及其实现 非网络的邻接矩阵 给定图G=(V,E),其中V(G)={, Ⅵ,…,Vn},G的邻接矩阵( Adacency Matrⅸ) 具有如下性质的η阶方阵 A[,-1,如果<j>∈E或者(i)∈E 10.否则 无向图的邻接矩阵是对称的,有向图的邻接矩 阵可能是不对称的
8.3.1邻接矩阵及其实现 给定图G=（V，E），其中V（G）={v0，…， vi，…，vn-1 }，G的邻接矩阵（Adacency Matrix）是 具有如下性质的n阶方阵： = , , , ( , ) A [ ] 否 则 如 果 或 者 0 1 < i j > E i j E i , j 无向图的邻接矩阵是对称的，有向图的邻接矩 阵可能是不对称的。 一、非网络的邻接矩阵
图的邻接矩阵示例 0100 A1=1010A2 1010 1101 1100 1010 0100 图87无向图G及有向图G的邻接矩阵表示
v0 v1 v3 v2 v3 v1 v0 v2 图的邻接矩阵示例 0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 0 1 0 0 1 0 1 0 1 1 0 0 0 1 0 0 A1= A2= 图8.7 无向图G9及有向图G10的邻接矩阵表示