数据结构图论部分课件.ppt

1、Data StructureData StructurePage 12023-4-2710086510Data StructureData StructurePage 22023-4-27q 学习目标学习目标v领会领会图的类型定义图的类型定义。v熟悉熟悉图的各种存储结构图的各种存储结构及其构造算法，了解各种存储结构的特点及其构造算法，了解各种存储结构的特点及其及其选用原则选用原则。v熟练掌握图的两种熟练掌握图的两种遍历遍历算法。算法。v理解各种图的理解各种图的应用问题的算法应用问题的算法。q 重点和难点重点和难点v重点：图的各种应用问题的算法都比较经典，注意重点：图的各种应用问题的算法都比较经

2、典，注意理解各种图的理解各种图的算法及其应用场合算法及其应用场合。Data StructureData StructurePage 32023-4-27q 知识点知识点v图的类型定义图的类型定义v图的存储表示图的存储表示v图的深度优先搜索遍历和广度优先搜索遍历图的深度优先搜索遍历和广度优先搜索遍历v无向网的最小生成树无向网的最小生成树v拓扑排序拓扑排序v关键路径关键路径v最短路径最短路径Data StructureData StructurePage 42023-4-27欧拉欧拉17071707年出生在瑞士的巴塞尔城，年出生在瑞士的巴塞尔城，1919岁开始发岁开始发表论文，直到表论文，直到76

3、76岁。几乎每一个数学领域都可以岁。几乎每一个数学领域都可以看到欧拉的名字，从初等几何的欧拉线，多面体看到欧拉的名字，从初等几何的欧拉线，多面体的欧拉定理，立体解析几何的欧拉变换公式，四的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法到数论中的欧拉函数，微分方次方程的欧拉解法到数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数，变分学的欧程的欧拉方程，级数论的欧拉常数，变分学的欧拉方程，复变函数的欧拉公式等等。据统计他那拉方程，复变函数的欧拉公式等等。据统计他那不倦的一生，共写下了不倦的一生，共写下了886886本书籍和论文，其中本书籍和论文，其中分析、代数、数论占分析、代数、数

4、论占40%40%，几何占，几何占18%18%，物理和，物理和力学占力学占28%28%，天文学占，天文学占11%11%，弹道学、航海学、，弹道学、航海学、建筑学等占建筑学等占3%3%。17331733年，年仅年，年仅2626岁的欧拉担任岁的欧拉担任了彼得堡科学院数学教授。了彼得堡科学院数学教授。17411741年到柏林担任科年到柏林担任科学院物理数学所所长，直到学院物理数学所所长，直到17661766年，重回彼得堡，年，重回彼得堡，没有多久，完全失明。欧拉在数学上的建树很多，没有多久，完全失明。欧拉在数学上的建树很多，对著名的哥尼斯堡七桥问题的解答开创了图论的对著名的哥尼斯堡七桥问题的解答开创了

5、图论的研究。研究。Data StructureData StructurePage 52023-4-27能否从某个地方出发，穿过所有的桥仅一次能否从某个地方出发，穿过所有的桥仅一次后再回到出发点？后再回到出发点？Data StructureData StructurePage 62023-4-27CADB七桥问题的图模型七桥问题的图模型欧拉回路的判定规则：欧拉回路的判定规则：1.如果通奇数桥的地方多于如果通奇数桥的地方多于两个，则不存在欧拉回路；两个，则不存在欧拉回路；2.如果只有两个地方通奇数如果只有两个地方通奇数桥，可以从这两个地方之一桥，可以从这两个地方之一出发，找到欧拉回路；出发，找到

