《数据结构》课程授课教案（讲稿）第七章 图 第一节 概述 第二节 图的存储结构

课程名称：数据结构第 12 周，第12讲次摘要第七章图授课题目（章、节）第一节概述第二节图的存储结构【目的要求】通过本讲课程的学习，理解图的定义以及相关概念（完全图、连通图、强连通图等），掌握图的两种存储结构（邻接矩阵、邻接表），了解两种存储结构各自的特点。[重点】掌握邻接矩阵存储结构和邻接表存储结构的各自特点。【难点】掌握邻接矩阵存储结构和邻接表存储结构的各自特点。内容【本讲课程的引入】图也是一种非线性的数据结构，在图中结点之间的关系是多对多的，这是一种比树还要复杂的一种数据结构，从这一次课起我们开始学习图的相关知识。本讲课我们首先讨论图中涉及到的一系列的基本概念。【本讲课程的内容】第7章图7.1概述7.1.1图的基本概念1、图：由结点集合及结点间的关系集合组成的一种数据结构。记为G=（V，E），其中：V是G的顶点集合；E是G的边集合。2、有向图：图G中的每条边都是有方向的：3、无向图：图G中的每条边都是无方向的：（vl,v4）4、完全图：图G任意两个顶点都有一条边相连接；若n个顶点的无向图有n(n-1)/2条边，称为无向完全图若n个顶点的有向图有n(n-1）条边，称为有向完全图5、子图：设有两个图G1=（V1,EI）和G2=（V2、E2)。若V2iV1且E2iE1,则称图G2是图G1的子图。01D(a)图 1(b)图 26、带权图：指边上带权的图。其中权是指每条边标上具有与该边相关的数据信息。CDa7、路径：在图G=（V，E)中，若从顶点Vi出发，沿一些边经过顶点vpl，Vp2，"，Vpm到

课程名称：数据结构 第 12 周，第 12 讲次 摘 要 授课题目（章、节） 第七章 图 第一节 概述 第二节 图的存储结构 【目的要求】通过本讲课程的学习，理解图的定义以及相关概念（完全图、连通图、强连通图等），掌握图的 两种存储结构（邻接矩阵、邻接表），了解两种存储结构各自的特点。 【重 点】掌握邻接矩阵存储结构和邻接表存储结构的各自特点。 【难 点】掌握邻接矩阵存储结构和邻接表存储结构的各自特点。 内 容 【本讲课程的引入】图也是一种非线性的数据结构，在图中结点之间的关系是多对多的， 这是一种比树还要复杂的一种数据结构，从这一次课起我们开始学习图的相关知识。本讲 课我们首先讨论图中涉及到的一系列的基本概念。 【本讲课程的内容】 第 7 章 图 7.1 概述 7.1.1 图的基本概念 １、图：由结点集合及结点间的关系集合组成的一种数据结构。记为 G＝( V, E )，其中： V 是 G 的顶点集合；E 是 G 的边集合。 2、有向图：图 G 中的每条边都是有方向的； 3、无向图：图 G 中的每条边都是无方向的；(v1,v4) 4、完全图：图 G 任意两个顶点都有一条边相连接； 若 n 个顶点的无向图有 n(n-1)/2 条边, 称为无向完全图 若 n 个顶点的有向图有 n(n-1) 条边, 称为有向完全图 5、子图：设有两个图 G1＝(V1, E1) 和 G2＝(V2, E2)。若 V2 ÍV1 且 E2 ÍE1, 则称 图 G2 是 图 G1 的子图。 (a)图 1 (b)图２ 6、带权图：指边上带权的图。其中权是指每条边标上具有与该边相关的数据信息。 ７、路径：在图 G＝(V, E)中,若从顶点 vi 出发,沿一些边经过顶点 vp1,vp2,.,vpm，到

