72图的抽象数据类型 ∥返回边 oneeye的始点 int FromVertex(Edge oneedge) 返回边 oneedge的终点 int ToVertex(Edge oneedge) 返回边 oneedge的权 int Weight(edge oneedge); “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7.2 图的抽象数据类型 //返回边oneEdge的始点 int FromVertex(Edge oneEdge); //返回边oneEdge的终点 int ToVertex(Edge oneEdge); //返回边oneEdge的权 int Weight(Edge oneEdge); };
73图的存储结构 7.31相邻矩阵 732邻接表 7.33十字链表 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7.3 图的存储结构 ◼ 7.3.1 相邻矩阵 ◼ 7.3.2 邻接表 ◼ 7.3.3 十字链表
73.1相邻矩阵 图的相邻矩阵( adjacency matriⅸ,或邻接矩阵)表示顶 点之间的邻接关系,即表示顶点之间有边或没有边的 情况。 设G=<V,E>是一个有n个顶点的图,则图的相邻矩 阵是一个二维数组A[n,m],定义如下 All, jE ∫1,若(V,V∈E或V,V∈E 0,若(,V)zE或W,V>E ■对于n个顶点的图,相邻矩阵的空间代价都为O(n2),与边数无关 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7.3.1 相邻矩阵 图的相邻矩阵(adjacency matrix，或邻接矩阵)表示顶 点之间的邻接关系，即表示顶点之间有边或没有边的 情况。 设G = <V，E>是一个有n个顶点的图，则图的相邻矩 阵是一个二维数组A[n，n]，定义如下： 1 E E A[i j]= 0 E E i j i j i j i j ，若(V ，V ) 或<V ，V > ， ，若(V ，V ) 或<V ，V > ◼对于n个顶点的图，相邻矩阵的空间代价都为O(n2)，与边数无关
01000 10001 A7= 01010 V3 10000 00010 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 A7= 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0
03015 3040 A4= 15 0406 15060 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 A4= 0 3 0 15 3 0 4 0 0 4 0 6 15 0 6 0