6、欧拉回路；3.如果没有一个地方是通奇如果没有一个地方是通奇数桥的，则无论从哪里出发，数桥的，则无论从哪里出发，都能找到欧拉回路。都能找到欧拉回路。Data StructureData StructurePage 72023-4-27图的定义图的定义图是由图是由顶点顶点的的有穷非空有穷非空集合和顶点之间集合和顶点之间边边的集合组的集合组成，通常表示为：成，通常表示为：G=(V，E)其中：其中：G表示一个图，表示一个图，V是图是图G中顶点的集合，中顶点的集合，E是是图图G中顶点之间边的集合。中顶点之间边的集合。在线性表中，元素个数可以为零，称为空表；在线性表中，元素个数可以为零，称为空表；在树中，

7、结点个数可以为零，称为空树；在树中，结点个数可以为零，称为空树；在图中，顶点个数不能为零，但可以没有边。在图中，顶点个数不能为零，但可以没有边。7.1 7.1 图的定义和术语图的定义和术语Data StructureData StructurePage 82023-4-27q线性表线性表v每个数据元素只有一个直接前驱和一个直接后继。每个数据元素只有一个直接前驱和一个直接后继。q树形结构树形结构v每个数据元素只有一个直接前驱，但可能有多个直接后继。每个数据元素只有一个直接前驱，但可能有多个直接后继。q图形结构图形结构v每个数据元素可能有多个直接前驱和多个直接后继。每个数据元素可能有多个直接前驱和

8、多个直接后继。图是比线性表和树复杂的数据结构，广泛应用于语图是比线性表和树复杂的数据结构，广泛应用于语言学、逻辑学、物理、化学等领域。言学、逻辑学、物理、化学等领域。Data StructureData StructurePage 92023-4-27如果图的任意两个顶点之间的边都如果图的任意两个顶点之间的边都是是无向边，则称该图为无向边，则称该图为无向图无向图。若顶点若顶点vi和和vj之间的边没有方向，则之间的边没有方向，则称这条边为称这条边为无向边无向边，表示为，表示为(vi,vj)。若从顶点若从顶点vi到到vj的边有方向，则称这的边有方向，则称这条边为条边为有向边有向边，表示为，表示为。

9、如果图的任意两个顶点之间的边都如果图的任意两个顶点之间的边都是是有向边，则称该图为有向边，则称该图为有向图有向图。V1V2V3V4V5V1V2V3V4图的基本术语图的基本术语 Data StructureData StructurePage 102023-4-27简单图：简单图：在图中，若不存在顶点到其自身的边，且同在图中，若不存在顶点到其自身的边，且同一条边不重复出现一条边不重复出现。V3V4V5V1V2V3V4V5V1V2非简单图非简单图 非简单图非简单图 简单图简单图V1V2V3V4V5v 数据结构中讨论的都是简单图。数据结构中讨论的都是简单图。Data StructureData St

10、ructurePage 112023-4-27图的基本术语图的基本术语 邻接、依附邻接、依附无向图无向图中，对于任意两个顶点中，对于任意两个顶点vi和顶点和顶点vj，若存在边，若存在边(vi，vj)，则称顶点，则称顶点vi和顶点和顶点vj互为邻接点，同时称边互为邻接点，同时称边(vi，vj)依附于顶点依附于顶点vi和顶点和顶点vj。V1V2V3V4V5V1的邻接点：的邻接点：V2、V4V2的邻接点：的邻接点：V1、V3、V5Data StructureData StructurePage 122023-4-27图的基本术语图的基本术语 邻接、依附邻接、依附有向图有向图中，对于任意两个顶点中，对

11、于任意两个顶点vi和顶点和顶点vj，若存在弧，若存在弧，则称顶点，则称顶点vi邻接到顶点邻接到顶点vj，顶点，顶点vj邻接自顶邻接自顶点点vi，同时称弧同时称弧依附于顶点依附于顶点vi和顶点和顶点vj。V1V2V3V4V1的邻接点：的邻接点：V2、V3V3的邻接点：的邻接点：V4Data StructureData StructurePage 132023-4-27无向完全图无向完全图：在无向图中，如果任意两个顶点之间：在无向图中，如果任意两个顶点之间都存在边，都存在边，则称该图为无向完全图。则称该图为无向完全图。有向完全图有向完全图：在有向图中，如果任意两个顶点之间：在有向图中，如果任意两个

