图的基本操作如下: (1) creatgraph(&g)创建一个图的存储结构。 (2) insertvertex(&g,v)在图g中增加一个顶 点v (3) deletevertex(&g,v)在图g中删除顶点 所有和顶点V相关联的边或弧。 (4) insertedge(&g,V,u)在图g中增加一条从 顶点V到顶点u的边或弧。 (5) deleteedge(&g,V,u)在图g中删除条从 顶点到顶点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) firstvertex(g,V)求图g中顶点v第 邻接点。 (9) degree(g,v)求图g中顶点v的度数。 (10) nextvertex(g,v,W)求图g中与顶点v相 邻接的顶点w的下一个邻接点。即求图g中顶点v的 某个邻接点,它的存储顺序排在邻接点w的存储位 置之后。 1 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 V3 V4 V2V3 图的存储结构至少要保存两类信户 1)顶点的数据 如何表示顶点间的关系? 2顶点间的关系 约定: G=<VE>是图v={,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),其中∨(G)={yo, …,Vn1},G的邻接矩阵( Adacency Ma×)是 具有如下性质的n阶方阵 A[,门= ∫1如果<>E或者(i∈E 0,否则 无向图的邻接矩阵是对称的,有向图的邻接矩 阵可能是不对称的
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 无向图的邻接矩阵是对称的，有向图的邻接矩 阵可能是不对称的。 一、非网络的邻接矩阵
图的邻接矩阵示例 01 0100 1010 A1= 10 10A2 1101 100 1010 0100 图8.7无向图G及有向图G10的邻接矩阵表示
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的邻接矩阵表示