西安石油大学：《数据结构》精品课程资源（PPT教学课件）使用C语言（第4版）第09章 图

/无向图的邻接矩阵一定是对称矩阵 100 2345 A=100 100 010 110 10 00 (a) 有向图的邻接矩阵一般是非对称矩阵 0111 00000 A=0000 D 01000 0000 (b) 其中表示了图的顶点集合,A表示了图的邻接矩阵

无向图的邻接矩阵一定是对称矩阵 2 1 4 3 5                 = 5 4 3 2 1 V                 = 1 0 1 0 0 1 1 0 0 0 1 0 0 0 1 1 0 0 1 0 0 1 1 1 1 A (b) (a) 有向图的邻接矩阵一般是非对称矩阵 其中V表示了图的顶点集合，A表示了图的邻接矩阵 B A D C E                 = E D C B A V                 = 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 A (b) (a)

带权图及其邻接矩阵 02030∞∞ 200 40 30∞050∞∞ A 40500708 00∞700 o80∞0 (a) 其中表示了图的顶点集合,A表示了图的邻接矩阵。对于 带权图,邻接矩阵第行中所有04的元素个数等于第价个 顶点的出度,邻接矩阵第例列中所有0<anx的元素个数等于 第个顶点的入度

2 1 4 3 5 6                                       = 8 0 0 7 0 0 40 5 0 0 70 80 30 0 5 0 20 0 4 0 0 20 3 0 A                     = 6 5 4 3 2 1 V (a) (b) 20 40 30 50 70 80 带权图及其邻接矩阵 其中V表示了图的顶点集合，A表示了图的邻接矩阵。对于 带权图，邻接矩阵第i行中所有0<aij<∞的元素个数等于第i个 顶点的出度，邻接矩阵第j列中所有0<aij<∞的元素个数等于 第j个顶点的入度

2图的邻接表存储结构 当图的边数少于顶点个数且顶点个数值较大时,图的邻接 nxn矩阵的存储问题就变成了稀疏矩阵的存储问题,此时,邻 接表就是一种较邻接矩阵更为有效的存储结构。 dat a sorce ad dest next 1B ∧ D 01234 4 E

2.图的邻接表存储结构 当图的边数少于顶点个数且顶点个数值较大时，图的邻接 n×n矩阵的存储问题就变成了稀疏矩阵的存储问题，此时，邻 接表就是一种较邻接矩阵更为有效的存储结构。 B A D C E ( a) 0 1 2 3 4 A B C D E 0 dat a s orce 1 4 3 2 adj dest next 2 3 4 1 1 ∧ ∧ ∧ ∧ ( b) 4 ∧

数组的data存储图的顶点信息, sorce域存储该顶点在数 组中的下标序号,ad为该顶点的邻接顶点单链表的头指针。 第行单链表中的dest存储所有起始顶点为v的邻接项点v在 数组中的下标序号,n为单链表中下一个邻接顶点的指针 城。如果是带权图,单链表中需再增加cost,用来存储边 vy>的权值wyo 问题:邻接表存储结构和数组一章中的什么存储结构类似?

数组的data域存储图的顶点信息，sorce域存储该顶点在数 组中的下标序号，adj域为该顶点的邻接顶点单链表的头指针。 第i行单链表中的dest域存储所有起始顶点为vi的邻接顶点vj在 数组中的下标序号，next域为单链表中下一个邻接顶点的指针 域。如果是带权图，单链表中需再增加cost域，用来存储边 <vi ,vj>的权值wij。 问题：邻接表存储结构和数组一章中的什么存储结构类似？

93图的实现 1邻接矩阵存储结构下图操作的实现 #include Seqlist. h typedef struct Seqlist vertices; int edge Max Vertices Max vertices int numofEdges; JAdjMGraph;

9.3 图的实现 1.邻接矩阵存储结构下图操作的实现 #include "SeqList.h" typedef struct { SeqList Vertices; int edge[MaxVertices][MaxVertices]; int numOfEdges; }AdjMGraph;