12、顶点之间都存在方向相反的两条弧，都存在方向相反的两条弧，则称该图为有向完全图则称该图为有向完全图。图的基本术语图的基本术语 V1V2V3V1V2V3V4Data StructureData StructurePage 142023-4-27含有含有n个顶点的无向完全图有个顶点的无向完全图有多少多少条边？条边？含有含有n个顶点的有向完全图有个顶点的有向完全图有多少多少条弧？条弧？含有含有n个顶点的无向完全图有个顶点的无向完全图有n(n-1)/2条边。条边。含有含有n个顶点的有向完全图有个顶点的有向完全图有n(n-1)条边。条边。V1V2V3V1V2V3V4Data StructureData S

13、tructurePage 152023-4-27稀疏图：稀疏图：称边数很少的图为稀疏图；称边数很少的图为稀疏图；稠密图：稠密图：称边数很多的图为稠密图。称边数很多的图为稠密图。顶点的度：顶点的度：在无向图中，顶点在无向图中，顶点v的的度度是指依附于该顶是指依附于该顶点的边数，通常记为点的边数，通常记为TD(v)。图的基本术语图的基本术语 顶点的入度：顶点的入度：在有向图中，顶点在有向图中，顶点v的的入度入度是指以该顶是指以该顶点为弧头的弧的数目，点为弧头的弧的数目，记为记为ID(v)；顶点顶点的的出度：出度：在有向图中，顶点在有向图中，顶点v的的出度出度是指以该顶是指以该顶点为弧尾的弧的数目，