达顶点vj°则称顶点序列（vi,Vpl,Vp2，"，Vpm，Vj）为从顶点vi到顶点vj的路径。路径长度：非带权图的路径长度是指此路径上边的条数带权图的路径长度是指路径上各边的权之和。a8、简单路径：路径上各顶点V1,v2..，Vm均不互相重复。9、回路：若路径上第一个顶点v1与最后一个顶点vm重合，则称这样的路径为回路或环。10、连通图：在无向图中，若从顶点v1到项点v2有路径，则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的，则称此图是连通图。非连通图的极大连通子图叫做连通分量。11、强连通图：在有向图中，若对于每一对顶点vi和vj，都存在一条从到和从到vi的路径，则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。CYQQ.2-12、生成树：一个连通图的最小连通子图，它含有图中全部n个顶点，但只有n-1条边。13、结点的度：结点v的度是与它相关联的边的条数。记作TD(v)。在有向图中，结点的度等于该结点的入度与出度之和。其中结点v的入度是以v为终点的有向边的条数，记作ID(v)：结点v的出度是以v为始点的有向边的条数，记作OD(v)。14.邻接结点在无向图G中，若（u,v）是E(G)中的一条边，则称u和v互为邻接结点，并称边（u,v）依附于结点u和v。在有向图G中，若是E(G)中的一条边，则称结点u邻接到结点v，结点v邻接自结点u，并称边和结点u和结点v相关联。7.1.2图的抽象数据类型数据集合：由一组结点集合(vi和一组边e集合组成。当为带权图时每条边上权wj还构成权集合wjl。操作集合：（1）初始化initiate(n)：（2）插入结点insertVertex（vertex)：

达顶点 vj。则称顶点序列(vi,vp1,vp2,., vpm ,vj ) 为从顶点 vi 到顶点 vj 的路径。 路径长度：非带权图的路径长度是指此路径上边的条数；带权图的路径长度是指路径 上各边的权之和。 ８、简单路径：路径上各顶点 v1,v2,.,vm 均不互相重复。 ９、回路：若路径上第一个顶点 v1 与最后一个顶点 vm 重合，则称这样的路径为回路或 环。 10、连通图：在无向图中, 若从顶点 v1 到顶点 v2 有路径, 则称顶点 v1 与 v2 是连通的。 如果图中任意一对顶点都是连通的, 则称此图是连通图。非连通图的极大连通子图叫做连 通分量。 11、强连通图：在有向图中, 若对于每一对顶点 vi 和 vj, 都存在一条从 vi 到 vj 和从 vj 到 vi 的路径, 则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。 12、生成树：一个连通图的最小连通子图，它含有图中全部 n 个顶点，但只有 n-1 条边。 13、结点的度：结点 v 的度是与它相关联的边的条数。记作 TD(v)。在有向图中, 结点的 度等于该结点的入度与出度之和。其中结点 v 的入度是以 v 为终点的有向边的条数, 记 作 ID(v);结点 v 的出度是以 v 为始点的有向边的条数, 记作 OD(v)。 14.邻接结点 在无向图 G 中，若（u,v）是 E(G)中的一条边，则称 u 和 v 互为邻接结点， 并称边（u,v）依附于结点 u 和 v。在有向图 G 中，若＜u,v＞是 E(G)中的一条边，则称结 点 u 邻接到结点 v，结点 v 邻接自结点 u，并称边＜u,v＞和结点 u 和结点 v 相关联。 7.1.2 图的抽象数据类型 数据集合：由一组结点集合{vi}和一组边{ej}集合组成。当为带权图时每条边上权 wj 还构成权集合{wj}。 操作集合： （1）初始化 initiate(n)： （2）插入结点 insertVertex(vertex)：

