数据结构图论部分课件

Data StructureData Structure第七章第七章 图图100865108/3/20241Data Structure第七章 图100865107Data StructureData Structureq学习目标学习目标v领会领会图的类型定义图的类型定义。v熟悉熟悉图的各种存储结构图的各种存储结构及其构造算法，了解各种存储结构的特点及其构造算法，了解各种存储结构的特点及其及其选用原则选用原则。v熟练掌握图的两种熟练掌握图的两种遍历遍历算法。算法。v理解各种图的理解各种图的应用问题的算法应用问题的算法。q重点和难点重点和难点v重点：图的各种应用问题的算法都比较经典，注意重点：图的各种应用问题的算法都比较经典，注意理解各种图的理解各种图的算法及其应用场合算法及其应用场合。8/3/20242学习目标7/29/20232Data StructureData Structureq知识点知识点v图的类型定义图的类型定义v图的存储表示图的存储表示v图的深度优先搜索遍历和广度优先搜索遍历图的深度优先搜索遍历和广度优先搜索遍历v无向网的最小生成树无向网的最小生成树v拓扑排序拓扑排序v关键路径关键路径v最短路径最短路径8/3/20243知识点7/29/20233Data StructureData Structure欧拉欧拉17071707年出生在瑞士的巴塞尔城，年出生在瑞士的巴塞尔城，1919岁开始发岁开始发表论文，直到表论文，直到7676岁。几乎每一个数学领域都可以岁。几乎每一个数学领域都可以看到欧拉的名字，从初等几何的欧拉线，多面体看到欧拉的名字，从初等几何的欧拉线，多面体的欧拉定理，立体解析几何的欧拉变换公式，四的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法到数论中的欧拉函数，微分方次方程的欧拉解法到数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数，变分学的欧程的欧拉方程，级数论的欧拉常数，变分学的欧拉方程，复变函数的欧拉公式等等。据统计他那拉方程，复变函数的欧拉公式等等。据统计他那不倦的一生，共写下了不倦的一生，共写下了886886本书籍和论文，其中本书籍和论文，其中分析、代数、数论占分析、代数、数论占40%40%，几何占，几何占18%18%，物理和力，物理和力学占学占28%28%，天文学占，天文学占11%11%，弹道学、航海学、建筑，弹道学、航海学、建筑学等占学等占3%3%。1733 1733年，年仅年，年仅2626岁的欧拉担任了彼岁的欧拉担任了彼得堡科学院数学教授。得堡科学院数学教授。17411741年到柏林担任科学院年到柏林担任科学院物理数学所所长，直到物理数学所所长，直到17661766年，重回彼得堡，没年，重回彼得堡，没有多久，完全失明。欧拉在数学上的建树很多，有多久，完全失明。欧拉在数学上的建树很多，对著名的哥尼斯堡七桥问题的解答开创了图论的对著名的哥尼斯堡七桥问题的解答开创了图论的研究。研究。图论图论欧拉欧拉8/3/20244欧拉1707年出生在瑞士的巴塞尔城，19岁开始发表论文，直到Data StructureData Structure能否从某个地方出发，穿过所有的桥仅一次能否从某个地方出发，穿过所有的桥仅一次后再回到出发点？后再回到出发点？哥尼斯堡七桥问题哥尼斯堡七桥问题 8/3/20245能否从某个地方出发，穿过所有的桥仅一次后再回到出发点？哥尼斯Data StructureData StructureCADB七桥问题的图模型欧拉回路的判定规则：欧拉回路的判定规则：1.如果通奇数桥的地方多于如果通奇数桥的地方多于两个，则不存在欧拉回路；两个，则不存在欧拉回路；2.如果只有两个地方通奇数如果只有两个地方通奇数桥，可以从这两个地方之一桥，可以从这两个地方之一出发，找到欧拉回路；出发，找到欧拉回路；3.如果没有一个地方是通奇如果没有一个地方是通奇数桥的，则无论从哪里出发，数桥的，则无论从哪里出发，都能找到欧拉回路。都能找到欧拉回路。8/3/20246CADB七桥问题的图模型欧拉回路的判定规则：7/29/202Data StructureData Structure图的定义图的定义图的定义图的定义图是由图是由顶点顶点的的有穷非空有穷非空集合和顶点之间集合和顶点之间边边的集合组的集合组成，通常表示为：成，通常表示为：G=(V，E)其中：其中：G表示一个图，表示一个图，V是图是图G中顶点的集合，中顶点的集合，E是是图图G中顶点之间边的集合。中顶点之间边的集合。在线性表中，元素个数可以为零，称为空表；在线性表中，元素个数可以为零，称为空表；在树中，结点个数可以为零，称为空树；在树中，结点个数可以为零，称为空树；在图中，顶点个数不能为零，但可以没有边。在图中，顶点个数不能为零，但可以没有边。7.1 7.1 7.1 7.1 图的定义和术语图的定义和术语图的定义和术语图的定义和术语8/3/20247图的定义图是由顶点的有穷非空集合和顶点之间边的集合组成，通常Data StructureData Structureq线性表线性表v每个数据元素只有一个直接前驱和一个直接后继。每个数据元素只有一个直接前驱和一个直接后继。q树形结构树形结构v每个数据元素只有一个直接前驱，但可能有多个直接后继。每个数据元素只有一个直接前驱，但可能有多个直接后继。q图形结构图形结构v每个数据元素可能有多个直接前驱和多个直接后继。每个数据元素可能有多个直接前驱和多个直接后继。图是比线性表和树复杂的数据结构，广泛应用于语图是比线性表和树复杂的数据结构，广泛应用于语言学、逻辑学、物理、化学等领域。言学、逻辑学、物理、化学等领域。8/3/20248线性表 图是比线性表和树复杂的数据结构，广泛应用于语言Data StructureData Structure如如果果图图的的任任意意两两个个顶顶点点之之间间的的边边都都是是无向边，则称该图为无向边，则称该图为无向图无向图。若顶点若顶点vi和和vj之间的边没有方向，则之间的边没有方向，则称这条边为称这条边为无向边无向边，表示为，表示为(vi,vj)。若从顶点若从顶点vi到到vj的边有方向，则称这的边有方向，则称这条边为条边为有向边有向边，表示为，表示为。如如果果图图的的任任意意两两个个顶顶点点之之间间的的边边都都是是有向边，则称该图为有向边，则称该图为有向图有向图。V1V2V3V4V5V1V2V3V4图的基本术语图的基本术语8/3/20249如果图的任意两个顶点之间的边都是无向边，则称该图为无向图。若Data StructureData Structure简单图：简单图：在图中，若不存在顶点到其自身的边，且同在图中，若不存在顶点到其自身的边，且同一条边不重复出现一条边不重复出现。V3V4V5V1V2V3V4V5V1V2非简单图非简单图 非简单图非简单图 简单图简单图V1V2V3V4V5v 数据结构中讨论的都是简单图。数据结构中讨论的都是简单图。8/3/202410简单图：在图中，若不存在顶点到其自身的边，且同一条边不重复出Data StructureData Structure图的基本术语图的基本术语邻接、依附邻接、依附无无向向图图中中，对对于于任任意意两两个个顶顶点点vi和和顶顶点点vj，若若存存在在边边(vi，vj)，则则称称顶顶点点vi和和顶顶点点vj互互为为邻邻接接点点，同同时时称称边边(vi，vj)依附于顶点依附于顶点vi和顶点和顶点vj。V1V2V3V4V5V1的邻接点：的邻接点：V2、V4V2的邻接点：的邻接点：V1、V3、V58/3/202411图的基本术语 邻接、依附V1V2V3V4V5V1的邻接点：Data StructureData Structure图的基本术语图的基本术语邻接、依附邻接、依附有有向向图图中中，对对于于任任意意两两个个顶顶点点vi和和顶顶点点vj，若若存存在在弧弧，则则称称顶顶点点vi邻邻接接到到顶顶点点vj，顶顶点点vj邻邻接接自自顶顶点点vi，同时称弧同时称弧依附于顶点依附于顶点vi和顶点和顶点vj。V1V2V3V4V1的邻接点：的邻接点：V2、V3V3的邻接点：的邻接点：V48/3/202412图的基本术语 邻接、依附V1V2V3V4V1的邻接点：V2Data StructureData Structure无无向向完完全全图图：在在无无向向图图中中，如如果果任任意意两两个个顶顶点点之之间间都都存在边，存在边，则称该图为无向完全图。则称该图为无向完全图。有有向向完完全全图图：在在有有向向图图中中，如如果果任任意意两两个个顶顶点点之之间间都都存在方向相反的两条弧，存在方向相反的两条弧，则称该图为有向完全图。则称该图为有向完全图。图的基本术语图的基本术语V1V2V3V1V2V3V48/3/202413无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该Data StructureData Structure含有含有n个顶点的无向完全图有个顶点的无向完全图有多少多少条边？条边？含有含有n个顶点的有向完全图有个顶点的有向完全图有多少多少条弧？条弧？含有含有n个顶点的无向完全图有个顶点的无向完全图有n(n-1)/2条边。条边。含有含有n个顶点的有向完全图有个顶点的有向完全图有n(n-1)条边。条边。V1V2V3V1V2V3V48/3/202414含有n个顶点的无向完全图有多少条边？含有n个顶点的无向完全图Data StructureData Structure稀疏图：稀疏图：称边数很少的图为稀疏图；称边数很少的图为稀疏图；稠密图：稠密图：称边数很多的图为稠密图。称边数很多的图为稠密图。顶顶点点的的度度：在在无无向向图图中中，顶顶点点v的的度度是是指指依依附附于于该该顶顶点的边数，通常记为点的边数，通常记为TD(v)。图的基本术语图的基本术语顶顶点点的的入入度度：在在有有向向图图中中，顶顶点点v的的入入度度是是指指以以该该顶顶点为弧头的弧的数目，点为弧头的弧的数目，记为记为ID(v)；顶顶点点的的出出度度：在在有有向向图图中中，顶顶点点v的的出出度度是是指指以以该该顶顶点为弧尾的弧的数目，记为点为弧尾的弧的数目，记为OD(v)。8/3/202415稀疏图：称边数很少的图为稀疏图；顶点的度：在无向图中，顶点vData StructureData StructureV1V2V3V4V5图的基本术语图的基本术语在在具具有有n个个顶顶点点、e条条边边的的无无向向图图G中中，各各顶顶点点的度之和与边数之和的关系？的度之和与边数之和的关系？=niievTD12)(8/3/202416V1V2V3V4V5图的基本术语 在具有n个顶点、e条边的无Data StructureData StructureV1V2V3V4图的基本术语图的基本术语在在具具有有n个个顶顶点点、e条条边边的的有有向向图图G中中，各各顶顶点点的的入入度度之之和和与与各各顶顶点点的的出出度度之之和和的的关关系系？与与边边数之和的关系？数之和的关系？evODvIDiiii=11)()(nn8/3/202417V1V2V3V4图的基本术语 在具有n个顶点、e条边的有向图Data StructureData Structure权：权：是指对边赋予的有意义的数值量。是指对边赋予的有意义的数值量。网：网：边上带权的图，也称网图。边上带权的图，也称网图。图的基本术语图的基本术语V1V2V3V427858/3/202418权：是指对边赋予的有意义的数值量。图的基本术语 V1V2V3Data StructureData Structure路路径径：在在无无向向图图G=(V,E)中中，从从顶顶点点vp到到顶顶点点vq之之间间的的路路径径是是一一个个顶顶点点序序列列(vp=vi0,vi1,vi2,vim=vq)，其其中中，(vij-1,vij)E（1jm）。若若G是是有有向向图图，则则路路径径也也是是有方向的，顶点序列满足有方向的，顶点序列满足E。图的基本术语图的基本术语V1V2V3V4V5v一般情况下，图中的路径不惟一。一般情况下，图中的路径不惟一。V1到到V4的路径：的路径：V1V4V1V2V3V4 V1V2V5V3V48/3/202419路径：在无向图G=(V,E)中，从顶点vp到顶点vq之间的Data StructureData Structure路径长度：路径长度：图的基本术语图的基本术语非带权图非带权图路径路径上边的上边的个数个数带权图带权图路径上路径上各边的各边的权之和权之和V1V2V3V4V5V1V4：长度为：长度为1V1V2V3V4：长度为：长度为3V1V2V5V3V4：长度为：长度为48/3/202420路径长度：图的基本术语 非带权图路径上边的个数V1V2VData StructureData Structure路径长度：路径长度：图的基本术语图的基本术语非带权图非带权图路径路径上边的上边的个数个数带权图带权图路径上路径上各边的各边的权之和权之和V1V4：长度为：长度为8V1V2V3V4：长度为：长度为7V1V2V5V3V4：长度为：长度为15V1V2V3V4V52563288/3/202421路径长度：图的基本术语 非带权图路径上边的个数V1 V4Data StructureData Structure回路（环）回路（环）：第一个顶点和最后一个顶点相同的路径。：第一个顶点和最后一个顶点相同的路径。简单路径：简单路径：序列中顶点不重复出现的路径。序列中顶点不重复出现的路径。简单回路（简单环）：简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。顶点不重复出现的回路。图的基本术语图的基本术语V1V2V3V4V5V1V2V3V48/3/202422回路（环）：第一个顶点和最后一个顶点相同的路径。图的基本术语Data StructureData Structure子子图图：若若图图G=（V，E），G=（V，E），如如果果V V且且E E，则称图，则称图G是是G的子图。的子图。图的基本术语图的基本术语V1V2V3V4V5V1V2V3V4V5V1V3V48/3/202423子图：若图G=（V，E），G=（V，E），如果VVData StructureData Structure连连通通图图：在在无无向向图图中中，如如果果从从一一个个顶顶点点vi到到另另一一个个顶顶点点vj(ij)有有路路径径，则则称称顶顶点点vi和和vj是是连连通通的的。如如果果图图中任意两个顶点都是连通的，则称该图是连通中任意两个顶点都是连通的，则称该图是连通图。图。连通分量：连通分量：非连通图的极大连通子图称为连通分量。非连通图的极大连通子图称为连通分量。图的基本术语图的基本术语如何求得一个非连通图的连通分量如何求得一个非连通图的连通分量?1.含有极大含有极大顶点顶点数；数；2.依附于这些顶点的所有依附于这些顶点的所有边边。8/3/202424连通图：在无向图中，如果从一个顶点vi到另一个顶点vj(iData StructureData Structure连通分量连通分量1V1V2V3V4V5V6V7V1V2V4V5V3V6V7连通分量连通分量2图的基本术语图的基本术语v连通分量是对无向图的一种划分。连通分量是对无向图的一种划分。8/3/202425连通分量1 V1V2V3V4V5V6Data StructureData Structure强强连连通通图图：在在有有向向图图中中，对对图图中中任任意意一一对对顶顶点点vi和和vj(ij)，若若从从顶顶点点vi到到顶顶点点vj和和从从顶顶点点vj到到顶顶点点vi均均有有路径，则称该有向图是强连通图。路径，则称该有向图是强连通图。强连通分量：强连通分量：非强连通图非强连通图的极大强连通子图。的极大强连通子图。图的基本术语图的基本术语如何求得一个非连通图的连通分量如何求得一个非连通图的连通分量?8/3/202426强连通图：在有向图中，对图中任意一对顶点vi和vj(ijData StructureData Structure图的基本术语图的基本术语V1V2V3V4强连通分量强连通分量1强连通分量强连通分量2V1V3V4V28/3/202427图的基本术语 V1V2V3V4强连通分量1 Data StructureData Structure生生成成树树：n个个顶顶点点的的连连通通图图G的的生生成成树树是是包包含含G中中全全部部顶点顶点的一个极小连通的一个极小连通子图。子图。生生成成森森林林：在在非非连连通通图图中中，由由每每个个连连通通分分量量都都可可以以得得到到一一棵棵生生成成树树，这这些些连连通通分分量量的的生生成成树树就就组组成成了了一一个个非连通图的非连通图的生成森林生成森林。如何理解极小连通子图如何理解极小连通子图?图的基本术语图的基本术语多多构成回路构成回路少少不连通不连通含有含有n-1条边条边8/3/202428生成树：n个顶点的连通图G的生成树是包含G中全部顶点的一个极Data StructureData StructureV1V2V3V4V5V6V7V1V2V3V4V5V6V7V1V2V3V4V5V1V2V3V4V5生成树生成树生成森林生成森林8/3/202429V1V2V3V4V5V6V7V1V2V3V4V5V6V7V1Data StructureData Structureq图的抽象数据类型定义如下：图的抽象数据类型定义如下：ADT ADT GraphGraph 数据对象数据对象V V ：V V是具有相同特性的数据元素的集合，称为顶是具有相同特性的数据元素的集合，称为顶 点集。点集。数据关系数据关系R R ：R=VRR=VRVRVR|v,wV|v,wV且且P(v,w)P(v,w)，表示从表示从v v到到w w的的 弧，谓词弧，谓词P(v,w)P(v,w)定义了弧定义了弧的意义的意义 或信息或信息 8/3/202430图的抽象数据类型定义如下：7/29/202330Data StructureData StructureG1=(G1=(V1V1,VR1VR1)V1=A,B,C,D,EV1=A,B,C,D,EVR1=,VR1=,G2=(G2=(V2V2,VR2VR2)V2=A,B,C,D,E,FV2=A,B,C,D,E,FVR2=(A,B),(A,E),(B,E),(C,D),VR2=(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F)(D,F),(B,F),(C,F)8/3/202431G1=(V1,VR1)G2=(V2,VR2)7/29/2Data StructureData StructureCreateGraph(&G,V,VR);CreateGraph(&G,V,VR);初始条件：初始条件：V V 是图的顶点集，是图的顶点集，VR VR 是图中弧的集合。是图中弧的集合。操作结果：按操作结果：按 V V 和和 VR VR 的定义的定义构造图构造图 G G。DestroyGraph(&G);DestroyGraph(&G);初始条件：图初始条件：图 G G 存在。存在。操作结果：操作结果：销毁图销毁图 G G。LocateVex(G,u);LocateVex(G,u);初始条件：图初始条件：图 G G 存在，存在，u u 和和 G G 中顶点有相同特征。中顶点有相同特征。操作结果：若操作结果：若 G G 中存在和中存在和 u u 相同的顶点，则相同的顶点，则返回该顶点返回该顶点 在图中位置在图中位置；否则返回其它信息。；否则返回其它信息。8/3/202432CreateGraph(&G,V,VR);初始条件：Data StructureData StructureGetVex(G,v);GetVex(G,v);初始条件：图初始条件：图 G G 存在，存在，v v 是是 G G 中某个顶点。中某个顶点。操作结果：返回操作结果：返回 v v 的值的值。FirstAdjVex(G,v);FirstAdjVex(G,v);初始条件：图初始条件：图 G G 存在，存在，v v 是是 G G 中某个顶点。中某个顶点。操作结果：操作结果：返回返回 v v 的第一个邻接点。的第一个邻接点。若该顶点在若该顶点在 G G 中没中没 有邻接点，则返回有邻接点，则返回“空空”。NextAdjVex(G,v,w);NextAdjVex(G,v,w);初始条件：图初始条件：图 G G 存在，存在，v v 是是 G G 中某个顶点，中某个顶点，w w 是是 v v 的的 邻接顶点。邻接顶点。操作结果：操作结果：返回返回 v v 的（相对于的（相对于 w w 的）下一个邻接点。的）下一个邻接点。若若 w w 是是 v v 的最后一个邻接点，则返回的最后一个邻接点，则返回“空空”。8/3/202433GetVex(G,v);初始条件：图 G 存在，v 是Data StructureData StructurePutVex(&G,v,value);PutVex(&G,v,value);初始条件：图初始条件：图 G G 存在，存在，v v 是是 G G 中某个顶点。中某个顶点。操作结果：操作结果：对对 v v 赋值赋值 value value。InsertVex(&G,v);InsertVex(&G,v);初始条件：图初始条件：图 G G 存在，存在，v v 和图中顶点有相同特征。和图中顶点有相同特征。操作结果：在图操作结果：在图 G G 中中增添新顶点增添新顶点 v v。DeleteVex(&G,v);DeleteVex(&G,v);初始条件：图初始条件：图 G G 存在，存在，v v 是是 G G 中某个顶点。中某个顶点。操作结果：操作结果：删除删除 G G 中顶点中顶点 v v 及其相关的弧及其相关的弧。8/3/202434PutVex(&G,v,value);初始条件：图 Data StructureData StructureInsertArc(&G,v,w);InsertArc(&G,v,w);初始条件：图初始条件：图 G G 存在，存在，v v 和和 w w 是是 G G 中两个顶点。中两个顶点。操作结果：在操作结果：在 G G 中中增添弧增添弧，若，若 G G 是是无向的，则还无向的，则还 增添对称弧增添对称弧。DeleteArc(&G,v,w);DeleteArc(&G,v,w);初始条件：图初始条件：图 G G 存在，存在，v v 和和 w w 是是 G G 中两个顶点。中两个顶点。操作结果：在操作结果：在 G G 中中删除弧删除弧，若若 G G 是是无向的，则还无向的，则还 删除对称弧删除对称弧。8/3/202435InsertArc(&G,v,w);初始条件：图 GData StructureData StructureDFSTraverse(G,Visit();DFSTraverse(G,Visit();初始条件：图初始条件：图 G G 存在，存在，Visit Visit 是顶点的应用函数。是顶点的应用函数。操作结果：对图操作结果：对图 G G 进行进行深度优先深度优先遍历。遍历过程中对每遍历。遍历过程中对每 个顶点调用函数个顶点调用函数Visit Visit 一次且仅一次。一旦一次且仅一次。一旦 visit()visit()失败，则操作失败。失败，则操作失败。FSTraverse(G,Visit();FSTraverse(G,Visit();初始条件：图初始条件：图 G G 存在，存在，Visit Visit 是顶点的应用函数。是顶点的应用函数。操作结果：对图操作结果：对图 G G 进行进行广度优先广度优先遍历。遍历过程中对每遍历。遍历过程中对每 个顶点调用函数个顶点调用函数Visit Visit 一次且仅一次。一旦一次且仅一次。一旦 visit()visit()失败，则操作失败。失败，则操作失败。ADT Graph ADT Graph8/3/202436DFSTraverse(G,Visit();初始条件Data StructureData Structure是否可以采用顺序存储结构存储图是否可以采用顺序存储结构存储图?图的特点：顶点之间的关系是图的特点：顶点之间的关系是m:n，即，即任何两任何两个顶点之间都可能存在关系（边），无法通过个顶点之间都可能存在关系（边），无法通过存储位置表示这种任意的逻辑关系，所以，图存储位置表示这种任意的逻辑关系，所以，图无法采用顺序存储结构。无法采用顺序存储结构。如何存储图如何存储图?考虑图的定义，图是由顶点和边组成的，分别考虑图的定义，图是由顶点和边组成的，分别考虑如何存储顶点、如何存储边。考虑如何存储顶点、如何存储边。7.2 7.2 图的存储结构图的存储结构图的存储结构图的存储结构8/3/202437是否可以采用顺序存储结构存储图?图的特点：顶点之间的关系是mData StructureData Structure7.2 7.2 7.2 7.2 图的存储结构图的存储结构图的存储结构图的存储结构q数组表示法数组表示法(邻接矩阵邻接矩阵)v将图的将图的顶点信息存储在一个一维数组中顶点信息存储在一个一维数组中，并将它的，并将它的邻接矩阵存邻接矩阵存储在一个二维数组中储在一个二维数组中即构成图的数组表示。即构成图的数组表示。v假设图中顶点数为假设图中顶点数为n n，则邻接矩阵，则邻接矩阵A A定义为定义为网的邻接矩阵的定义为，当网的邻接矩阵的定义为，当v vi i到到v vj j有弧相邻接时，有弧相邻接时，a aijij的值应为该的值应为该弧上的权值，否则为弧上的权值，否则为。8/3/2024387.2 图的存储结构数组表示法(邻接矩阵)网的邻接矩阵的定Data StructureData Structurev图的数组图的数组(邻接矩阵邻接矩阵)存储表示存储表示#define INFINITY#define INFINITY INT_MAX;INT_MAX;/最大值最大值#define MAX_VERTEX_NUM#define MAX_VERTEX_NUM 20;20;/最大顶点个数最大顶点个数typedef enum DG,DN,UDG,UDN GraphKind;typedef enum DG,DN,UDG,UDN GraphKind;/有向图有向图,有向网有向网,无向图无向图,无向网无向网 typedef struct ArcCell typedef struct ArcCell VRType VRType adj;adj;/VRType/VRType是顶点关系类型。对无权图，用是顶点关系类型。对无权图，用1 1或或0 0 /表示相邻否；对带权图，则为权值类型。表示相邻否；对带权图，则为权值类型。InfoType InfoType*info;*info;/该弧相关信息的指针该弧相关信息的指针 ArcCell,ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUMAdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct typedef struct VertexType VertexType vexsMAX_VERTEX_NUMvexsMAX_VERTEX_NUM;/顶点信息顶点信息AdjMatrix AdjMatrix arcsarcs;/邻接矩阵邻接矩阵int int vexnum,arcnumvexnum,arcnum;/图的当前顶点数和弧图的当前顶点数和弧(边边)数数GraphKind GraphKind kindkind;/图的种类标志图的种类标志 MGraphMGraph;8/3/202439图的数组(邻接矩阵)存储表示7/29/202339Data StructureData Structure有向图的存储结构有向图的存储结构G1G1BDACG1.vexs=A,B,C,DG1.vexnum=4G1.arcnum=4G1.kind=DG8/3/202440有向图的存储结构G1BDACG1.vexs=A,B,C,DData StructureData Structure有向图的邻接矩阵有向图的邻接矩阵V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何求顶点如何求顶点i 的出度？的出度？邻接矩阵的第邻接矩阵的第i 行元素之和。行元素之和。8/3/202441有向图的邻接矩阵V1V2V3V4V1 V2 V3 Data StructureData Structure有向图的邻接矩阵有向图的邻接矩阵V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何求顶点如何求顶点i 的入度？的入度？邻接矩阵的第邻接矩阵的第i 列元素之和。列元素之和。8/3/202442有向图的邻接矩阵V1V2V3V4V1 V2 V3 Data StructureData Structure有向图的邻接矩阵有向图的邻接矩阵V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何判断从顶点如何判断从顶点i 到顶点到顶点j 是否存在边？是否存在边？测试邻接矩阵中相应位置的元素测试邻接矩阵中相应位置的元素arcij是否为是否为1。8/3/202443有向图的邻接矩阵V1V2V3V4V1 V2 V3 Data StructureData Structure无向图的存储结构无向图的存储结构AECBDG2G2G2.vexs=A,B,C,D,EG2.vexnum=5G2.arcnum=6G2.kind=UDG8/3/202444无向图的存储结构AECBDG2G2.vexs=A,B,C,Data StructureData Structure网图的存储结构网图的存储结构A AD DE EB BC C7 75 53 31 18 86 64 42 2G3G3G3.vexs=A,B,C,D,EG3.vexnum=5G3.arcnum=8G3.kind=UDN8/3/202445网图的存储结构ADEBC75318642G3G3.vexs=Data StructureData Structure如何求顶点如何求顶点i的度？的度？无向图的邻接矩阵无向图的邻接矩阵V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4邻接矩阵的第邻接矩阵的第i行（或第行（或第i列）非零元素的个数。列）非零元素的个数。8/3/202446如何求顶点i的度？无向图的邻接矩阵V1V3V4V2V1 Data StructureData Structure如何判断顶点如何判断顶点i 和和j 之间是否存在边？之间是否存在边？无向图的邻接矩阵无向图的邻接矩阵V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4测试邻接矩阵中相应位置的元素测试邻接矩阵中相应位置的元素arcij是否为是否为1。8/3/202447如何判断顶点 i 和 j 之间是否存在边？无向图的邻接矩阵VData StructureData Structure如何求顶点如何求顶点i 的所有邻接点？的所有邻接点？无向图的邻接矩阵无向图的邻接矩阵V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4将数组中第将数组中第i行元素扫描一遍，若行元素扫描一遍，若arcij为为1，则，则顶点顶点j为顶点为顶点i 的邻接点。的邻接点。8/3/202448如何求顶点 i 的所有邻接点？无向图的邻接矩阵V1V3V4VData StructureData Structurev特点特点：无向图无向图的邻接的邻接矩阵对称矩阵对称，可，可压缩存储压缩存储；有；有n n个顶点的无向图需个顶点的无向图需存储空间为存储空间为n(n+1)/2n(n+1)/2。有向图有向图邻接邻接矩阵不一定对称矩阵不一定对称；有；有n n个顶点的有向图需存储空间个顶点的有向图需存储空间为为n n。无向图无向图中顶点中顶点ViVi的度的度TD(Vi)TD(Vi)是邻接矩阵是邻接矩阵A A中第中第i i行元素之和行元素之和。有向图有向图中，中，顶点顶点ViVi的的出度是出度是A A中第中第i i行元素之和行元素之和。顶点顶点ViVi的的入度是入度是A A中第中第i i列元素之和列元素之和。v邻接矩阵的优缺点邻接矩阵的优缺点优点优点：容易判定顶点间有无边（弧）和计算顶点的度（出度、：容易判定顶点间有无边（弧）和计算顶点的度（出度、入度）。入度）。缺点缺点：边数较少时，空间浪费较大。：边数较少时，空间浪费较大。8/3/202449特点：7/29/202349Data StructureData Structure网图的邻接矩阵网图的邻接矩阵网图的邻接矩阵可定义为：网图的邻接矩阵可定义为：arcijwij若若(vi,vj)E（或（或E）0若若i=j其他其他V1V2V3V4278502500870arc=8/3/202450网图的邻接矩阵网图的邻接矩阵可定义为：arcijData StructureData Structure7.2.2 7.2.2 7.2.2 7.2.2 图的邻接表表示法图的邻接表表示法图的邻接表表示法图的邻接表表示法q引入原因引入原因v邻接矩阵在稀疏图时空间浪费较大。邻接矩阵在稀疏图时空间浪费较大。q实现实现v为图中为图中每个顶点建立一个单链表每个顶点建立一个单链表，第，第i i个单链表中的结点表示依附个单链表中的结点表示依附于顶点于顶点ViVi的边（有向图中指以的边（有向图中指以ViVi为尾的弧）。为尾的弧）。v每个链表附设一个表头结点每个链表附设一个表头结点。表结点表结点adjvexadjvexnextarcnextarcinfoinfo与与ViVi邻接的邻接的点在表头数点在表头数组中的位置组中的位置头结点头结点datadatafirstarcfirstarc8/3/2024517.2.2 图的邻接表表示法引入原因每个链表附设一个表头结Data StructureData Structure图的邻接表存储表示图的邻接表存储表示#define MAX_VERTEX_NUM 20;#define MAX_VERTEX_NUM 20;typedef struct ArcNode typedef struct ArcNode int int adjvex;adjvex;/该弧所指向的顶点的位置该弧所指向的顶点的位置struct ArcNode struct ArcNode*nextarc;*nextarc;/指向下一条弧的指针指向下一条弧的指针InfoType InfoType*info;*info;/该弧相关信息的指针该弧相关信息的指针 ArcNode;ArcNode;typedef struct VNode typedef struct VNode VertexType VertexType data;data;/顶点信息顶点信息ArcNode ArcNode*firstarc;*firstarc;/指向第一条依附该顶点的弧指向第一条依附该顶点的弧 AdjListMAX_VERTEX_NUMAdjListMAX_VERTEX_NUM;typedef struct typedef struct AdjList AdjList verticesvertices;/顶点数组顶点数组int vexnum,arcnum;int vexnum,arcnum;/图的当前顶点数和弧数图的当前顶点数和弧数int kind;int kind;/图的种类标志图的种类标志 ALGraphALGraph;8/3/202452图的邻接表存储表示#define MAX_VERTEX_NUData StructureData Structure10323101V1V2V3V40123vertexfirstedgeV1V3V4V2无向图的邻接表无向图的邻接表边表中的结点表示什么？边表中的结点表示什么？每个结点对应图中的一条边，每个结点对应图中的一条边，邻接表的空间复杂度为邻接表的空间复杂度为O(n+e)。8/3/20245310323101 V1 V2 V3 V40Data StructureData Structure10323101V1V2V3V40123vertexfirstedgeV1V3V4V2无向图的邻接表无向图的邻接表如何求顶点如何求顶点i 的度？的度？顶点顶点i的边表中结点的个数。的边表中结点的个数。8/3/20245410323101 V1 V2 V3 V40Data StructureData Structure如何判断顶点如何判断顶点i 和顶点和顶点j之间是否存在边之间是否存在边?测试顶点测试顶点i 的边表中是否存的边表中是否存在终点为在终点为j 的结点。的结点。10323101V1V2V3V40123vertexfirstedgeV1V3V4V2无向图的邻接表无向图的邻接表8/3/202455如何判断顶点 i 和顶点 j测试顶点 i 的边表中是否存在终Data StructureData Structure有向图的邻接表有向图的邻接表V1V2V3V41220V1V2V3V40123vertexfirstedge如何求顶点如何求顶点i 的出度？的出度？顶点顶点i 的出边表中结点的个数。的出边表中结点的个数。8/3/202456有向图的邻接表V1V2V3V41220 V1 V2Data StructureData Structure有向图的邻接表有向图的邻接表V1V2V3V41220V1V2V3V40123vertexfirstedge如何求顶点如何求顶点i 的入度？的入度？各顶点的出边表中以顶点各顶点的出边表中以顶点i 为为终点的结点个数。终点的结点个数。8/3/202457有向图的邻接表V1V2V3V41220 V1 V2Data StructureData Structure有向图的邻接表有向图的邻接表V1V2V3V41230V1V2V3V40123vertexfirstedge如何求顶点如何求顶点i 的所有邻接点？的所有邻接点？遍历顶点遍历顶点i 的边表，该边表中的的边表，该边表中的所有终点都是顶点所有终点都是顶点i 的邻接点。的邻接点。8/3/202458有向图的邻接表V1V2V3V41230 V1 V2Data StructureData Structure网图的邻接表网图的邻接表V1V2V3V4278521V1V2V3V40123vertexfirstedge5283708/3/202459网图的邻接表V1V2V3V427852 1 V1 VData StructureData Structurev优缺点优缺点优点优点：空间较省；无向图容易求各顶点的度；有向图容易：空间较省；无向图容易求各顶点的度；有向图容易求顶点的出度；求顶点的出度；缺点缺点：求有向图顶点的入度则不容易，要遍历整个表。：求有向图顶点的入度则不容易，要遍历整个表。为了求顶点的入度，有时可设逆邻接表（指向某顶点的邻为了求顶点的入度，有时可设逆邻接表（指向某顶点的邻接点链接成单链表）。接点链接成单链表）。bdac0123acdbdatafirstarc3002adjvex next逆邻接表逆邻接表8/3/202460优缺点bdac0123acdbdatafirstarc3 0Data StructureData Structure7.2.3 7.2.3 7.2.3 7.2.3 图的十字链表表示法图的十字链表表示法图的十字链表表示法图的十字链表表示法q引入原因引入原因v对于同一个对于同一个有向图需要同时用邻接表和逆邻接表有向图需要同时用邻接表和逆邻接表时，不方便。时，不方便。q实现实现v将在有向图的将在有向图的邻接表和逆邻接表中两次出现的同一条弧用一个结邻接表和逆邻接表中两次出现的同一条弧用一个结点表示点表示，由于在邻接表和逆邻接表中的顶点，由于在邻接表和逆邻接表中的顶点数据数据是相同的，则在是相同的，则在十字链表中十字链表中只需要出现一次只需要出现一次，但需，但需保留分别指向第一条保留分别指向第一条 出弧出弧 和和第一条第一条 入弧入弧 的指针的指针。G1G1bdac0123acdbdatafirstarc2130adjvex next邻接表邻接表8/3/2024617.2.3 图的十字链表表示法引入原因G1bdac0123Data StructureData Structure7.2.3 7.2.3 7.2.3 7.2.3 图的十字链表表示法图的十字链表表示法图的十字链表表示法图的十字链表表示法q引入原因引入原因v对于同一个对于同一个有向图需要同时用邻接表和逆邻接表有向图需要同时用邻接表和逆邻接表时，不方便。时，不方便。q实现实现v将在有向图的将在有向图的邻接表和逆邻接表中两次出现的同一条弧用一个结邻接表和逆邻接表中两次出现的同一条弧用一个结点表示点表示，由于在邻接表和逆邻接表中的顶点，由于在邻接表和逆邻接表中的顶点数据数据是相同的，则在是相同的，则在十字链表中十字链表中只需要出现一次只需要出现一次，但需，但需保留分别指向第一条保留分别指向第一条 出弧出弧 和和第一条第一条 入弧入弧 的指针的指针。G1G1bdac逆邻接表逆邻接表0123acdbdatafirstarc3002adjvex next8/3/2024627.2.3 图的十字链表表示法引入原因G1bdac逆邻接表Data StructureData Structure弧结点弧结点tailvextailvexheadvexheadvexhlinkhlinktlinktlinkinfoinfo顶点结点顶点结点datadatafirstinfirstinfirstoutfirstout弧尾弧尾位置位置弧头弧头位置位置弧尾相同的下弧尾相同的下一条弧指针一条弧指针弧相关信息弧相关信息的指针的指针弧头相同的下弧头相同的下弧头相同的下弧头相同的下一条弧指针一条弧指针一条弧指针一条弧指针指向该顶点指向该顶点第一条入弧第一条入弧指向该顶点指向该顶点第一条出弧第一条出弧8/3/202463弧结点tailvexheadvexhlinktlinkinfData StructureData Structure02012320323130bdacabcd0123求结点的入度求结点的入度和出度的方法和出度的方法？8/3/202464 0 2 0 1 2 3 2 0 3 2Data StructureData Structure7.2.4 7.2.4 7.2.4 7.2.4 图的邻接多重表表示法图的邻接多重表表示法图的邻接多重表表示法图的邻接多重表表示法 q引入原因引入原因v无向图的邻接表中无向图的邻接表中每一条边有两个结点，每一条边有两个结点，给对图的边进行访问的给对图的边进行访问的操作带来不便。有些时候需要同时找到表示同一条边的两个结点操作带来不便。有些时候需要同时找到表示同一条边的两个结点（如删除一条边）。（如删除一条边）。aecbd0123acdbdatafirstarc3101adjvex next4e324042128/3/2024657.2.4 图的邻接多重表表示法 引入原因aecbd012Data StructureData Structureq实现实现v每条边用一个结点表示。每条边用一个结点表示。边结点边结点markmarkivexivexilinkilinkjvexjvexjlinkjlinkinfoinfo顶点结点顶点结点markmarkfirstedgefirstedge访问访问标记标记边依附的边依附的一个顶点一个顶点边依附的边依附的另一个顶另一个顶点点依附这个顶依附这个顶点的下一条点的下一条边指针边指针依附这个顶依附这个顶点的下一条点的下一条边指针边指针访问访问标记标记指向第一条指向第一条 依附该顶点的依附该顶点的边边8/3/202466实现边结点markivexilinkjvexjlinkinfData StructureData Structureaecbd0123acdb4e0103232124418/3/202467aecbd0123acdb4e 0 Data StructureData Structure7.3 7.3 7.3 7.3 图的遍历图的遍历图的遍历图的遍历q图的遍历图的遍历v从从图图中中某某一一顶顶点点出出发发，访访问问图图中中其其余余顶顶点点，使使每每个个顶顶点点被被访访问问一一次次且只被访问一次且只被访问一次。v可以从图中可以从图中任意一个顶点出发任意一个顶点出发进行遍历。进行遍历。v遍历中需解决的问题遍历中需解决的问题确定一搜索路径确定一搜索路径；确保确保每个顶点被访问到每个顶点被访问到；确保每个顶点确保每个顶点只能被访问一次只能被访问一次。v解决方法解决方法深度优先和广度优先。深度优先和广度优先。设设辅辅助助数数组组visitedvisited，初初始始时时，数数组组元元素素的的值值均均为为0 0或或falsefalse，表示未被遍历，一旦遍历，就置为表示未被遍历，一旦遍历，就置为1 1或或truetrue。8/3/2024687.3 图的遍历图的遍历7/29/202368Data StructureData Structure7.3.1 7.3.1 7.3.1 7.3.1 深度优先搜索深度优先搜索深度优先搜索深度优先搜索q方法方法v从图的某一顶点从图的某一顶点V0V0出发，访问此顶点；出发，访问此顶点；v然后依次从然后依次从V0V0的未被访问的邻接点出发，深度优先遍历图，直的未被访问的邻接点出发，深度优先遍历图，直至图中所有和至图中所有和V0V0相通的顶点都被访问到；相通的顶点都被访问到；v若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。点作起点，重复上述过程，直至图中所有顶点都被访问为止。访问任意一个与访问任意一个与V0V0邻接的顶点邻接的顶点W1W1，再从，再从W1W1出发；出发；访问与访问与W1W1邻接且未被访问过的任意顶点邻接且未被访问过的任意顶点W2W2，再从，再从W2W2出发；出发；重复以上过程，直到一个所有邻接点都被访问过的顶点为止；重复以上过程，直到一个所有邻接点都被访问过的顶点为止；退回到尚有邻接点未被访问过的顶点，再从该顶点出发；退回到尚有邻接点未被访问过的顶点，再从该顶点出发；直到所有的被访问过的顶点的邻接点都已被访问过为止。直到所有的被访问过的顶点的邻接点都已被访问过为止。8/3/2024697.3.1 深度优先搜索方法若此时图中尚有顶点未被访问，则Data StructureData Structure深一层递归深一层递归递归返回递归返回深度优先遍历序列深度优先遍历序列?入栈序列入栈序列?出栈序列出栈序列?V1V3V2V4V5V6V7V8V1遍历序列：遍历序列：V1V2V2V4V4V5V58/3/202470深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?V1Data StructureData Structure深一层递归深一层递归递归返回递归返回深度优先遍历序列深度优先遍历序列?入栈序列入栈序列?出栈序列出栈序列?V1V3V2V4V5V6V7V8V1遍历序列：遍历序列：V1V2V2V4V4V5V8V88/3/202471深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?V1Data StructureData Structure深一层递归深一层递归递归返回递归返回深度优先遍历序列深度优先遍历序列?入栈序列入栈序列?出栈序列出栈序列?6