教黎 第七章图 程序设计—数据结构 图的遍历算法及其应用 2) 邻接表的头结点 typedef struct VNode! Vertex Type data; 体顶点信息制 ArcNode *firstarc; 体邻接表指针*/ }VNode,AdjList[MAX VERTEX NUM]; 3)图的整体结构 typedef struct{ AdjList vertices; int vexnum,arcnum; GraphKind kind; }ALGraph; 4、邻接矩阵与邻接表的对比 假设图为G,顶点数为n,边/弧数为e。 A邻接矩阵 B邻接表 存储空间 0(n+n2) O(n+e) T1(n)=0(e+n2)或T2(n=0(e*n+n2) T1(n)=0(n+e)或T2(n)=0(e*n) 图的创建算 T1(n)是指在输入边/弧时，输入的顶点信息为顶点的编号：而T2(n)则指 法 在输入边弧时，输入的为顶点本身的信息，此时需要查找顶点在图中的 位置 GarcM小a(第i行之利成 无向图中求 j-0 第ⅰ顶点的度 cana时第i列之利 G.vertices[i.firstarc所指向的邻接 表包含的结点个数 j=0 无向网中求 第i行/列中ad值不为NFINITY的 第ⅰ顶点的度 元素个数 有向图中求 入度： acU0a(第i列 第i顶点的入 0 入度：扫描各顶点的邻接表，统计 出度 出度： GaresiUJad(第i行 表结点的adjvex为i的表结点个数 /0 T(n)=O(n+e) 有向网中求 入度：第i列中ad值不为NFINITY 出度：G.vertices[i).firstarc所指向 第i顶点的入/ 的元素个数 的邻接表包含的结点个数 出度 出度：第i行中adi值不为NFINITY 的元素个数 无向图： GonaEad 无向网：G.arcs中adj值不为 无向图/网：图中表结点数目的一 统计边/弧数 NFINITY的元素个数的一半 义 有向图： cacf1a时 有向图/网：图中表结点的数目 i=0j=0 有向网：G.arcs中adj值不为 INFINITY的元素个数 文档编号 完成时间 完成人张昱 修改时间20026-6 第4页程序设计——数据结构 第七章 图 图的遍历算法及其应用 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 4 页 2) 邻接表的头结点 typedef struct VNode{ VertexType data; /* 顶点信息 */ ArcNode *firstarc; /* 邻接表指针 */ }VNode, AdjList[MAX_VERTEX_NUM]; 3) 图的整体结构 typedef struct { AdjList vertices; int vexnum, arcnum; GraphKind kind; }ALGraph; 4、邻接矩阵与邻接表的对比 假设图为 G，顶点数为 n，边/弧数为 e。 A 邻接矩阵 B 邻接表 存储空间 O(n+n2 ) O(n+e) 图的创建算 法 T1(n)=O(e+n2 )或 T2(n)=O(e*n+n2 ) T1(n)=O(n+e)或 T2(n)=O(e*n) T1(n)是指在输入边/弧时，输入的顶点信息为顶点的编号；而 T2(n)则指 在输入边/弧时，输入的为顶点本身的信息，此时需要查找顶点在图中的 位置 无向图中求 第 i 顶点的度 G arcs i j adj n j . [ ][ ]. 1 0  − = (第 i 行之和)或 G arcs j i adj n j . [ ][ ]. 1 0  − = (第 i 列之和) G.vertices[i].firstarc 所指向的邻接 表包含的结点个数 无向网中求 第 i 顶点的度 第 i 行/列中 adj 值不为 INFINITY 的 元素个数 有向图中求 第i顶点的入/ 出度 入度：  − = 1 0 . [ ][ ]. n j G arcs j i adj (第 i 列) 出度：  − = 1 0 . [ ][ ]. n j G arcs i j adj (第 i 行) 入度：扫描各顶点的邻接表，统计 表结点的adjvex为i的表结点个数 T(n)=O(n+e) 出度：G.vertices[i].firstarc 所指向 的邻接表包含的结点个数 有 向网中求 第i顶点的入/ 出度 入度：第 i 列中 adj 值不为 INFINITY 的元素个数 出度：第 i 行中 adj 值不为 INFINITY 的元素个数 统计边/弧数 无向图：  − = − = 1 0 1 0 . [ ][ ]. 2 1 n i n j G arcs i j adj ) 无向网： G.arcs 中 adj 值不为 INFINITY 的元素个数的一半 有向图：  − = − = 1 0 1 0 . [ ][ ]. n i n j G arcs i j adj 有向网： G.arcs 中 adj 值不为 INFINITY 的元素个数 无向图/网：图中表结点数目的一 半 有向图/网：图中表结点的数目