（3）插入边insertEdge(vl，v2，weight)：（4）删除边deleteEdge(vl，v2)：（5）删除结点deleteVertex（vertex）：（6）第一个邻接结点getFirstVex（v)：（7）下一个邻接结点getNextVex(v1，v2)：（8）遍历depthFirstSearch（vs)：7.2图的存储结构图的存储结构主要有邻接矩阵和邻接表两种。7.2.1图的邻接矩阵存储结构假设图G=(V,E)有n个结点，即V={v0,vl,,vn-1)，E可用如下形式的矩阵A描述，对于A中的每一个元素aij，满足：1若(v,y)EE或EEau=否则1o由于矩阵A中的元素aij表示了结点vi和结点vj之间边的关系，或者说，A中的元素aij表示了结点vi和结点vj的邻接关系，所以矩阵A称作邻接矩阵。1、无权值的有向图的邻接矩阵设有向图具有n个结点，则用n行n列的矩阵A表示该有向图：并且A[i,j]=1，如果i至j有一条有向边：A[i,j]=0，如果i至j没有一条有向边。38[01111E00000V=QA=00001D01000[C00000(a)b)分析1：有向图的邻接矩阵可能是不对称的。分析2：顶点vi的出度=第i行为1的元素之和。顶点vi的入度=第i列为1的元素之和。顶点的度=第i行为1元素之和+第i列为1元素之和，即：TD（vi）=OD（vi）+ID（vi）2、无权值的无向图的邻接矩阵设无向图具有n个结点，则用n行n列的布尔矩阵A表示该无向图：并且A[i,j]=1，如果i至］有一条无向边；A[1j]=0，如果i至j没有一条无向边。G口[01111210010V=310001A=1411000510100(b)分析1：无向图的邻接矩阵是对称的；分析2：顶点i的度=第i行（列）中1的个数：

（3）插入边 insertEdge(v1, v2, weight)： （4）删除边 deleteEdge(v1, v2)： （5）删除结点 deleteVertex(vertex)： （6）第一个邻接结点 getFirstVex(v)： （7）下一个邻接结点 getNextVex(v1, v2)： （8）遍历 depthFirstSearch(vs)： 7.2 图的存储结构 图的存储结构主要有邻接矩阵和邻接表两种。 7.2.1 图的邻接矩阵存储结构 假设图 G=(V,E)有 n 个结点，即 V={v0,v1,.,vn-1}，E 可用如下形式的矩阵 A 描述， 对于 A 中的每一个元素 aij，满足： 由于矩阵 A 中的元素 aij 表示了结点 vi 和结点 vj 之间边的关系，或者说，A 中的元 素 aij 表示了结点 vi 和结点 vj 的邻接关系，所以矩阵 A 称作邻接矩阵。 1、无权值的有向图的邻接矩阵 设有向图具有 n 个结点，则用 n 行 n 列的矩阵 A 表示该有向图；并且 A[i,j] = 1 , 如果 i 至 j 有一条有向边；A[i,j]=0，如果 i 至 j 没有一条有向边。 分析 1：有向图的邻接矩阵可能是不对称的。 分析 2：顶点 vi 的出度=第 i 行为 1 的元素之和。顶点 vi 的入度=第 i 列为 1 的元素之和。 顶点的度=第 i 行为 1 元素之和+第 i 列为 1 元素之和, 即：TD( vi ) = OD( vi ) + ID( vi ) 2、无权值的无向图的邻接矩阵 设无向图具有 n 个结点，则用 n 行 n 列的布尔矩阵 A 表示该无向图；并且 A[i,j]=1 , 如果 i 至 j 有一条无向边；A[I,j]=0，如果 i 至 j 没有一条无向边。 分析 1：无向图的邻接矩阵是对称的； 分析 2：顶点 i 的度＝第 i 行 (列) 中 1 的个数；

特别：完全图的邻接矩阵中，对角元素为0，其余全1。3、带权图的邻接矩阵设带权图具有n个结点，则用n行n列的矩阵A表示该图。W若(i)EEE否则且询p否则且调0[1][02030O20622000408500030C010V405007080.5C7003.O0608000?(b)a邻接矩阵法优点：容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。邻接矩阵法缺点：n个顶点需要n*n个单元存储边（弧）：空间效率为0（n2)。7.2.2图的邻接表存储结构1、图的邻接表它是一种顺序存储与链式存储相结合的存储方法，顺序存储部分用来保存图中顶点的信息，链式存储部分用来保存图中边（或弧）的信息ded nadA自C0o62、邻接表存储法的特点：一它其实是对邻接矩阵法的一种改进分析1：对于n个顶点e条边的无向图，邻接表中除了n个头结点外，只有2e个表结点，空间效率为0(n+2e）。若是稀疏图(e<<n2)，则比邻接矩阵表示法0(n2)省空间。怎样计算无向图顶点的度？TD(Vi)=单链表中链接的结点个数分析2：在有向图中，邻接表中除了n个头结点外，只有e个表结点，空间效率为0(n+e)。若是稀疏图，则比邻接矩阵表示法合适。邻接表的优点：空间效率高：容易寻找顶点的邻接点：邻接表的缺点：判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。3、讨论：邻接表与邻接矩阵有什么异同之处？（1）联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。（2）区别：①对于任一确定的图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链

特别：完全图的邻接矩阵中，对角元素为 0，其余全 1。 3、带权图的邻接矩阵 设带权图具有 n 个结点，则用 n 行 n 列的矩阵 A 表示该图。 邻接矩阵法优点： 容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、 找顶点的邻接点等等。 邻接矩阵法缺点：n 个顶点需要 n*n 个单元存储边(弧);空间效率为 O(n2)。 7.2.2 图的邻接表存储结构 1、图的邻接表 它是一种顺序存储与链式存储相结合的存储方法，顺序存储部分用来保存图中顶点的 信息，链式存储部分用来保存图中边（或弧）的信息 2、邻接表存储法的特点：—它其实是对邻接矩阵法的一种改进 分析 1: 对于 n 个顶点 e 条边的无向图，邻接表中除了 n 个头结点外，只有 2e 个表结点, 空间效率为 O(n+2e)。 若是稀疏图(e<<n2)，则比邻接矩阵表示法 O(n2)省空间。 怎样计算无向图顶点的度？TD(Vi)=单链表中链接的结点个数 分析 2: 在有向图中，邻接表中除了 n 个头结点外，只有 e 个表结点,空间效率为 O(n+e)。 若是稀疏图，则比邻接矩阵表示法合适。 邻接表的优点：空间效率高；容易寻找顶点的邻接点； 邻接表的缺点：判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵 方便。 3、讨论：邻接表与邻接矩阵有什么异同之处？ （1） 联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非 零元素的个数。 （2） 区别： ① 对于任一确定的图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链

接次序与顶点编号无关）。②邻接矩阵的空间复杂度为0(n2)，而邻接表的空间复杂度为0(n+e)。（3）用途：邻接矩阵多用于稠密图的存储；而邻接表多用于稀疏图的存储（e<<n2）。【本讲课程的小结】对于图这种数据结构它的定义及相关概念比较容易理解，关键是我们要掌握在计算机中我们该如何存储图，我们提到了最常用的两种方式，一个是邻接矩阵，一个是邻接表，两种不同的存储方式各有特点，在遇到具体问题时应能根据图的特点选择适当的存储结构，这就需要我们掌握邻接矩阵和邻接表之间的异同点。【本讲课程的作业】对于下图所示的有向图，给出：（1）该有向图的邻接矩阵存储结构；（2）该有向图的邻接表存储结构

接次序与顶点编号无关）。 ② 邻接矩阵的空间复杂度为 O(n2),而邻接表的空间复杂度为 O(n+e)。 （3） 用途： 邻接矩阵多用于稠密图的存储； 而邻接表多用于稀疏图的存储（e<<n2）。 【本讲课程的小结】对于图这种数据结构它的定义及相关概念比较容易理解，关键是我们 要掌握在计算机中我们该如何存储图，我们提到了最常用的两种方式，一个是邻接矩阵， 一个是邻接表，两种不同的存储方式各有特点，在遇到具体问题时应能根据图的特点选择 适当的存储结构，这就需要我们掌握邻接矩阵和邻接表之间的异同点。 【本讲课程的作业】 对于下图所示的有向图，给出： （1）该有向图的邻接矩阵存储结构； （2）该有向图的邻接表存储结构