14、记为点为弧尾的弧的数目，记为OD(v)。Data StructureData StructurePage 162023-4-27V1V2V3V4V5图的基本术语图的基本术语 在具有在具有n个顶点、个顶点、e条边的无向图条边的无向图G中，各顶点中，各顶点的度之和与边数之和的关系？的度之和与边数之和的关系？=niievTD12)(Data StructureData StructurePage 172023-4-27V1V2V3V4图的基本术语图的基本术语 在具有在具有n个顶点、个顶点、e条边的有向图条边的有向图G中，各顶点中，各顶点的入度之和与各顶点的出度之和的关系？与边的入度之和与各顶点的出度

15、之和的关系？与边数之和的关系？数之和的关系？evODvIDiiii=11)()(nnData StructureData StructurePage 182023-4-27权：权：是指对边赋予的有意义的数值量。是指对边赋予的有意义的数值量。网：网：边上带权的图，也称网图。边上带权的图，也称网图。图的基本术语图的基本术语 V1V2V3V42785Data StructureData StructurePage 192023-4-27路径：路径：在无向图在无向图G=(V,E)中，从顶点中，从顶点vp到顶点到顶点vq之间的之间的路径路径是一个顶点序列是一个顶点序列(vp=vi0,vi1,vi2,vi

16、m=vq)，其中，其中，(vij-1,vij)E（1jm）。若）。若G是有向图，则路径也是有是有向图，则路径也是有方向的，顶点序列满足方向的，顶点序列满足E。图的基本术语图的基本术语 V1V2V3V4V5v一般情况下，图中的路径不惟一。一般情况下，图中的路径不惟一。V1 到到V4的路径：的路径：V1 V4 V1 V2 V3 V4 V1 V2 V5V3 V4Data StructureData StructurePage 202023-4-27路径长度：路径长度：图的基本术语图的基本术语 非带权图非带权图路径路径上边的上边的个数个数带权图带权图路径上路径上各边的各边的权之和权之和V1V2V3V4

17、V5V1 V4：长度为：长度为1V1 V2 V3 V4：长度为：长度为3V1 V2 V5V3 V4：长度为：长度为4Data StructureData StructurePage 212023-4-27路径长度：路径长度：图的基本术语图的基本术语 非带权图非带权图路径路径上边的上边的个数个数带权图带权图路径上路径上各边的各边的权之和权之和V1 V4：长度为：长度为8V1 V2 V3 V4：长度为：长度为7V1 V2 V5V3 V4：长度为：长度为15V1V2V3V4V5256328Data StructureData StructurePage 222023-4-27回路（环）回路（环）：第

18、一个顶点和最后一个顶点相同的路径。：第一个顶点和最后一个顶点相同的路径。简单路径：简单路径：序列中顶点不重复出现的路径。序列中顶点不重复出现的路径。简单回路（简单环）：简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。顶点不重复出现的回路。图的基本术语图的基本术语 V1V2V3V4V5V1V2V3V4Data StructureData StructurePage 232023-4-27子图：子图：若图若图G=（V，E），），G=（V，E），如果），如果V V 且且E E，则称图，则称图G是是G的子图。的子图。图的基本术语图的基本

19、术语 V1V2V3V4V5V1V2V3V4V5V1V3V4Data StructureData StructurePage 242023-4-27连通图：连通图：在无向图中，如果从一个顶点在无向图中，如果从一个顶点vi到另一个顶到另一个顶点点vj(ij)有路径，则称顶点有路径，则称顶点vi和和vj是连通的。如果图中是连通的。如果图中任意两个顶点都是连通的，则称该图是连通任意两个顶点都是连通的，则称该图是连通图。图。连通分量：连通分量：非连通图的极大连通子图称为连通分量。非连通图的极大连通子图称为连通分量。图的基本术语图的基本术语 如何求得一个非连通图的连通分量如何求得一个非连通图的连通分量?1

20、.含有极大含有极大顶点顶点数；数；2.依附于这些顶点的所有依附于这些顶点的所有边边。Data StructureData StructurePage 252023-4-27连通分量连通分量1 V1V2V3V4V5V6V7V1V2V4V5V3V6V7连通分量连通分量2图的基本术语图的基本术语 v连通分量是对无向图的一种划分。连通分量是对无向图的一种划分。Data StructureData StructurePage 262023-4-27强连通图：强连通图：在有向图中，对图中任意一对顶点在有向图中，对图中任意一对顶点vi和和vj(ij)，若从顶点，若从顶点vi到顶点到顶点vj和从顶点和从顶点v

21、j到顶点到顶点vi均有路径均有路径，则称该有向图是强连通图。，则称该有向图是强连通图。强连通分量：强连通分量：非强连通图非强连通图的极大强连通子图。的极大强连通子图。图的基本术语图的基本术语 如何求得一个非连通图的连通分量如何求得一个非连通图的连通分量?Data StructureData StructurePage 272023-4-27图的基本术语图的基本术语 V1V2V3V4强连通分量强连通分量1 强连通分量强连通分量2V1V3V4V2Data StructureData StructurePage 282023-4-27生成树：生成树：n个顶点的连通图个顶点的连通图G的生成树是包含的生

22、成树是包含G中中全全部顶点部顶点的一个极小连通的一个极小连通子图。子图。生成森林：生成森林：在非连通图中，由每个连通分量都可以得在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分到一棵生成树，这些连通分量的生成树就组成了一个量的生成树就组成了一个非连通图的非连通图的生成森林生成森林。如何理解极小连通子图如何理解极小连通子图?图的基本术语图的基本术语 多多构成回路构成回路少少不连通不连通含有含有n-1条边条边Data StructureData StructurePage 292023-4-27V1V2V3V4V5V6V7V1V2V3V4V5V6V7V1V2V3V4V5V1V2V3V4

23、V5生成树生成树生成森林生成森林Data StructureData StructurePage 302023-4-27q图的抽象数据类型定义如下：图的抽象数据类型定义如下：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)定义了弧定义了弧的意义的意义 或信息或信息 Data StructureData Struc

