例:无向图的邻接表邹接表 当邻接表 的存储结 构形成后, 图便唯一 定! 3 V 注:邻接表不唯一,因各个边结点的链入顺序是任意的。 例:有向图的邻接表 邻接表(出边) v2
26
邻接表存储法的特点:它其实是对邻接矩阵法的一种改进 分析1:对于n个顶点e条边的无向图,邻接表中除了n个头结点 外,只有2e个表结点,空间效率为0(m+2e)。 若是稀疏图(e<n2),则比邻接矩阵表示法0(n2省空间。 怎样计算无向图顶点的度?m(V)单链表中链接的结点个数 分析2在有向图中邻接表中除了n个头结点外,只有e个表结点空 间效率为omn+e。若是稀疏图,则比邻接矩阵表示法合适。 怎样计算有向图项点的出度?oDV)=单链出边表中链接的结点数 怎样计算有向图项点的入度?IDV)=邻接点为v的弧个数 怎样计算有向图顶点的度:TD(V)=OD(V)+D吟需遍历全表 邻接表的优点:空间效率高;容易寻找顶点的邻接点; 邻接表的缺点:判断两顶点间是否有边或弧,需搜索两结点对 应的单链表,没有邻接矩阵方便
27
讨论:邻接表与邻接矩阵有什么异同之处? 联系:邻接表中每个链表对应于邻接矩阵中的一行,链 表中结点个数等于一行中非零元素的个数。 区别: ①对于任一确定的无向图,邻接矩阵是唯一的(行列号 与顶点编号一致),但邻接表不唯一(链接次序与顶 点编号无关)。 ②邻接矩阵的空间复杂度为0(n2),而邻接表的空间复杂 度为0(n+e)。 用途:邻接矩阵多用于稠密图的存储(e接近n(n-)2);而 邻接表多用于稀疏图的存储(e<<n2)
28
的豪储录 # define maX verteX num20M设的最大顶点数 Typedef struct ArcNode t int adjvex; ∥该弧所指向的顶点位置 struct ArcNode'nextarcs;∥指向下一条弧的指针 InfoArc*info;‖该弧相关信息的指针 ArcNode Typedef struct VNode J顶点结构 VertexType data;顶点信息 ArcNode* firstarc;∥指向依附该顶点的第一条弧的指针 3 VNode, AdjList[ MAX_VERTEX_NUM]; Typedef struct t ∥图结构 AdjList vertices;∥应包含邻接表 int vexnum, archon;∥应包含顶点总数和弧总数 int kind ∥还应说明图的种类(用标志) } ALGraph;/图结构 空间效率为0(m+2e)或0(n+e) 时间效率为0(n+en)
29
void CreateUDG(ALGraph &G 【∥采用邻接表存储表示,构造无向图G( G kind=UDG)。 cin> G. vexnum> G, arcum> IncInfo;∥ cInfo为0表明各弧不含其它信息 for(i=0; i<G. vexnum; ++i)t ∥构造表头向量 cin >>Gvertices[[ data ∥输入顶点值 G vertices[]. firstarc=NUL;∥初始化链表头指针为"空 I/for tor(K叫U;K<G. arcum;#K{输入各放并构造邻接表 cin >>v1>>v2: 输入一条弧的始点和终点 i=Locate VeX(G, v1);j=Locate Vex(G, v2) ∥确定V和v2在G中位置,即顶点的序号 pi= new ArcNode pi→> adjvex=j; ∥对弧结点赋邻接点"位置"信息 pi-> nextarc=G vertices[]. firstarc; Gvertices[]. firstarc= pi ∥插入链表 G vertices,前插 pj=new ArcNode; pj-> adjvex=i;∥对弧结点赋邻接点"位置"信息 pj-> nextarc=Gvertices []. firstarc; Gvertices[]. firstarc= pj ∥插入链表 Gvertices[ if (IncInfo) ∥若弧含有相关信息,则输入 [cin>> pj->info; pi->info=pj->info; 1 }∥for ∥ CreateUDG
30