2014/47 §7.2.1邻接矩阵表示法 §7.2.2邻接表 链式存储结构 。建立无向图的邻接矩阵表示 stpl:输入顶点数、边数O四 为每个顶点的邻接关系建立一个单链表，将头结点 放在一个数组中，形成一个顶点表和一个边表。 se2:输入顶点表 o 顶点表结点： 顶点数据 step巾：初始化邻接矩阵 0w) 标+为向第一个边表结点（边表的头结点） sen4:输入边（及权值） O(e) 边表结点： 接点号 ☐→边浓站点法边仪，则端个级 边表示：（化，y》,因为”和分别存情在顶点表的th 和h分量中，故只需在y的边表中存放序号引即可。 87.2.2邻接表 S7.22邻接表 例： 123 typedef struct vnode顶点表结点 03子2 VertexType vertex;顶点数据罐 10 EdgeNode+firestedge:/边表头指针 3男一 0】A }Vertex Node,AdjList[Max VertexNum];I邻接衰类里 顶点表 说明 typedef structf typedef struct node边结点 AdjLis过t adjlist:/邻接表 int ad小vex点序号 intn,e:顶点数和边数 struct node*next指向下一个边铺点 ALGraphi 著有权，则增加一媒 EdgeNode; 87.2.2邻接表 87.2.2邻接表 无向图的邻接表 有向图的邻接表 (化，)eE,则在y的邻接表中有一a1ex=的边表结点。 表结盒，在，的邻接表中有一个时的边 在y,的邻接表中有一aex=1的边表结点。 每边表示了1次，所以共有e个边表结点。 每条边表示了两次，所以一共有2个边表结点 空间复杂度为Om+e),邻接矩阵为0。 此时的边表称为出边表。 出边表中求出度易，求入度难。 稀疏图邻接表节省空间，调密图邻接矩阵为宜。 表的近表给轰：的邻接表中有一个 逆邻接表：<，y>EE 此时的边表称为入边表。 入边表中求入度易，求出度难。 32014/4/7 3 §7.2.1 邻接矩阵表示法  建立无向图的邻接矩阵表示 step1：输入顶点数、边数 step2：输入顶点表 step3 初始化邻接矩阵 13 ： step4：输入边（及权值） §7.2.2 邻接表  链式存储结构 为每个顶点的邻接关系建立一个单链表，将头结点 放在一个数组中，形成一个顶点表和一个边表。 顶点表结点： 14 边表结点： 边表示： ，因为 和 分别存储在顶点表的ith 和jth分量中，故只需在 的边表中存放序号j即可。 §7.2.2 邻接表  例： 15  说明 typedef struct node{//边表结点 int adjvex；//邻接点序号 struct node * next; //指向下一个边表结点 //若有权，则增加一域 }EdgeNode； §7.2.2 邻接表 typedef struct vnode{//顶点表结点 VertexType vertex；//顶点数据域 EdgeNode * firestedge; //边表头指针 }VertexNode，AdjList[MaxVertexNum]；//邻接表类型 16 typedef struct { AdjList adjlist; //邻接表 int n, e; //顶点数和边数 }ALGraph； §7.2.2 邻接表  无向图的邻接表 , 则在 的邻接表中有一 的边表结点。 在 的邻接表中有一 的边表结点。 每条边表示了两次，所以一共有2e个边表结点。 17 空间复杂度为 ，邻接矩阵为 。 稀疏图邻接表节省空间，稠密图邻接矩阵为宜。 §7.2.2 邻接表  有向图的邻接表 , 在 的邻接表中有一个 的边 表结点。 每边表示了1次，所以共有e个边表结点。 此时的边表称为出边表 18 。 出边表中求出度易，求入度难。 逆邻接表： , 在 的邻接表中有一个 的边表结点。 此时的边表称为入边表。 入边表中求入度易，求出度难