1、Page 12022-11-11p 画出下列二叉链表代表的二叉树（画出下列二叉链表代表的二叉树（0代表代表NULL指针），并指针），并完成其先序线索链表完成其先序线索链表InfoInfoA AB BC CD DE EF FG GH HI IJ JK KL LM MN NLtagLtagLchildLchild2 24 46 60 07 70 010100 0121213130 00 00 00 0RtagRtagRchildRchild3 35 50 00 08 89 911110 00 00 014140 00 00 0InfoInfoA AB BC CD DE EF FG GH HI IJ
2、 JK KL LM MN NLtagLtag0 00 00 01 10 01 10 01 10 00 01 11 11 11 1LchildLchild2 24 46 62 27 73 3101014141212131313139 910101111RtagRtag0 00 01 11 10 00 00 01 11 11 10 01 11 11 1RchildRchild3 35 56 65 58 89 911113 31212131314140 011118 81 2 3 4 5 6 7 8 9 10 11 12 13 14Page 22022-11-11第第8-1讲讲 图的基础知识图的基础
3、知识清华大学清华大学 自动化系自动化系 黄双喜黄双喜 博士、副教授博士、副教授Page 32022-11-11q学习目标学习目标v领会领会图的基本概念图的基本概念。v熟悉熟悉图的各种存储结构图的各种存储结构及其构造算法，了解各种存储及其构造算法，了解各种存储结构的特点及其结构的特点及其选用原则选用原则。v熟练掌握图的两种熟练掌握图的两种遍历遍历算法及应用。算法及应用。v理解各种图的理解各种图的应用问题的算法应用问题的算法。q重点和难点重点和难点v重点：图的各种应用问题的算法都比较经典，注意重点：图的各种应用问题的算法都比较经典，注意理理解各种图的算法及其应用场合解各种图的算法及其应用场合。Pa
4、ge 42022-11-11q知识点知识点v图的类型定义图的类型定义v图的存储表示图的存储表示v图的深度优先搜索遍历和广度优先搜索遍历图的深度优先搜索遍历和广度优先搜索遍历v最小生成树算法最小生成树算法v拓扑排序拓扑排序v关键路径关键路径v最短路径最短路径q图的概念与基本术语q图的类型定义与存储q图的遍历q图的连通性与最小生成树Page 52022-11-112022-11-11欧拉欧拉17071707年出生在瑞士的巴塞尔城，年出生在瑞士的巴塞尔城，1919岁开始发岁开始发表论文，直到表论文，直到7676岁。几乎每一个数学领域都可以岁。几乎每一个数学领域都可以看到欧拉的名字，从初等几何的欧拉线
5、，多面体看到欧拉的名字，从初等几何的欧拉线，多面体的欧拉定理，立体解析几何的欧拉变换公式，四的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法到数论中的欧拉函数，微分方次方程的欧拉解法到数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数，复变函数的程的欧拉方程，级数论的欧拉常数，复变函数的欧拉公式等等。据统计他那不倦的一生，共写下欧拉公式等等。据统计他那不倦的一生，共写下了了886886本书籍和论文，其中分析、代数、数论占本书籍和论文，其中分析、代数、数论占40%40%，几何占，几何占18%18%，物理和力学占，物理和力学占28%28%，天文，天文学占学占11%11%，弹道学、航海
6、学、建筑学等占，弹道学、航海学、建筑学等占3%3%。17331733年，年仅年，年仅2626岁的欧拉担任了彼得堡科学院岁的欧拉担任了彼得堡科学院数学教授。数学教授。17411741年到柏林担任科学院物理数学所年到柏林担任科学院物理数学所所长，直到所长，直到17661766年，重回彼得堡，没有多久，完年，重回彼得堡，没有多久，完全失明。欧拉在数学上的建树很多，对著名的哥全失明。欧拉在数学上的建树很多，对著名的哥尼斯堡七桥问题的解答开创了图论的研究。尼斯堡七桥问题的解答开创了图论的研究。Page 72022-11-11能否从某个地方出发，穿过所有的桥仅一次能否从某个地方出发，穿过所有的桥仅一次后再
7、回到出发点？后再回到出发点？18世纪东普鲁士哥尼斯堡被普列戈世纪东普鲁士哥尼斯堡被普列戈尔河分为四块尔河分为四块,它们通过七座桥相互它们通过七座桥相互连接。当时该城的市民热衷于这样连接。当时该城的市民热衷于这样一个游戏：一个游戏：“一个散步者怎样才能一个散步者怎样才能从某块陆地出发，经每座桥一次且从某块陆地出发，经每座桥一次且仅一次回到出发点？仅一次回到出发点？”2022-11-11CADB七桥问题的图模型七桥问题的图模型欧拉回路的判定规则：欧拉回路的判定规则：1.如果通奇数桥的地方多于如果通奇数桥的地方多于两个，则不存在欧拉回路；两个，则不存在欧拉回路；2.如果只有两个地方通奇数如果只有两个
8、地方通奇数桥，可以从这两个地方之一桥，可以从这两个地方之一出发，找到欧拉回路；出发，找到欧拉回路；3.如果没有一个地方是通奇如果没有一个地方是通奇数桥的，则无论从哪里出发，数桥的，则无论从哪里出发，都能找到欧拉回路。都能找到欧拉回路。Page 92022-11-11最短路问题（SPPshortest path problem）一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。旅行商问题（TSPtraveling salesman
9、problem）一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商问题。中国邮递员问题（CPPChinese postman problem）一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？由于这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题。运输问题(transportation problem)某种原材料有N个产地，现在需要将原材料从产地运往M个使用这些原材料的工厂
10、。假定N个产地的产量和M家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？公路连接问题 某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？上述问题有两个共同的特点：一、它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化（optimization）问题；二、它们都易于用图形的形式直观地描述和表达，数学上把这种与图
11、相关的结构称为网络（network）。与图和网络相关的最优化问题就是。q线性表线性表v每个数据元素只有一个直接前驱和一个直接后继。每个数据元素只有一个直接前驱和一个直接后继。q树形结构树形结构v每个数据元素只有一个直接前驱，但可能有多个直接后继。每个数据元素只有一个直接前驱，但可能有多个直接后继。q图形结构图形结构v每个数据元素可能有多个直接前驱和多个直接后继。每个数据元素可能有多个直接前驱和多个直接后继。图是比线性表和树复杂的数据结构，广泛应用于计图是比线性表和树复杂的数据结构，广泛应用于计算机、逻辑学、物理、化学等领域。算机、逻辑学、物理、化学等领域。图的基本特性图的基本特性网络拓扑结构网
12、络拓扑结构社交网络社交网络图像处理图像处理物理化学结构物理化学结构电脑游戏电脑游戏2022-11-11图的定义图的定义图是由图是由顶点顶点的的有穷非空有穷非空集合和顶点之间集合和顶点之间边边的集合组的集合组成，通常表示为：成，通常表示为：G=(V，E)其中：其中：G表示一个图，表示一个图，V是图是图G中顶点的集合，中顶点的集合，E是是图图G中顶点之间边的集合。中顶点之间边的集合。在线性表中，元素个数可以为零，称为空表；在线性表中，元素个数可以为零，称为空表；在树中，结点个数可以为零，称为空树；在树中，结点个数可以为零，称为空树；在图中，顶点个数不能为零，但可以没有边。在图中，顶点个数不能为零，
13、但可以没有边。Page 15如果图的任意两个顶点之间的边都如果图的任意两个顶点之间的边都是是无向边，则称该图为无向边，则称该图为无向图无向图。若顶点若顶点vi和和vj之间的边没有方向，则之间的边没有方向，则称这条边为称这条边为无向边无向边，表示为，表示为(vi,vj)。若从顶点若从顶点vi到到vj的边有方向，则称这的边有方向，则称这条边为条边为有向边有向边，表示为，表示为。如果图的任意两个顶点之间的边都如果图的任意两个顶点之间的边都是是有向边，则称该图为有向边，则称该图为有向图有向图。V1V2V3V4V5V1V2V3V4图的基本术语图的基本术语 Page 16简单图：简单图：在图中，若不存在顶
14、点到其自身的边，且同在图中，若不存在顶点到其自身的边，且同一条边不重复出现一条边不重复出现。V3V4V5V1V2V3V4V5V1V2非简单图非简单图 非简单图非简单图 简单图简单图V1V2V3V4V5v 数据结构中讨论的都是简单图。数据结构中讨论的都是简单图。邻接、依附邻接、依附无向图无向图中，对于任意两个顶点中，对于任意两个顶点vi和顶点和顶点vj，若存在，若存在边边(vi，vj)，则称顶点，则称顶点vi和顶点和顶点vj互为邻接点，同时称边互为邻接点，同时称边(vi，vj)依附于顶点依附于顶点vi和顶点和顶点vj。V1V2V3V4V5V1的邻接点：的邻接点：V2的邻接点：的邻接点：V2、V4
15、V1、V3、V52022-11-11邻接、依附邻接、依附有向图有向图中，对于任意两个顶点中，对于任意两个顶点vi和顶点和顶点vj，若存在，若存在弧弧，则称顶点，则称顶点vi邻接到顶点邻接到顶点vj，顶点，顶点vj邻接自顶邻接自顶点点vi，同时称弧同时称弧依附于顶点依附于顶点vi和顶点和顶点vj。V1V2V3V4V1的邻接点：的邻接点：V3的邻接点：的邻接点：V2、V3V42022-11-11无向完全图无向完全图：在无向图中，如果任意两个顶点之：在无向图中，如果任意两个顶点之间都存在边，间都存在边，则称该图为无向完全图。则称该图为无向完全图。有向完全图有向完全图：在有向图中，如果任意两个顶点之：
16、在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，间都存在方向相反的两条弧，则称该图为有向完则称该图为有向完全图。全图。V1V2V3V1V2V3V42022-11-11含有含有n个顶点的无向完全图有个顶点的无向完全图有多少多少条边？条边？含有含有n个顶点的有向完全图有个顶点的有向完全图有多少多少条弧？条弧？含有含有n个顶点的无向完全图有个顶点的无向完全图有n(n-1)/2条边。条边。含有含有n个顶点的有向完全图有个顶点的有向完全图有n(n-1)条边。条边。V1V2V3V1V2V3V42022-11-11稀疏图：稀疏图：称边数很少的图为稀疏图；称边数很少的图为稀疏图；稠密图：稠密图：称边数
17、很多的图为稠密图。称边数很多的图为稠密图。顶点的度：顶点的度：在无向图中，顶点在无向图中，顶点v的的度度是指依附于该顶是指依附于该顶点的边数，通常记为点的边数，通常记为TD(v)。顶点的入度：顶点的入度：在有向图中，顶点在有向图中，顶点v的的入度入度是指以该顶是指以该顶点为点为弧头弧头的弧的数目，的弧的数目，记为记为ID(v)；顶点顶点的的出度：出度：在有向图中，顶点在有向图中，顶点v的的出度出度是指以该顶是指以该顶点为点为弧尾弧尾的弧的数目，记为的弧的数目，记为OD(v)。2022-11-11V1V2V3V4V5在具有在具有n个顶点、个顶点、e条边的无向图条边的无向图G中，各顶点中，各顶点的
18、度之和与边数之和的关系？的度之和与边数之和的关系？=niievTD12)(V1V2V3V4在具有在具有n个顶点、个顶点、e条边的有向图条边的有向图G中，各顶点中，各顶点的入度之和与各顶点的出度之和的关系？与边的入度之和与各顶点的出度之和的关系？与边数之和的关系？数之和的关系？evODvIDiiii=11)()(nn2022-11-11权：权：是指对边赋予的有意义的数值量。是指对边赋予的有意义的数值量。网：网：边上带权的图，也称网图。边上带权的图，也称网图。V1V2V3V42785图结构中的权和哈夫曼树中的权有什么区别？图结构中的权和哈夫曼树中的权有什么区别？2022-11-11路径：路径：在无
19、向图在无向图G=(V,E)中，从顶点中，从顶点vp到顶点到顶点vq之间之间的的路径路径是一个顶点序列是一个顶点序列(vp=vi0,vi1,vi2,vim=vq)，其，其中，中，(vij-1,vij)E（1jm）。若）。若G是有向图，则路径是有向图，则路径也是有方向的，顶点序列满足也是有方向的，顶点序列满足E。V1V2V3V4V5一般情况下，图中两个顶点之间的路径不唯一。一般情况下，图中两个顶点之间的路径不唯一。在什么情况下唯一？在什么情况下唯一？V1 到到V4的路径：的路径：V1 V4 V1 V2 V3 V4 V1 V2 V5V3 V42022-11-11路径长度：路径长度：非带权图非带权图路
20、径路径上边的上边的个数个数带权图带权图路径上路径上各边的各边的权之和权之和V1V2V3V4V5V1 V4：长度为：长度为1V1 V2 V3 V4：长度为：长度为3V1 V2 V5V3 V4：长度为：长度为42022-11-11路径长度：路径长度：非带权图非带权图路径路径上边的上边的个数个数带权图带权图路径上路径上各边的各边的权之和权之和V1 V4：长度为：长度为8V1 V2 V3 V4：长度为：长度为7V1 V2 V5V3 V4：长度为：长度为15V1V2V3V4V52563282022-11-11回路（环）回路（环）：第一个顶点和最后一个顶点相同的路径。：第一个顶点和最后一个顶点相同的路径。
21、简单路径：简单路径：序列中顶点不重复出现的路径。序列中顶点不重复出现的路径。简单回路（简单环）：简单回路（简单环）：除了第一个顶点和最后一个顶点外，除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。其余顶点不重复出现的回路。V1V2V3V4V5V1V2V3V42022-11-11子图：子图：若图若图G=（V，E），），G=（V，E），如果），如果V V 且且E E，则称图，则称图G是是G的子图。的子图。V1V2V3V4V5V1V2V3V4V5V1V3V42022-11-11连通图：连通图：在无向图中，如果从一个顶点在无向图中，如果从一个顶点vi到另一个顶到另一个顶点点vj(ij)有路径
22、，则称顶点有路径，则称顶点vi和和vj是连通的。如果图中是连通的。如果图中任意两个顶点都是连通的，则称该图是连通任意两个顶点都是连通的，则称该图是连通图。图。连通分量：连通分量：非连通图的极大连通子图称为连通分量。非连通图的极大连通子图称为连通分量。如何求得一个非连通图的连通分量如何求得一个非连通图的连通分量?1.含有极大含有极大顶点顶点数；数；2.依附于这些顶点的所有依附于这些顶点的所有边边。2022-11-11连通分量连通分量1 V1V2V3V4V5V6V7V1V2V4V5V3V6V7连通分量连通分量2v连通分量是对无向图的一种划分。连通分量是对无向图的一种划分。Page 322022-1
23、1-11强连通图：强连通图：在在有向图有向图中，对图中任意一对顶点中，对图中任意一对顶点vi和和vj(ij)，若从顶点，若从顶点vi到顶点到顶点vj和从顶点和从顶点vj到顶点到顶点vi均有路径均有路径，则称该有向图是强连通图。，则称该有向图是强连通图。强连通分量：强连通分量：非强连通图非强连通图的极大强连通子图。的极大强连通子图。如何求得一个有向非连通图的强连通分量如何求得一个有向非连通图的强连通分量?2022-11-11V1V2V3V4强连通分量强连通分量1 强连通分量强连通分量2V1V3V4V22022-11-11生成树：生成树：n个顶点的连通图个顶点的连通图G的生成树是包含的生成树是包含
24、G中中全全部顶点部顶点的一个极小连通的一个极小连通子图。子图。生成森林：生成森林：在非连通图中，由每个连通分量都可以得在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分到一棵生成树，这些连通分量的生成树就组成了一个量的生成树就组成了一个非连通图的非连通图的生成森林生成森林。如何理解极小连通子图如何理解极小连通子图?多多构成回路构成回路少少不连通不连通含有含有n-1条边条边2022-11-11V1V2V3V4V5V6V7V1V2V3V4V5V6V7V1V2V3V4V5V1V2V3V4V5生成树生成树生成森林生成森林q图的概念与基本术语q图的类型定义与存储q图的遍历q图的连通性与最小生成
25、树Page 362022-11-112022-11-11图的抽象数据类型定义如下：图的抽象数据类型定义如下：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)定义了弧定义了弧的意义的意义 或信息或信息 Page 382022-11-11G1=(G1=(V1V1,VR1VR1)V1=A,B,C,D,EV1=A,B,C
26、,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)Page 392022-11-11CreateGraph(&G,V,VR);CreateGraph(&G,V,VR);初始条件：初始条件：V V 是图的顶点集，是图的顶点集，VR VR 是图中弧的集合。是图中弧的集合。操作结果：按操作结果：按 V V 和和 VR VR 的定义的定义构造图构造图
27、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 相同的顶点，则相同的顶点，则返回该顶点返回该顶点 在图中位置在图中位置；否则返回其它信息。；否则返回其它信息。GetVex(G,v);GetVex(G,v);初始条件：图初始条件：图 G G 存在，存在，v v
28、是是 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 的的 邻接顶点。
29、邻接顶点。操作结果：操作结果：返回返回 v v 的（相对于的（相对于 w w 的）下一个邻接点。的）下一个邻接点。若若 w w 是是 v v 的最后一个邻接点，则返回的最后一个邻接点，则返回“空空”。Page 412022-11-11PutVex(&G,v,value);PutVex(&G,v,value);初始条件：图初始条件：图 G G 存在，存在，v v 是是 G G 中某个顶点。中某个顶点。操作结果：操作结果：对对 v v 赋值赋值 valuevalue。InsertVex(&G,v);InsertVex(&G,v);初始条件：图初始条件：图 G G 存在，存在，v v 和图中顶点有相
30、同特征。和图中顶点有相同特征。操作结果：在图操作结果：在图 G G 中中增添新顶点增添新顶点 v v。DeleteVex(&G,v);DeleteVex(&G,v);初始条件：图初始条件：图 G G 存在，存在，v v 是是 G G 中某个顶点。中某个顶点。操作结果：操作结果：删除删除 G G 中顶点中顶点 v v 及其相关的弧及其相关的弧。2022-11-11InsertArc(&G,v,w);InsertArc(&G,v,w);初始条件：图初始条件：图 G G 存在，存在，v v 和和 w w 是是 G G 中两个顶点。中两个顶点。操作结果：在操作结果：在 G G 中中增添弧增添弧，若，若
31、 G G 是是无向的，则还无向的，则还 增添对称弧增添对称弧。DeleteArc(&G,v,w);DeleteArc(&G,v,w);初始条件：图初始条件：图 G G 存在，存在，v v 和和 w w 是是 G G 中两个顶点。中两个顶点。操作结果：在操作结果：在 G G 中中删除弧删除弧，若若 G G 是是无向的，则还无向的，则还 删除对称弧删除对称弧。Page 432022-11-11DFSTraverse(G,Visit();DFSTraverse(G,Visit();初始条件：图初始条件：图 G G 存在，存在，Visit Visit 是顶点的应用函数。是顶点的应用函数。操作结果：对图
32、操作结果：对图 G G 进行进行深度优先深度优先遍历。遍历过程中对每遍历。遍历过程中对每 个顶点调用函数个顶点调用函数Visit Visit 一次且仅一次。一旦一次且仅一次。一旦 visit()visit()失败，则操作失败。失败，则操作失败。BFSTraverse(G,Visit();BFSTraverse(G,Visit();初始条件：图初始条件：图 G G 存在，存在，Visit Visit 是顶点的应用函数。是顶点的应用函数。操作结果：对图操作结果：对图 G G 进行进行广度优先广度优先遍历。遍历过程中对每遍历。遍历过程中对每 个顶点调用函数个顶点调用函数Visit Visit 一次且
33、仅一次。一旦一次且仅一次。一旦 visit()visit()失败，则操作失败。失败，则操作失败。ADT Graph ADT Graph2022-11-11是否可以采用顶点的顺序存储结构存储图是否可以采用顶点的顺序存储结构存储图?图的特点：顶点之间的关系是图的特点：顶点之间的关系是m:n，即，即任何两任何两个顶点之间都可能存在关系（边），无法通过个顶点之间都可能存在关系（边），无法通过存储位置表示这种任意的逻辑关系，所以，图存储位置表示这种任意的逻辑关系，所以，图无法采用顺序存储结构。无法采用顺序存储结构。如何存储图如何存储图?考虑图的定义，图是由顶点和边组成的，分别考虑图的定义，图是由顶点和边
34、组成的，分别考虑如何存储顶点、如何存储边。考虑如何存储顶点、如何存储边。q 数组表示法数组表示法(邻接矩阵邻接矩阵)v将图的将图的顶点信息存储在一个一维数组中顶点信息存储在一个一维数组中，并将它的，并将它的邻接矩阵存储在一个二维数组中邻接矩阵存储在一个二维数组中即构成图的数组表即构成图的数组表示。示。v假设图中顶点数为假设图中顶点数为n n，则邻接矩阵，则邻接矩阵A A定义为定义为=，其它0E(G)v,v或)v,(v若1,jijijiA网的邻接矩阵的定义为，当网的邻接矩阵的定义为，当v vi i到到v vj j有弧相邻接时，有弧相邻接时，a aijij的值应为该弧上的权值，否则为的值应为该弧上
35、的权值，否则为。1 1、图的邻接矩阵表示法、图的邻接矩阵表示法2022-11-11v图的数组图的数组(邻接矩阵邻接矩阵)存储表示存储表示#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 s
36、truct 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 typ
37、edef struct VertexType VertexType vexsMAX_VERTEX_NUMvexsMAX_VERTEX_NUM;/顶点信息顶点信息AdjMatrix AdjMatrix arcsarcs;/邻接矩阵邻接矩阵int int vexnum,arcnumvexnum,arcnum;/图的当前顶点数和弧图的当前顶点数和弧(边边)数数GraphKind GraphKind kindkind;/图的种类标志图的种类标志 MGraphMGraph;2022-11-11G1G1BDAC0 01 11 10 00 00 00 00 0G G1 1.a ar rc cs s=0 00
38、 00 01 11 10 00 00 0G1.vexs=A,B,C,DG1.vexnum=4G1.arcnum=4G1.kind=DGPage 482022-11-11V1V2V3V4V1 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 行元素之和。行元素之和。Page 492022-11-11V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc=V1 V2 V3
39、 V4V1V2V3V4如何求顶点如何求顶点 i 的入度？的入度？邻接矩阵的第邻接矩阵的第 i 列元素之和。列元素之和。2022-11-11V1V2V3V4V1 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 到顶点到顶点 j 是否存在边？是否存在边？测试邻接矩阵中相应位置的元素测试邻接矩阵中相应位置的元素arcij是否为是否为1。2022-11-11AECBDG2G20 01 10 01 10 01 10 01 10 01 1G G2 2.a ar rc cs s=0
40、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=UDG2022-11-11如何求顶点如何求顶点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行（或第行（或第i列）非零元素的个数。列）非零元素的个数。2022-11-11如何判断顶点如何判断顶点 i 和和 j 之间是否存在边？之间是否存在边？V1V3V4V2V1
41、V2 V3 V4vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc=V1 V2 V3 V4V1V2V3V4测试邻接矩阵中相应位置的元素测试邻接矩阵中相应位置的元素arcij是否为是否为1。Page 542022-11-11如何求顶点如何求顶点 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 的邻接点。
42、的邻接点。网图的邻接矩阵定义：网图的邻接矩阵定义：arcij wij 若若(vi,vj)E（或（或E）/0 若若i=j 其他其他V1V2V3V42785 2 5 8 7 arc=Page 562022-11-115 57 73 35 54 48 8G G3 3.a ar rc cs s=7 72 21 14 42 26 63 38 81 16 6A AD DE EB BC C7 75 53 31 18 86 64 42 2G3G3G3.vexs=A,B,C,D,EG3.vexnum=5G3.arcnum=8G3.kind=UDN2022-11-11v邻接矩阵表示的特点邻接矩阵表示的特点：无向图
43、无向图的邻接的邻接矩阵对称矩阵对称，可，可压缩存储压缩存储；有；有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邻接矩阵的优缺点邻接矩阵
44、的优缺点优点优点：容易判定顶点间有无边（弧）和计算顶点的度（出度、：容易判定顶点间有无边（弧）和计算顶点的度（出度、入度）。入度）。缺点缺点：边数较少时，空间浪费较大。：边数较少时，空间浪费较大。2022-11-112 2、图的邻接表表示法、图的邻接表表示法q 引入原因引入原因v邻接矩阵在稀疏图时空间浪费较大。邻接矩阵在稀疏图时空间浪费较大。q 实现实现v为图中为图中每个顶点建立一个单链表（边表）每个顶点建立一个单链表（边表），第，第i i个单链表中的结个单链表中的结点表示依附于顶点点表示依附于顶点ViVi的边（有向图中指以的边（有向图中指以ViVi为尾的弧）。为尾的弧）。v每个链表附设一个表
45、头结点（顶点结点）每个链表附设一个表头结点（顶点结点）。表结点表结点adjvexadjvexnextarcnextarcinfoinfo与与ViVi邻接的邻接的点在表头数点在表头数组中的位置组中的位置头结点头结点datadatafirstarcfirstarcPage 592022-11-11#define MAX_VERTEX_NUM 20;#define MAX_VERTEX_NUM 20;typedef struct ArcNode typedef struct ArcNode int int adjvex;adjvex;/该弧所指向的顶点的位置该弧所指向的顶点的位置struct Arc
46、Node 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_NUMAdjListM
47、AX_VERTEX_NUM;/顶点表顶点表typedef struct typedef struct AdjList AdjList verticesvertices;/顶点数组顶点数组int vexnum,arcnum;int vexnum,arcnum;/图的当前顶点数和弧数图的当前顶点数和弧数int kind;int kind;/图的种类标志图的种类标志 ALGraphALGraph;Page 602022-11-1110323101 V1 V2 V3 V40123vertex firstedgeV1V3V4V2边表中的结点表示什么？边表中的结点表示什么？每个结点对应图中的一条边，每个结
48、点对应图中的一条边，邻接表的空间复杂度为邻接表的空间复杂度为O(n+2e)。2022-11-1110323101 V1 V2 V3 V40123vertex firstedgeV1V3V4V2如何求顶点如何求顶点 i 的度？的度？顶点顶点i的边表中结点的个数。的边表中结点的个数。无向图的邻接表无向图的邻接表2022-11-11如何判断顶点如何判断顶点 i 和顶点和顶点 j之间是否存在边之间是否存在边?测试顶点测试顶点 i 的边表中是否存的边表中是否存在终点为在终点为 j 的结点。的结点。10323101 V1 V2 V3 V40123vertex firstedgeV1V3V4V2Page 6
49、3有向图的邻接表有向图的邻接表V1V2V3V41230 V1 V2 V3 V40123vertex firstedge如何求顶点如何求顶点 i 的出度？的出度？顶点顶点 i 的出边表中结点的个数。的出边表中结点的个数。2022-11-11V1V2V3V41230 V1 V2 V3 V40123vertex firstedge如何求顶点如何求顶点 i 的入度？的入度？各顶点的出边表中以顶点各顶点的出边表中以顶点 i 为为终点的结点个数。终点的结点个数。Page 652022-11-11V1V2V3V41230 V1 V2 V3 V40123vertex firstedge如何求顶点如何求顶点 i
50、 的所有邻接点？的所有邻接点？遍历顶点遍历顶点 i 的边表，该边表中的的边表，该边表中的所有终点都是顶点所有终点都是顶点 i 的邻接点。的邻接点。Page 662022-11-11网图的邻接表网图的邻接表V1V2V3V427852 1 V1 V2 V3 V40123vertex firstedge5 28 37 02022-11-11v优缺点优缺点优点优点：空间较省；无向图容易求各顶点的度；有向：空间较省；无向图容易求各顶点的度；有向图容易求顶点的出度；图容易求顶点的出度；缺点缺点：求有向图顶点的入度则不容易，要遍历整个：求有向图顶点的入度则不容易，要遍历整个表。表。为了求顶点的入度，有时可设