24、turePage 312023-4-27G1=(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)Data StructureData StructurePage 322023-4-27CreateGraph(&GCreateGraph(&G,V,VR);,V,VR);初始

25、条件：初始条件：V V 是图的顶点集，是图的顶点集，VR VR 是图中弧的集合。是图中弧的集合。操作结果：按操作结果：按 V V 和和 VR VR 的定义的定义构造图构造图 G G。DestroyGraph(&GDestroyGraph(&G););初始条件：图初始条件：图 G G 存在。存在。操作结果：操作结果：销毁图销毁图 G G。LocateVex(GLocateVex(G,u);,u);初始条件：图初始条件：图 G G 存在，存在，u u 和和 G G 中顶点有相同特征。中顶点有相同特征。操作结果：若操作结果：若 G G 中存在和中存在和 u u 相同的顶点，则相同的顶点，则返回该顶点

26、返回该顶点 在图中位置在图中位置；否则返回其它信息。；否则返回其它信息。Data StructureData StructurePage 332023-4-27GetVex(GGetVex(G,v);,v);初始条件：图初始条件：图 G G 存在，存在，v v 是是 G G 中某个顶点。中某个顶点。操作结果：返回操作结果：返回 v v 的值的值。FirstAdjVex(GFirstAdjVex(G,v);,v);初始条件：图初始条件：图 G G 存在，存在，v v 是是 G G 中某个顶点。中某个顶点。操作结果：操作结果：返回返回 v v 的第一个邻接点。的第一个邻接点。若该顶点在若该顶点在

27、G G 中没中没 有邻接点，则返回有邻接点，则返回“空空”。NextAdjVex(GNextAdjVex(G,v,w);,v,w);初始条件：图初始条件：图 G G 存在，存在，v v 是是 G G 中某个顶点，中某个顶点，w w 是是 v v 的的 邻接顶点。邻接顶点。操作结果：操作结果：返回返回 v v 的（相对于的（相对于 w w 的）下一个邻接点。的）下一个邻接点。若若 w w 是是 v v 的最后一个邻接点，则返回的最后一个邻接点，则返回“空空”。Data StructureData StructurePage 342023-4-27PutVex(&GPutVex(&G,v,valu

28、e);,v,value);初始条件：图初始条件：图 G G 存在，存在，v v 是是 G G 中某个顶点。中某个顶点。操作结果：操作结果：对对 v v 赋值赋值 valuevalue。InsertVex(&GInsertVex(&G,v);,v);初始条件：图初始条件：图 G G 存在，存在，v v 和图中顶点有相同特征。和图中顶点有相同特征。操作结果：在图操作结果：在图 G G 中中增添新顶点增添新顶点 v v。DeleteVex(&GDeleteVex(&G,v);,v);初始条件：图初始条件：图 G G 存在，存在，v v 是是 G G 中某个顶点。中某个顶点。操作结果：操作结果：删除删

29、除 G G 中顶点中顶点 v v 及其相关的弧及其相关的弧。Data StructureData StructurePage 352023-4-27InsertArc(&GInsertArc(&G,v,w);,v,w);初始条件：图初始条件：图 G G 存在，存在，v v 和和 w w 是是 G G 中两个顶点。中两个顶点。操作结果：在操作结果：在 G G 中中增添弧增添弧，若，若 G G 是是无向的，则还无向的，则还 增添对称弧增添对称弧。DeleteArc(&GDeleteArc(&G,v,w);,v,w);初始条件：图初始条件：图 G G 存在，存在，v v 和和 w w 是是 G G

