数据结构第七章图.ppt

数据结构课件第七章图现在学习的是第1页，共76页7.1 7.1 7.1 7.1 图的定义和术语图的定义和术语图的定义和术语图的定义和术语 1图的定义图的定义定义：图（定义：图（Graph）是由）是由非空非空的的顶点集合顶点集合和一个描述顶和一个描述顶点之间关系点之间关系（边或者弧）（边或者弧）的集合组成。的集合组成。其二元组定义为：其二元组定义为：G（V，E）Vvi|viDataObjectE(vi,vj)|vi,vjV且且P(vi,vj)其中，其中，G表示一个图，表示一个图，V是图是图G中顶点的集合中顶点的集合，E是图是图G中边的集合。中边的集合。集合集合E可以是空集，若可以是空集，若E为空，则该图只有顶点而没有为空，则该图只有顶点而没有边。边。现在学习的是第2页，共76页图的应用举例例例1 1 交通图（公路、铁路）交通图（公路、铁路）顶点顶点：地点：地点 边：边：连接地点的公路连接地点的公路例例2 2 电路图电路图 顶点顶点：元件：元件 边：边：连接元件之间的线路连接元件之间的线路例例3 3 各种流程图各种流程图 如产品的生产流程图如产品的生产流程图 顶点顶点：工序：工序 边：边：各道工序之间的顺序关系各道工序之间的顺序关系V0V0V4V4V3V3V1V1V2V2V0V0V2V2V3V3V1V1现在学习的是第3页，共76页2图的相关术语图的相关术语n 有向图和无向图有向图和无向图在在图图中中，若若用用箭箭头头标标明明了了边边是是有有方方向向性性的的，则则称称这这样样的的图图为为有有向向图，否则称为，否则称为无向无向图。在在无无向向图图中中，一一条条边边（x,y）与与（y,x）表表示示的的结结果果相相同同，用用圆括号圆括号表示。例如：表示。例如：G1=(V1,E1)其中：其中：V1=v0,v1,v2,v3,v4E1=(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3),(v2,v4)无序对无序对(vi,vj)(vi,vj)：用连接顶点用连接顶点vivi、vjvj的的线段表示，称为线段表示，称为无向无向边；边；无向图无向图G1G1V0V0V4V4V3V3V1V1V2V2现在学习的是第4页，共76页在在有有向向图图中中，一一条条边边与与表表示示的的结结果果不不相相同同，用用尖尖括括号号表表示示。表表示示从从顶顶点点x出出发发向向顶顶点点y的的边边，x为为始始点点，y为为终终点点，有有向向边边也也称称为为弧弧，x为为弧弧尾尾，y为为弧弧头头,则则表表示示为为一一条条弧弧,而而表示表示y为弧尾，为弧尾，x为弧头的另一条弧为弧头的另一条弧。例如：例如：G2=(V2,E2)其中：其中：V2=v0,v1,v2,v3E2=,有向图有向图G2G2V0V0V2V2V3V3V1V1有序对有序对 ：用以用以vivi为起点、以为起点、以vjvj为为终点的有向线段表示，终点的有向线段表示，称为有向边或弧；称为有向边或弧；在图在图G中，若所有边都是无向边，则称中，若所有边都是无向边，则称G为为无向图无向图；在图在图G中，若所有边都是有向边，则称中，若所有边都是有向边，则称G为为有向图有向图；在图在图G中，既有无向边又有有向边，则称中，既有无向边又有有向边，则称G为为混合图混合图；现在学习的是第5页，共76页n 顶点、边、弧、弧头、弧尾顶点、边、弧、弧头、弧尾 图图中中的的数数据据元元素素vi称称为为顶点点(Vertex)；P(vi,vj)表表示示在在顶顶点点vi和和顶点顶点vj之间有一条直接连线。之间有一条直接连线。如如果果是是在在无无向向图图中中，则则称称这这条条连连线线为为边(edge)；边边用用顶顶点点的的无无序序偶偶对对(vi,vj)来来表表示示，称称顶顶点点vi和和顶顶点点vj互互为为邻接接点点，边边(vi,vj)依依附于顶点附于顶点vi与顶点与顶点vj。在在有有向向图图中中，用用有有序序偶偶对对表表示示从从顶顶点点vi出出发发向向顶顶点点vj的的边边，vi为为始始点点，vj为为终终点点。有有向向边边也也称称为为弧弧(arc)，vi为为弧弧尾尾(tail)或或初初始始点点，vj为为弧弧头(head)或或终端端点点,则则表表示示为为一一条条弧弧,而而表示表示vj为弧尾、为弧尾、vi为弧头的另一条弧为弧头的另一条弧。ViViVjVjViViVjVj无向图无向图有向图有向图现在学习的是第6页，共76页n端点和邻接点端点和邻接点在一个无向图中在一个无向图中,若存在一条边若存在一条边(vi,vj),则称则称vi和和vj为此边的为此边的两个端点两个端点,并称它们互为并称它们互为邻接点邻接点(adjacent).在一个有向图中在一个有向图中,若存在一条弧若存在一条弧,则称则称vi和和vj为此弧的为此弧的初始点和终端点初始点和终端点,称它们互为称它们互为邻接点邻接点，称，称vj为为vi得出边邻接点得出边邻接点,vi为为vj的入边邻接点的入边邻接点.G2G2G1G17 71 12 26 65 54 43 35 52 23 36 64 41 1现在学习的是第7页，共76页n 完全图、稠密图、稀疏图完全图、稠密图、稀疏图 无无向向完完全全图：在在一一个个无无向向图图中中，如如果果任任意意两两顶顶点点都都有有一一条条直直接接边边相相连连接接，则则称称该该图图为为无无向向完完全全图图。在在一一个个含含有有n个个顶顶点点的的无无向向完完全图中，有全图中，有n(n-1)/2条边。条边。有向完全有向完全图：在一个有向图中，如果任意两顶点之间都有方向互在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为为相反的两条弧相连接，则称该图为有向完全图有向完全图。在一个含有。在一个含有n个个顶点的有向完全图中，有顶点的有向完全图中，有n(n-1)条弧。条弧。稠稠密密图、稀稀疏疏图：若若一一个个图图接接近近完完全全图图，称称为为稠稠密密图图；称称边边数数很很少的图为少的图为稀疏图稀疏图。有向完全图有向完全图无向完全图无向完全图3 31 12 23 31 12 2现在学习的是第8页，共76页G2G2顶点顶点2入度：入度：1出度：出度：3顶点顶点4入度：入度：1出度：出度：0G1G1顶点顶点5的度：的度：3顶点顶点2的度：的度：47 71 12 26 65 54 43 35 52 23 36 64 41 1n 度、入度、出度度、入度、出度在图中，一个顶点依附的边或弧的数目，称为该顶点的在图中，一个顶点依附的边或弧的数目，称为该顶点的度度。在。在有向图中，以顶点有向图中，以顶点V为为起点起点的有向边数称为顶点的有向边数称为顶点V的的出度出度(Outdegree)，以顶点，以顶点V为为终点终点的有向边数称为顶点的有向边数称为顶点V的的入度入度(Indegree)，有向图中某个顶点的，有向图中某个顶点的入度和出度之和入度和出度之和称为称为该顶点的度该顶点的度。现在学习的是第9页，共76页设图设图G的顶点数为的顶点数为n，边或弧数为，边或弧数为e。则图中。则图中所有顶点的度数和所有顶点的度数和=2*e。（每条边对图的（每条边对图的所有顶点的度数都所有顶点的度数都“贡献贡献”2度）度）G2G2G1G17 71 12 26 65 54 43 35 52 23 36 64 41 1ri为入度，为入度，ci为出度为出度在在有向图有向图中，所有顶点的入度之和等于出度中，所有顶点的入度之和等于出度之和：之和：现在学习的是第10页，共76页n 边的权、网边的权、网与边有关的数据信息称为与边有关的数据信息称为权（weight），权可以代），权可以代表一个顶点到另一个顶点的距离，耗费等。边上带权表一个顶点到另一个顶点的距离，耗费等。边上带权的图称为的图称为网网（network）。）。1 12 25 54 43 3176324 58B BC CA A21435无向带权图和有向带权图无向带权图和有向带权图(a)无向网无向网(b)有向网有向网现在学习的是第11页，共76页n 路径、路径长度路径、路径长度 在无向图中，若存在一个顶点序列在无向图中，若存在一个顶点序列vp,vi1,vi2,vim,vq使得使得(vp,vi1),(),(vi1,vi2),),(,(vim,vq)都属于都属于E(G)E(G)，则称其为顶点，则称其为顶点vp到到顶点顶点vq之间的一条之间的一条路径路径（PathPath）。路径上）。路径上边的数目边的数目称为称为路径路径长度度（Path lengthPath length）。在有向图中，路径也是有向的，它是由）。在有向图中，路径也是有向的，它是由若干条弧组成。若干条弧组成。如图所示的无向图如图所示的无向图G1G1中，中，v0v3v2v4v0v3v2v4与与v0v1v4v0v1v4是是从顶点从顶点v0 v0 到顶点到顶点v4 v4 的两条路径，路径长度分别为的两条路径，路径长度分别为3 3和和2 2。V0V0V4V4V3V3V1V1V2V2V0V0V1V1G1G1现在学习的是第12页，共76页n 回路、简单路径、简单回路回路、简单路径、简单回路 起点和终点相同的路径称为起点和终点相同的路径称为回路回路或者或者环（环（CycleCycle）。序。序列中顶点不重复出现的路径称为列中顶点不重复出现的路径称为简单路径路径。除第一个顶。除第一个顶点与最后一个顶点之外，其他顶点不重复出现的回路称为点与最后一个顶点之外，其他顶点不重复出现的回路称为简单回路回路。在图在图G1G1中，中，V0,V1,V2,V3 V0,V1,V2,V3 是简单路径；是简单路径；V0,V1,V2,V4,V1V0,V1,V2,V4,V1不是简单路径；在图不是简单路径；在图G2G2中，中，V0,V2,V3,V0V0,V2,V3,V0是简单回路；是简单回路；V0V0V4V4V3V3V1V1V2V2V0V0V2V2V3V3V1V1无向图无向图G1有向图有向图G2现在学习的是第13页，共76页n 子图子图 若有两个图若有两个图G和和G，G=(V,E)，G=(V,E)，满足满足如下条件：如下条件：V V，E E，即，即V为为V的子集，的子集，E为为E的的子集，称图子集，称图G为图为图G的的子子图（Subgraph）。例：例：(b)是是(a)的子图，的子图，(c)图不是（图不是（a）的子图。）的子图。V0V0V4V4V3V3V1V1V2V2V0V0V4V4V3V3V1V1V2V2V0V0V3V3V1V1(a)(a)(b)(b)(c)(c)现在学习的是第14页，共76页n 连通图、连通分量连通图、连通分量 在无向图中，在无向图中，如果从一个顶点如果从一个顶点vi到另一个顶点到另一个顶点vj（ij）有路径有路径，则称顶点，则称顶点vi和和vj是是连通的通的。若图中任意两个顶点都是连通。若图中任意两个顶点都是连通的，则称此无向图为的，则称此无向图为连通通图（Connected GraphConnected Graph），否则称为），否则称为非非连通通图。无向图中，无向图中，极大极大的连通子图为该图的的连通子图为该图的连通分量通分量。显然，。显然，任任何连通图的连通分量只有一个何连通图的连通分量只有一个，即它本身，即它本身，而非连通图有多个连而非连通图有多个连通分量。通分量。V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4连通图连通图G1非连通图非连通图G2G2的两个的两个连通分量连通分量现在学习的是第15页，共76页n 强连通图、强连通分量强连通图、强连通分量 对于对于有向图有向图来说，若图中任意一对顶点来说，若图中任意一对顶点vi和和vj（ij）均有从）均有从一个顶点一个顶点vi到另一个顶点到另一个顶点vj的路径，也有从的路径，也有从vj到到vi的路径，则称该的路径，则称该有向图是有向图是强连通通图。有向图的极大强连通子图称为。有向图的极大强连通子图称为强连通分量通分量。显然，显然，任何强连通图的强连通分量只有一个，即它本身，而非任何强连通图的强连通分量只有一个，即它本身，而非强连通图有多个强连通分量强连通图有多个强连通分量。V0V0 V1V1 V2V2 V3V3 V0V0 V1V1 V2V2 V3V3强连通图强连通图G1非强连通图非强连通图G2 V1V1 V0V0 V2V2 V3V3G2的两个强连的两个强连通分量通分量现在学习的是第16页，共76页n 生成树、生成森林生成树、生成森林 所谓连通图所谓连通图G的的生成树生成树，是，是G的包含其的包含其全部全部n个顶点，且以最少个顶点，且以最少的边数使其连通的边数使其连通的一个的一个极小连通子图极小连通子图。它必定包含且仅包含它必定包含且仅包含G的的n-1条边。条边。极小连通子图意思是：该子图是极小连通子图意思是：该子图是G的连通子图，在该子图的连通子图，在该子图中删除任何一条边，子图不再连通。中删除任何一条边，子图不再连通。非连通图的生成树则组成一个非连通图的生成树则组成一个生成森林生成森林。若图中有若图中有n个顶点，个顶点，m个连通分量，则生成森林中有个连通分量，则生成森林中有n-m条边条边。V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2连通图连通图G1G1的生成树的生成树现在学习的是第17页，共76页G2G2G1G15 54 42 26 63 31 11 17 73 32 24 46 65 5路径：路径：1，2，3，5，6，3路径长度：路径长度：5简单路径：简单路径：1，2，3，5回路：回路：1，2，3，5，6，3，1简单回路：简单回路：3，5，6，3路径：路径：1，2，5，7，6，5，2，3路径长度：路径长度：7简单路径：简单路径：1，2，5，7，6回路：回路：1，2，5，7，6，5，2，1简单回路：简单回路：1，2，3，1现在学习的是第18页，共76页3、图的运算、图的运算和其它结构一样，图的基本操作也是和其它结构一样，图的基本操作也是查找、查找、插入和删除插入和删除。但在。但在操作中常常需要指出操作中常常需要指出顶点在图中位置顶点在图中位置。从图的逻辑结构的定义来看，图中的从图的逻辑结构的定义来看，图中的顶点之间不存在全序的顶点之间不存在全序的关系关系（即无法将图中顶点排列成一个线性序列），任何一个顶点都可被（即无法将图中顶点排列成一个线性序列），任何一个顶点都可被看成是第一个；另一方面，看成是第一个；另一方面，任一顶点的邻接点之间也不存在次序关系任一顶点的邻接点之间也不存在次序关系。但为了操作方便，我们需要将图中顶点按任意的顺序排列起来（这个但为了操作方便，我们需要将图中顶点按任意的顺序排列起来（这个排列和关系排列和关系E无关）。无关）。由此，所谓由此，所谓顶点在图中的位置顶点在图中的位置指的是该顶点在这个指的是该顶点在这个人为人为的随意排的随意排列中的位置（或序号）。同理可对某个顶点的所有邻接点进行排队，列中的位置（或序号）。同理可对某个顶点的所有邻接点进行排队，在这个排队中自然形成了第在这个排队中自然形成了第1个或第个或第k个邻接点。若某个顶点的邻接个邻接点。若某个顶点的邻接点的个数大于点的个数大于k则称第则称第k1个邻接点为第个邻接点为第k个邻接点的下一个邻接个邻接点的下一个邻接点，而最后一个邻接点的下一个邻接点为点，而最后一个邻接点的下一个邻接点为“空空”。现在学习的是第19页，共76页图的基本操作 1、CreatGraph(&G,V,E)按按V和和E的定义构造图的定义构造图G。2、DestroyGraph(&G)销毁图销毁图G。3、LocateVex(G,u)若若G中存在顶点中存在顶点u，返回其在图中位置，否则返回，返回其在图中位置，否则返回-1。4、GetVex(G,v)在图中找到顶点在图中找到顶点v，并返回顶点，并返回顶点v的相关信息，否则返回空。的相关信息，否则返回空。5、FirstAdjVex(G,v)返回图中顶点返回图中顶点v的第一个邻接顶点，若没有，返回空。的第一个邻接顶点，若没有，返回空。6、NextAdjVex(G，v，w)返回返回v的相对于的相对于w的下一个邻接顶点，若的下一个邻接顶点，若w是是v的最后一个邻接的最后一个邻接点，则返回空。点，则返回空。现在学习的是第20页，共76页7、AddVex(&G,v)在图在图G中增添新顶点中增添新顶点v。8、DelVex(&G,v)在图在图G中，删除顶点中，删除顶点v及所有和其相关的边或弧。及所有和其相关的边或弧。9、AddArc(&G,v,w)在图在图G中增添一条从顶点中增添一条从顶点v到顶点到顶点w的边或弧。的边或弧。10、DelArc(&G,v,w)在图中删除一条从顶点在图中删除一条从顶点v到顶点到顶点w的边或弧。的边或弧。11、DFS(G,v)在图在图G中，从顶点中，从顶点v出发深度优先遍历图。出发深度优先遍历图。12、BFS(G,v)在图在图G中，从顶点中，从顶点v出发广度优先遍历图。出发广度优先遍历图。图的基本操作 现在学习的是第21页，共76页7.2 7.2 7.2 7.2 图的存储结构图的存储结构图的存储结构图的存储结构 图是一种结构复杂的数据结构，表现在不仅各个顶图是一种结构复杂的数据结构，表现在不仅各个顶点的度可以千差万别，而且顶点之间的逻辑关系也错综点的度可以千差万别，而且顶点之间的逻辑关系也错综复杂。从图的定义可知，一个图的信息包括两部分，即复杂。从图的定义可知，一个图的信息包括两部分，即图中顶点的信息以及描述顶点之间的关系（边或者弧）图中顶点的信息以及描述顶点之间的关系（边或者弧）的信息的信息。因此无论采用什么方法建立图的存储结构，都。因此无论采用什么方法建立图的存储结构，都要完整、准确地反映这两方面的信息。要完整、准确地反映这两方面的信息。图通常有图通常有邻接矩阵、邻接表、邻接多重表和十字邻接矩阵、邻接表、邻接多重表和十字链表链表等表示方法。等表示方法。现在学习的是第22页，共76页7.2.1 7.2.1 邻接矩阵邻接矩阵 定义：定义：在邻接矩阵表示中，除了在邻接矩阵表示中，除了用用一维数组一维数组存放顶点本身信息存放顶点本身信息外，还用外，还用一个矩阵一个矩阵表示各个顶点之间的邻接关系。表示各个顶点之间的邻接关系。这个这个矩阵矩阵称为称为邻邻接矩阵接矩阵。假设图假设图G(V,E)有有n个确定的顶点，即个确定的顶点，即Vv0,v1,vn-1，则表示则表示G中各顶点相邻关系为一个中各顶点相邻关系为一个nn的矩阵，矩阵的元素为的矩阵，矩阵的元素为：1若（若（i,ji,j）E(G)E(G)或或i,ji,jE(G)E(G)0 0其它情形其它情形 若若G是带权图，则邻接矩阵定义为：是带权图，则邻接矩阵定义为：wij若（若（i,ji,j）E(G)E(G)或或i,ji,jE(G)E(G)0 0 所在对角线上元素所在对角线上元素其它情形其它情形其中，其中，wij表示边上的表示边上的权值权值；表示大于所有边上权值的数。表示大于所有边上权值的数。Aij=Aij=现在学习的是第23页，共76页例V0V0V1V1V2V2V3V30 01 11 10 00 00 00 00 00 00 00 01 11 10 00 00 0V0V0V4V4V3V3V1V1V2V20 01 10 01 10 01 10 01 10 01 10 01 10 01 11 11 10 01 10 00 00 01 11 10 00 0V0V0V2V2V1V1V3V3V4V485679340 03 36 65 53 30 04 4 6 64 40 08 89 95 58 80 07 7 9 97 70 0A=B=C=无向图无向图有向图有向图无向网无向网现在学习的是第24页，共76页从从无向图无向图(网网)的邻接矩阵可以得出如下的邻接矩阵可以得出如下结论结论：矩阵是对称的；可压缩存储（上（下）三角）矩阵是对称的；可压缩存储（上（下）三角）;第第i行或第行或第i列列非非0元元(非非元元)的个数为顶点的个数为顶点i的的度度；矩阵中矩阵中非非0元元(非非元元)的个数的的个数的一半一半为图中为图中边的数目边的数目；很很容容易易判判断断顶顶点点i和和顶顶点点j之之间间是是否否有有边边相相连连(看看矩矩阵阵中中i行行j列列值值是否为是否为非非0元元(非非元元)。从从有向图有向图(网网)的邻接矩阵可以得出如下的邻接矩阵可以得出如下结论结论：矩阵不一定是对称的；矩阵不一定是对称的；第第i行行中中非非0元元(非非元元)的个数为顶点的个数为顶点i的的出度出度；第第i列列中中非非0元元(非非元元)的个数为顶点的个数为顶点i的的入度入度；矩阵中矩阵中非非0元元(非非元元)的个数为图中的个数为图中弧的数目弧的数目；很容易判断顶点很容易判断顶点i和顶点和顶点j是否有弧相连。是否有弧相连。现在学习的是第25页，共76页容易实现图的操作，如：求某顶点的度、判断顶点容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。之间是否有边（弧）、找顶点的邻接点等等。n个顶点需要个顶点需要n*nn*n个单元存储边个单元存储边(弧弧);空间复杂度为空间复杂度为O(n2)。对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。邻接矩阵法邻接矩阵法优点优点：邻接矩阵法邻接矩阵法缺点缺点：现在学习的是第26页，共76页图的邻接矩阵数据类型描述：图的邻接矩阵数据类型描述：在在用用邻邻接接矩矩阵阵存存储储图图时时，除除了了用用一一个个二二维维数数组组存存储储用用于于表表示示顶顶点点间间相相邻邻关关系系的的邻邻接接矩矩阵阵外外，还还需需用用一一个个一一维维数数组组来来存存储储顶顶点点信信息息，另另外外还还有有图图的的顶顶点点数数和和边边数数。故故可将其形式描述如下：可将其形式描述如下：#defineMaxVerNum20typedefstructVertexTypevexsMaxVerNum;intedgesMaxVerNumMaxVerNum;intn,e;MGragh;/*最大顶点个数最大顶点个数*/*顶点向量顶点向量*/*邻接矩阵，即边表邻接矩阵，即边表*/*顶点数和边数顶点数和边数*/*以邻接矩阵存储的图类型以邻接矩阵存储的图类型*/现在学习的是第27页，共76页邻接矩阵建立：邻接矩阵建立：voidCreatGraph(MGraph&G)inti,j,k;scanf(“%d%d”,&G.n,&G.e);/cinG.nG.e;for(i=0;iG.n;i+)scanf(“%c”,&G.vexsi);for(i=0;iG.n;i+)for(j=0;jG.n;j+)G.edgesij=0;for(k=0;kG-nG-e;for(i=0;in;i+)cinG-adjListi.vertex;G-adjListi.firstedge=NULL;for(k=0;ke;k+)cinij;p=newEdgeNode;p-adjvertex=j;p-next=G-adjListi.firstedge;/头插法头插法G-adjListi.firstedge=p;现在学习的是第33页，共76页二、有向图邻接表二、有向图邻接表在在有有向向图图中中，第第i个个链链表表中中的的结结点点个个数数是是顶顶点点vi的的出出度度。要要求求某某个个结结点点的的入入度度，必必须须遍遍历历整整个个邻邻接接表表。在在所所有有链链表表中中其其邻邻接接点点域域的的值值为为i的结点的个数是顶点的结点的个数是顶点vi的入度。的入度。n个顶点，个顶点，e条弧的有向图，需条弧的有向图，需n个表头结点，个表头结点，e个表结点。个表结点。V0V0 V1V1 V2V2 V3V30 0V0V01 1V1V1 2 2V2V23 3V3V31 12 23 30 0用链表存储同一顶点为用链表存储同一顶点为起点起点的弧的弧现在学习的是第34页，共76页三、有向图的逆邻接表三、有向图的逆邻接表为为了了便便于于确确定定顶顶点点的的入入度度或或以以顶顶点点vi为为头头的的弧弧，可可以以建建立立一一个个有有向向图图的的逆逆邻邻接接表表，即即对对每每个个顶顶点点vi建建立立一一个个以以vi为为弧弧头头的的结结点点组组成的链表。成的链表。V0V0 V1V1 V2V2 V3V30 0V0V01 1V1V1 2 2V2V23 3V3V3用链表存储同一顶点为用链表存储同一顶点为起点起点的弧的弧3 30 00 02 2现在学习的是第35页，共76页1从从无向图无向图的邻接表可以得到如下结论的邻接表可以得到如下结论（1）第）第i个链表中结点数目为顶点个链表中结点数目为顶点i的度；的度；（2）所有）所有链表链表中结点数目的一半为图中边数；中结点数目的一半为图中边数；（3）占用的存储单元数目为）占用的存储单元数目为n+2e。2从从有向图有向图的邻接表可以得到如下结论的邻接表可以得到如下结论（1）第）第i个链表中结点数目为顶点个链表中结点数目为顶点i的出度；的出度；（2）所有）所有链表链表中结点数目为图中弧数；中结点数目为图中弧数；（3）占用的存储单元数目为）占用的存储单元数目为n+e。四、四、结论结论现在学习的是第36页，共76页从有向图的邻接表可知，从有向图的邻接表可知，不能求出顶点的入度不能求出顶点的入度。为此，。为此，我们可以另外建立有向图的逆邻接表，以便求出每一个顶我们可以另外建立有向图的逆邻接表，以便求出每一个顶点的入度。点的入度。有向图的逆邻接表有向图的逆邻接表与邻接表类似，只是它是与邻接表类似，只是它是从入度考虑结点，而不是从出度考虑结点。从入度考虑结点，而不是从出度考虑结点。3.建立的邻接表建立的邻接表不是惟一不是惟一的，与键盘输入边的顺序有关，的，与键盘输入边的顺序有关，输入的边的顺序不同，则得到的链表也不同。输入的边的顺序不同，则得到的链表也不同。现在学习的是第37页，共76页例：已知某网的例：已知某网的邻接（出接（出边）表，）表，请画出画出该网网络。8064125当邻接表的存储当邻接表的存储结构形成后，图结构形成后，图便唯一确定！便唯一确定！现在学习的是第38页，共76页邻接表的邻接表的缺点：缺点：邻接表的邻接表的优点：优点：空间效率高；空间效率高；容易寻找顶点的邻接点；容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩索两结点对应的单链表，没有邻接矩阵方便。阵方便。现在学习的是第39页，共76页讨论：讨论：邻接表与邻接矩阵有什么异同之处？邻接表与邻接矩阵有什么异同之处？1.联系：联系：邻接表中每个链表对应于邻接矩阵中的一行，链邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于该行中非零元素的个数。表中结点个数等于该行中非零元素的个数。2.区别：区别：对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。编号一致），但邻接表不唯一（链接次序与顶点编号无关）。邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度而邻接表的空间复杂度为为O(n+e)。3.用途：用途：邻接矩阵邻接矩阵多用于多用于稠密图稠密图的存储（的存储（e接近接近n(n-1)/2)；而而邻接表邻接表多用于多用于稀疏图稀疏图的存储（的存储（evexnum,&G-arcnum);for(i=0;ivexnum;i+)scanf(&G-xlisti.vertex);G-xlisti.firstin=NULL;G-xlisti.firstout=NULL;for(k=0;ktailvex=i;p-headvex=j;p-tlink=G-xlisti.firstout;G-xlisti.firstout=p;p-hlink=G-xlistj.firstin;G-xlistj.firstin=p;/*构造表头数组构造表头数组*/*输入各弧并构造十字链表输入各弧并构造十字链表*/*确定确定v1和和v2在在G中位置中位置*/*结点赋值结点赋值*/*出弧的插入出弧的插入*/*入弧的插入入弧的插入*/现在学习的是第44页，共76页7.2.4 7.2.4 邻接多重表（无向图）邻接多重表是无向图的另一种链式存储结构。邻接多重表是无向图的另一种链式存储结构。每一个顶点有一个顶点结点，顶点结点结构为：每一个顶点有一个顶点结点，顶点结点结构为：图的每一条边有一个边结点，边结点的结构为：图的每一条边有一个边结点，边结点的结构为：其中：其中：vertex存放顶点的信息。存放顶点的信息。firstedge指向第一条依附于该顶点的边结点。指向第一条依附于该顶点的边结点。mark为标记域，用以标记该条边是否被处理过为标记域，用以标记该条边是否被处理过。ivex和和jvex为该边所依附的两个顶点。为该边所依附的两个顶点。ilink指向下一条依附于顶点指向下一条依附于顶点ivex的边。的边。jlink指向下一条依附于顶点指向下一条依附于顶点jvex的边。的边。vertex firstedgeivex ilink jvex jlinkmark现在学习的是第45页，共76页图的邻接多重表数据类型描述：图的邻接多重表数据类型描述：#defineMaxVerNum20typedefenumunvisited,visitedVisitIf;typedefstructEdgeNodeVisitIfmark;intivex,jvex;structEdgeNode*ilink,*jlink;EdgeNode;typedefstructVexNodeVertexTypevertex;EdgeNode*fistedge;VexNode;typedefstructVexNodeadjmulistMaxVerNum;intvexnum,edgenum;AMLGraph;/*访问标记访问标记*/*该边依附的两个顶点的位置该边依附的两个顶点的位置*/*指向依附这两个顶点的下一条边指向依附这两个顶点的下一条边*/*指向第一条依附该顶点的边指向第一条依附该顶点的边*/*无向图的当前顶点数和边数无向图的当前顶点数和边数*/*边结点的结构类型边结点的结构类型*/*顶点的结构类型顶点的结构类型*/*图的结构类型图的结构类型*/现在学习的是第46页，共76页1234134255121434323552 1 15 54 42 23 3例特点：特点：特点：特点：顶点结点数为顶点结点数为顶点结点数为顶点结点数为n n，边结点数为，边结点数为，边结点数为，边结点数为e e；对需要得到边的两个顶点的一类操作很方便对需要得到边的两个顶点的一类操作很方便对需要得到边的两个顶点的一类操作很方便对需要得到边的两个顶点的一类操作很方便现在学习的是第47页，共76页在不同的存储结构下，实现各种操作的效率可在不同的存储结构下，实现各种操作的效率可能是不同的。所以在求解实际问题时，要根据求解能是不同的。所以在求解实际问题时，要根据求解问题所需操作，选择合适的存储结构。问题所需操作，选择合适的存储结构。分析分析:在图的在图的链接存储链接存储(邻接表、逆邻接表、十字链表和邻接表、逆邻接表、十字链表和邻接多重表邻接多重表)中，中，表头向量需要占用表头向量需要占用n个存储单元个存储单元，所有所有边结点需要占用边结点需要占用2e或或e存储单元存储单元，所以最多需要，所以最多需要（n+2e）个存储单元，稀疏图采用这种存储方式可节个存储单元，稀疏图采用这种存储方式可节省存储空间。省存储空间。现在学习的是第48页，共76页7.3 7.3 图的遍历图的遍历 和树的遍历类似，图的遍历也是从某个顶点出发，沿着和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中所有顶点各作一次访问。某条搜索路径对图中所有顶点各作一次访问。图访问的四个难点：图访问的四个难点：首结点首结点、非连通图非连通图、回路、多个相连顶点回路、多个相连顶点我们可以设置一个全局型标志数组我们可以设置一个全局型标志数组visited来标志某来标志某个顶点是否被访过，未访问的值为个顶点是否被访过，未访问的值为0，访问过的值为，访问过的值为1。根据搜索路径的方向不同，图的遍历有两种方法：根据搜索路径的方向不同，图的遍历有两种方法：深度优先搜索遍历和广度优先搜索遍历。深度优先搜索遍历和广度优先搜索遍历。现在学习的是第49页，共76页深度优先搜索遍历类似于树的先序遍历。深度优先搜索遍历类似于树的先序遍历。假定给定图假定给定图G的初态是所有顶点均未被访问过，在的初态是所有顶点均未被访问过，在G中中任选任选一个顶点一个顶点i作为遍历的初始点，访问此顶点，然后作为遍历的初始点，访问此顶点，然后依次从依次从i的未被访问的邻接点出发的未被访问的邻接点出发深度优先遍历深度优先遍历图，直图，直到图中所有和到图中所有和i有路径相通的顶点都被访问到；有路径相通的顶点都被访问到；若此时尚有顶点未被访问，则另选图中一个未曾被访若此时尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。被访问到为止。7.3.1 7.3.1 深度优先搜索深度优先搜索深度优先搜索是一种深度优先搜索是一种递归递归的过程。的过程。现在学习的是第50页，共76页深度优先搜索遍历基本思想如下：深度优先搜索遍历基本思想如下：1)1)首首先先访访问问顶顶点点i，并并将将其其访访问问标标记记置置为为访访问问过过，即即visitedi=1；2)2)然后搜索与顶点然后搜索与顶点i有边相连的下一个顶点有边相连的下一个顶点j，若若j未未被被访访问问过过，则则访访问问它它，并并将将j的的访访问问标标记记置置为为访访问问过，过，visitedj=1，然后从，然后从j开始重复此过程，开始重复此过程，若若j已访问，再访问与已访问，再访问与i有边相连的其它顶点有边相连的其它顶点；1)1)若若与与i有有边边相相连连的的顶顶点点都都被被访访问问过过，则则退退回回到到前前一一个个访访问问顶点并重复刚才过程，直到图中所有顶点都被访问完止。顶点并重复刚才过程，直到图中所有顶点都被访问完止。深度优先搜索是一种深度优先搜索是一种递归递归的过程。的过程。现在学习的是第51页，共76页深度优先遍历深度优先遍历从图中某顶点从图中某顶点v v出发：出发：V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V11)1)访问顶点访问顶点v v；2)2)依次从依次从v v的的未被访问的邻接点未被访问的邻接点出发，对图进行深度优先遍历；出发，对图进行深度优先遍历；先序遍历先序遍历若树非空若树非空1)1)访问根结点；访问根结点；2)2)按照从左到右的顺序先序遍历按照从左到右的顺序先序遍历根结点的每一棵子树。根结点的每一棵子树。如果将图中顶点的如果将图中顶点的邻接点看作树中结点邻接点看作树中结点的孩子，图的深度优的孩子，图的深度优先遍历与树的先序遍先遍历与树的先序遍历是否很类似？历是否很类似？比较：比较：现在学习的是第52页，共76页深度遍深度遍历：V1V2V4V8V5V6V3V7深度遍历：深度遍历：V1V1 V2 V2 V4 V4 V8 V8 V3 V3 V6 V6 V7 V7 V5V5V6V6V1V1V2V2V4V4V5V5V3V3V7V7V8V8V1V1V2V2V4V4V5V5V3V3V7V7V6V6V8V8由于没有规定访问邻接点的顺序由于没有规定访问邻接点的顺序,深度优先序列不是深度优先序列不是唯一的唯一的现在学习的是第53页，共76页若若图图是是连连通通的的或或强强连连通通的的，则则从从图图中中某某一一个个顶顶点点出出发发可可以以访访问问到到图图中中所所有有顶顶点点，否否则则只只能能访访问问到到一一部部分分顶顶点点，再再从从未未被被访访问问的的顶顶点点中中选选一一个个顶顶点点出出发发访访问问未被访问的顶点。未被访