30、中两个顶点。中两个顶点。操作结果：在操作结果：在 G G 中中删除弧删除弧，若若 G G 是是无向的，则还无向的，则还 删除对称弧删除对称弧。Data StructureData StructurePage 362023-4-27DFSTraverse(GDFSTraverse(G,Visit();,Visit();初始条件：图初始条件：图 G G 存在，存在，Visit Visit 是顶点的应用函数。是顶点的应用函数。操作结果：对图操作结果：对图 G G 进行进行深度优先深度优先遍历。遍历过程中对每遍历。遍历过程中对每 个顶点调用函数个顶点调用函数Visit Visit 一次且仅一次。一旦一

31、次且仅一次。一旦 visit()visit()失败，则操作失败。失败，则操作失败。FSTraverse(GFSTraverse(G,Visit();,Visit();初始条件：图初始条件：图 G G 存在，存在，Visit Visit 是顶点的应用函数。是顶点的应用函数。操作结果：对图操作结果：对图 G G 进行进行广度优先广度优先遍历。遍历过程中对每遍历。遍历过程中对每 个顶点调用函数个顶点调用函数Visit Visit 一次且仅一次。一旦一次且仅一次。一旦 visit()visit()失败，则操作失败。失败，则操作失败。ADT Graph ADT GraphData StructureDa

32、ta StructurePage 372023-4-27是否可以采用顺序存储结构存储图是否可以采用顺序存储结构存储图?图的特点：顶点之间的关系是图的特点：顶点之间的关系是m:n，即，即任何两任何两个顶点之间都可能存在关系（边），无法通过个顶点之间都可能存在关系（边），无法通过存储位置表示这种任意的逻辑关系，所以，图存储位置表示这种任意的逻辑关系，所以，图无法采用顺序存储结构。无法采用顺序存储结构。如何存储图如何存储图?考虑图的定义，图是由顶点和边组成的，分别考虑图的定义，图是由顶点和边组成的，分别考虑如何存储顶点、如何存储边。考虑如何存储顶点、如何存储边。Data StructureData

33、StructurePage 382023-4-27q 数组表示法数组表示法(邻接矩阵邻接矩阵)v将图的将图的顶点信息存储在一个一维数组中顶点信息存储在一个一维数组中，并将它的，并将它的邻接矩阵存邻接矩阵存储在一个二维数组中储在一个二维数组中即构成图的数组表示。即构成图的数组表示。v假设图中顶点数为假设图中顶点数为n n，则邻接矩阵，则邻接矩阵A A定义为定义为=，其它0E(G)v,v或)v,(v若1,jijijiA网的邻接矩阵的定义为，当网的邻接矩阵的定义为，当v vi i到到v vj j有弧相邻接时，有弧相邻接时，a aijij的值应为该的值应为该弧上的权值，否则为弧上的权值，否则为。Dat

34、a StructureData StructurePage 392023-4-27v图的数组图的数组(邻接矩阵邻接矩阵)存储表示存储表示#define INFINITY#define INFINITY INT_MAX;INT_MAX;/最大值最大值#define MAX_VERTEX_NUM#define MAX_VERTEX_NUM 20;20;/最大顶点个数最大顶点个数typedef enum DG,DN,UDG,UDN GraphKindtypedef enum DG,DN,UDG,UDN GraphKind;/有向图有向图,有向网有向网,无向图无向图,无向网无向网 typedef st

35、ruct ArcCell typedef struct ArcCell VRType VRType adjadj;/VRType/VRType是顶点关系类型。对无权图，用是顶点关系类型。对无权图，用1 1或或0 0 /表示相邻否；对带权图，则为权值类型。表示相邻否；对带权图，则为权值类型。InfoTypeInfoType *info;info;/该弧相关信息的指针该弧相关信息的指针 ArcCell ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUMAdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct t

36、ypedef struct VertexTypeVertexType vexsMAX_VERTEX_NUMvexsMAX_VERTEX_NUM;/顶点信息顶点信息AdjMatrixAdjMatrix arcsarcs;/邻接矩阵邻接矩阵intint vexnum,arcnumvexnum,arcnum;/图的当前顶点数和弧图的当前顶点数和弧(边边)数数GraphKindGraphKind kindkind;/图的种类标志图的种类标志 MGraphMGraph;Data StructureData StructurePage 402023-4-27G1G1BDAC0 01 11 10 00 00

37、 00 00 0G G1 1.a ar rc cs s=0 00 00 01 11 10 00 00 0G1.vexs=A,B,C,DG1.vexnum=4G1.arcnum=4G1.kind=DGData StructureData StructurePage 412023-4-27有向图的邻接矩阵有向图的邻接矩阵V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc=V1 V2 V3 V4V1V2V3V4如何求顶点如何求顶点 i 的出度？的出度？邻接矩阵的第邻接矩阵的第 i 行元素之和。行元素之和。Data Structu

38、reData StructurePage 422023-4-27有向图的邻接矩阵有向图的邻接矩阵V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc=V1 V2 V3 V4V1V2V3V4如何求顶点如何求顶点 i 的入度？的入度？邻接矩阵的第邻接矩阵的第 i 列元素之和。列元素之和。Data StructureData StructurePage 432023-4-27有向图的邻接矩阵有向图的邻接矩阵V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc=V

39、1 V2 V3 V4V1V2V3V4如何判断从顶点如何判断从顶点 i 到顶点到顶点 j 是否存在边？是否存在边？测试邻接矩阵中相应位置的元素测试邻接矩阵中相应位置的元素arcij是否为是否为1。Data StructureData StructurePage 442023-4-27AECBDG2G20 01 10 01 10 01 10 01 10 01 1G G2 2.a ar rc cs s=0 01 10 01 11 11 10 01 10 00 00 01 11 10 00 0G2.vexs=A,B,C,D,EG2.vexnum=5G2.arcnum=6G2.kind=UDGData

40、StructureData StructurePage 452023-4-270 05 57 70 03 35 50 00 04 48 8G G3 3.a ar rc cs s=7 70 00 02 21 10 04 42 20 06 63 38 81 16 60 0A AD DE EB BC C7 75 53 31 18 86 64 42 2G3G3G3.vexs=A,B,C,D,EG3.vexnum=5G3.arcnum=8G3.kind=UDNData StructureData StructurePage 462023-4-27如何求顶点如何求顶点i的度？的度？无向图的邻接矩阵无向图的

41、邻接矩阵V1V3V4V2V1 V2 V3 V4vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc=V1 V2 V3 V4V1V2V3V4邻接矩阵的第邻接矩阵的第i行（或第行（或第i列）非零元素的个数。列）非零元素的个数。Data StructureData StructurePage 472023-4-27如何判断顶点如何判断顶点 i 和和 j 之间是否存在边？之间是否存在边？无向图的邻接矩阵无向图的邻接矩阵V1V3V4V2V1 V2 V3 V4vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc=V1 V2 V3 V4V1V2

42、V3V4测试邻接矩阵中相应位置的元素测试邻接矩阵中相应位置的元素arcij是否为是否为1。Data StructureData StructurePage 482023-4-27如何求顶点如何求顶点 i 的所有邻接点？的所有邻接点？无向图的邻接矩阵无向图的邻接矩阵V1V3V4V2V1 V2 V3 V4vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc=V1 V2 V3 V4V1V2V3V4将数组中第将数组中第 i 行元素扫描一遍，若行元素扫描一遍，若arcij为为1，则，则顶点顶点 j 为顶点为顶点 i 的邻接点。的邻接点。Data StructureData

43、 StructurePage 492023-4-27v特点特点：无向图无向图的邻接的邻接矩阵对称矩阵对称，可，可压缩存储压缩存储；有；有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的的入度是入度

44、是A A中第中第i i列元素之和列元素之和。v邻接矩阵的优缺点邻接矩阵的优缺点优点优点：容易判定顶点间有无边（弧）和计算顶点的度（出度、：容易判定顶点间有无边（弧）和计算顶点的度（出度、入度）。入度）。缺点缺点：边数较少时，空间浪费较大。：边数较少时，空间浪费较大。Data StructureData StructurePage 502023-4-27网图的邻接矩阵网图的邻接矩阵网图的邻接矩阵可定义为：网图的邻接矩阵可定义为：arcij wij 若若(vi,vj)E（或（或E）0 若若i=j 其他其他V1V2V3V42785 0 2 5 0 0 8 7 0 arc=Data Structure

45、Data StructurePage 512023-4-277.2.2 7.2.2 图的邻接表表示法图的邻接表表示法q 引入原因引入原因v邻接矩阵在稀疏图时空间浪费较大。邻接矩阵在稀疏图时空间浪费较大。q 实现实现v为图中为图中每个顶点建立一个单链表每个顶点建立一个单链表，第，第i i个单链表中的结点表示依个单链表中的结点表示依附于顶点附于顶点ViVi的边（有向图中指以的边（有向图中指以ViVi为尾的弧）。为尾的弧）。v每个链表附设一个表头结点每个链表附设一个表头结点。表结点表结点adjvexadjvexnextarcnextarcinfoinfo与与ViVi邻接的邻接的点在表头数点在表头数组

46、中的位置组中的位置头结点头结点datadatafirstarcfirstarcData StructureData StructurePage 522023-4-27#define MAX_VERTEX_NUM 20;#define MAX_VERTEX_NUM 20;typedef struct ArcNode typedef struct ArcNode int int adjvexadjvex;/该弧所指向的顶点的位置该弧所指向的顶点的位置struct ArcNode struct ArcNode*nextarcnextarc;/指向下一条弧的指针指向下一条弧的指针InfoTypeInf

47、oType *info;info;/该弧相关信息的指针该弧相关信息的指针 ArcNode ArcNode;typedef struct VNode typedef struct VNode VertexTypeVertexType data;data;/顶点信息顶点信息ArcNode ArcNode*firstarcfirstarc;/指向第一条依附该顶点的弧指向第一条依附该顶点的弧 AdjListMAX_VERTEX_NUMAdjListMAX_VERTEX_NUM;typedef structtypedef struct AdjListAdjList verticesvertices;/顶

48、点数组顶点数组int vexnum,arcnumint vexnum,arcnum;/图的当前顶点数和弧数图的当前顶点数和弧数intint kind;kind;/图的种类标志图的种类标志 ALGraphALGraph;Data StructureData StructurePage 532023-4-2710323101 V1 V2 V3 V40123vertex firstedgeV1V3V4V2无向图的邻接表无向图的邻接表边表中的结点表示什么？边表中的结点表示什么？每个结点对应图中的一条边，每个结点对应图中的一条边，邻接表的空间复杂度为邻接表的空间复杂度为O(n+e)。Data Struc

49、tureData StructurePage 542023-4-2710323101 V1 V2 V3 V40123vertex firstedgeV1V3V4V2无向图的邻接表无向图的邻接表如何求顶点如何求顶点 i 的度？的度？顶点顶点i的边表中结点的个数。的边表中结点的个数。Data StructureData StructurePage 552023-4-27如何判断顶点如何判断顶点 i 和顶点和顶点 j之间是否存在边之间是否存在边?测试顶点测试顶点 i 的边表中是否存的边表中是否存在终点为在终点为 j 的结点。的结点。10323101 V1 V2 V3 V40123vertex fir

50、stedgeV1V3V4V2无向图的邻接表无向图的邻接表Data StructureData StructurePage 562023-4-27有向图的邻接表有向图的邻接表V1V2V3V41220 V1 V2 V3 V40123vertex firstedge如何求顶点如何求顶点 i 的出度？的出度？顶点顶点 i 的出边表中结点的个数。的出边表中结点的个数。Data StructureData StructurePage 572023-4-27有向图的邻接表有向图的邻接表V1V2V3V41220 V1 V2 V3 V40123vertex firstedge如何求顶点如何求顶点 i 的入度？的