第1章 图的基本概及图的存储精选文档.ppt

《第1章 图的基本概及图的存储精选文档.ppt》由会员分享，可在线阅读，更多相关《第1章 图的基本概及图的存储精选文档.ppt（68页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第1 1章章 图的基本概及图的存储图的基本概及图的存储本讲稿第一页，共六十八页引论 哥尼斯堡七桥问题又称Euler回路问题一条河流横贯哥尼斯堡城区，它有两条支流，在这两条支流之间夹着一块岛形地带，这里是城市的繁华地区。全城分为北、东、南、岛四个区，各区之间共有七座桥梁联系着。游人从两岸A、B、C、D中任何一个地方出发，要找到一条路线一条路线一条路线一条路线做到每座桥恰好都通过一次而最后返回原地做到每座桥恰好都通过一次而最后返回原地做到每座桥恰好都通过一次而最后返回原地做到每座桥恰好都通过一次而最后返回原地。1736年，Euler提出该问题的解不存在。本讲稿第二页，共六十八页1.1 基本概念图

2、论知识的一个特点就是概念特别多。本节只介绍一些基本的概念，其他概念(如割点、割边等)在其他章节里需要用到的时候再补充。本讲稿第三页，共六十八页1.1.1 有向图与无向图图图图图是由顶点集合顶点集合顶点集合顶点集合和顶点间关系集合(即边的集合边的集合边的集合边的集合或弧的集合弧的集合弧的集合弧的集合)组成的数据结构，通常可以用 来表示，其顶点集合和边的集合分别用 和 表示。G:graph V:vertex E:edge例如，图1.1(a)所示的图可以表示为 ，其中顶点集合顶点集合顶点集合顶点集合 ，集合中的元素为顶点的序号；边的集边的集边的集边的集合合合合为：。本讲稿第四页，共六十八页 无向图无

3、向图无向图无向图：图中的每条边没有方向图中的每条边没有方向图中的每条边没有方向图中的每条边没有方向。通常用符号(u,v)(u,v)表示顶点u到顶点v的一条无向边。有向图有向图有向图有向图：图中的每条边(通常可称为弧弧弧弧)都有方向方向方向方向。通常用符号表示顶点u到顶点v的一条有向边，其中u为这条边的起始顶起始顶起始顶起始顶点点点点(起点起点起点起点)，v为这条有向边的终止顶点终止顶点终止顶点终止顶点(终点终点终点终点)。本讲稿第五页，共六十八页1.1.2 完全图、稀疏图、稠密图 完全图完全图完全图完全图：任何一对顶点之间都有一条边，这种无向图称为完全图。有向完全图有向完全图有向完全图有向完全

4、图：任何一对顶点u和v，都存在和两条有向边，这种有向图称为有向完全图。本讲稿第六页，共六十八页 稀疏图稀疏图稀疏图稀疏图：边或弧的数目相对较少（远小于n(n-1)）的图称为稀疏图。稠密图稠密图稠密图稠密图：边或弧的数目相对较多的图（接近于完全图或有向完全图）称为稠密图。本讲稿第七页，共六十八页1.1.3 顶点与顶点、顶点与边的关系在无向图和有向图中，顶点和顶点之间的关系顶点和顶点之间的关系顶点和顶点之间的关系顶点和顶点之间的关系，以及顶点和顶点和顶点和顶点和边的关系边的关系边的关系边的关系是通过“邻接邻接邻接邻接”这个概念来表示的。在无向图 中，如果 是 中的元素，即是图中的一条无向边，则称顶

5、点 与顶点 互为邻接顶点互为邻接顶点互为邻接顶点互为邻接顶点，且边 依附依附依附依附于于于于顶点 和 。例如，在图1.1(a)所示的无向图 中，与顶点1相邻接相邻接相邻接相邻接的顶点有0,2,3,4,5，而依依依依附于附于附于附于顶点1的边有 ,和 。本讲稿第八页，共六十八页例如，在图1.1(b)所示的有向图 中，顶点1分别邻接到邻接到邻接到邻接到顶点2,4,5，邻接自邻接自邻接自邻接自顶点0和4；有向边 的顶点1邻接到邻接到邻接到邻接到顶点5，顶点5邻接自邻接自邻接自邻接自顶点1；顶点1分别与边 ,和 相关联相关联相关联相关联；等等。在有向图 中，如果 是 中的元素，即是图中的一条有向边，则

6、称顶点 邻接到邻接到邻接到邻接到顶点 ，顶点 邻接自邻接自邻接自邻接自顶点 ，边 与顶点 和 相关联相关联相关联相关联。本讲稿第九页，共六十八页1.1.4 顶点的度数及度序列与顶点度数有关的概念：度数度数度数度数、出度出度出度出度、入度入度入度入度、偶点偶点偶点偶点、奇点奇点奇点奇点；度序列度序列度序列度序列与Havel-HakimiHavel-Hakimi定理定理定理定理。本讲稿第十页，共六十八页顶点的度度度度(degree)(degree)：一个顶点一个顶点一个顶点一个顶点 的度是与它相关联的边的条数的度是与它相关联的边的条数的度是与它相关联的边的条数的度是与它相关联的边的条数，记作 。例

7、如在图1.1(a)所示的无向图 中，顶点1的度数为5，顶点4的度数为3，等等。在有向图中，顶点的度等于该顶点的出度与入度之和顶点的度等于该顶点的出度与入度之和顶点的度等于该顶点的出度与入度之和顶点的度等于该顶点的出度与入度之和。其中顶点 的出度出度出度出度是以 为起始顶点的有向边的条数，记作 ；顶点 的入度入度入度入度是以 为终点的有向边的条数，记作 。顶点 的度度度度 。例如在图1.1(b)所示的有向图 中，顶点1的出度数为3，入度为2，度为3+2=5。本讲稿第十一页，共六十八页在无向图和有向图中，边的个数和顶点的度都存在如下在无向图和有向图中，边的个数和顶点的度都存在如下关系关系(假设图假

8、设图 有有 个顶点，有个顶点，有 条边条边)：即在无向图和有向图中，所有顶点的度的总和，等于边的数目的两倍。这是因为，不管是有向图还是无向图，在统计所有顶点的度的总和时，每条边都统计了两次每条边都统计了两次每条边都统计了两次每条边都统计了两次。本讲稿第十二页，共六十八页 偶点偶点偶点偶点：度数为偶数度数为偶数度数为偶数度数为偶数的顶点；奇点奇点奇点奇点：度数为奇数度数为奇数度数为奇数度数为奇数的顶点；孤立顶点孤立顶点孤立顶点孤立顶点：度数为度数为度数为度数为0 0的顶点的顶点的顶点的顶点，称为孤立顶点。孤立顶点不与其他任何顶点邻接。叶叶叶叶（叶顶点叶顶点叶顶点叶顶点、端点端点端点端点）：度数为

9、度数为度数为度数为1 1的顶点的顶点的顶点的顶点，称为叶顶点叶顶点叶顶点叶顶点。其他顶点称为非叶顶点非叶顶点非叶顶点非叶顶点。图G的最小度最小度最小度最小度：图G所有顶点的最小的度数，记为(G)(G)。图G的最大度最大度最大度最大度：图G所有顶点的最大的度数，记为(G)(G)。本讲稿第十三页，共六十八页度序列与Havel-Hakimi定理 度序列度序列度序列度序列：若把图G所有顶点的度数排成一个序列s，则称s为图G的度序列。s:2,5,4,3,3,1s:2,5,4,3,3,1按顶点序号排序s:1,2,3,3,4,5s:1,2,3,3,4,5按度数非减顺序排列s:5,4,3,3,2,1s:5,4

10、,3,3,2,1按度数非增顺序排列两个问题：1)给定一个图，确定它的度序列给定一个图，确定它的度序列：很简单；2)逆问题逆问题逆问题逆问题：给定一个由非负整数组成的有限序列给定一个由非负整数组成的有限序列s s，判断，判断s s是否是否是某个图的度序列是某个图的度序列。本讲稿第十四页，共六十八页 序列是可图的序列是可图的序列是可图的序列是可图的：一个非负整数组成的有限序列如果是某个无向图的度序列，则称该序列是可图的。Havel-HakimiHavel-Hakimi定理定理定理定理：由非负整数组成的非增序列s：d1,d2,dn(n 2,d1 1)是可图的，当且仅当序列s1:d2 1,d3 1,d

11、d1+1 1,dd1+2,dn是可图的。序列s1中有n-1个非负整数，s序列中d1后的前d1个度数(即d2 dd1+1)减1后构成s1中的前d1个数。练习：练习：练习：练习：判断序列s:7,7,4,3,3,3,2,1是否是可图的。判断序列s:5,4,3,3,2,2,2,1,1,1是否是可图的。本讲稿第十五页，共六十八页Havel-Hakimi定理实际上给出了根据一个序列根据一个序列根据一个序列根据一个序列s s构造图（或判定构造图（或判定构造图（或判定构造图（或判定s s不不不不是可图的）的方法是可图的）的方法是可图的）的方法是可图的）的方法：把序列s按照非递增的顺序排序以后，其顺序为d1,d

12、2,dn；度数最大的顶点（设为v1），将它与度数次大的前与度数次大的前与度数次大的前与度数次大的前d d1 1个顶点之间连边个顶点之间连边个顶点之间连边个顶点之间连边，然后这个顶点就可以不管这个顶点就可以不管这个顶点就可以不管这个顶点就可以不管了，即在序列中删除首项d1，并把后面的d1个度数减1；再把剩下的序列重新按非递增顺序排序，按照上述过程连边；直到建出完整的图，或出现负度数等明显不合理的情况为止。序列s:3,3,2,2,1,1s:3,3,2,2,1,1本讲稿第十六页，共六十八页1.1.5 二部图与完全二部图 二部图二部图二部图二部图：设无向图为G(V,E)，它的顶点集合V包含两个没有公共

13、元素的子集：X=x1,x2,xs 和Y=y1,y2,yt，元素个数分别为s和t；并且xi与xj之间(1 i,j s)、yl与yr之间(1 l,r t)之间没有边连接，则称G为二部图二部图二部图二部图。完全二部图完全二部图完全二部图完全二部图：在二部图G中，如果顶点集合X中每个顶点xi与顶点集合Y中每个顶点yl都有边相连，则称G为完全二部图完全二部图完全二部图完全二部图，记为Ks,t，s和t分别为集合X和集合Y中的顶点个数。本讲稿第十七页，共六十八页1.1.6 图的同构 图的同构图的同构图的同构图的同构：设有两个图G1和G2，如果这两个图区别仅在于图的画法与（或）顶点的标号方式，则称它们是同构的

14、。意思就是说这两个图是同一个图。本讲稿第十八页，共六十八页1.1.7 子图与生成树设有两个图 和 ，如果 ，且 ，则称图 是图 的子图子图子图子图。例如，图1.8(a)、(b)所示的无向图都是图1.1(a)所示的无向图 的子图，而图1.8(c)、(d)所示的有向图都是图1.1(b)所示的有向图 的子图。本讲稿第十九页，共六十八页生成树生成树生成树生成树：一个无向连通图的生成树是它的包含所有顶点的极小连通子图包含所有顶点的极小连通子图包含所有顶点的极小连通子图包含所有顶点的极小连通子图，这里所谓的极小就是边的数目极小。如果图中有n个顶点，则生成树有n-1条边。例如，图1.1(a)所示的无向图 的

15、一个生成树如图1.9(a)所示。为了更形象地表示这个生成树，图(b)把它画成了以顶点0为根节点的树，图(c)把它画成了以顶点2为根节点的树。本讲稿第二十页，共六十八页1.1.8 路径路径是图论中一个很重要的概念。在图 中，若从顶点 出发，沿着一些边经过一些顶点 ,，到达顶点 ，则称顶点序列(,)为从顶点 到顶点 的一条路径路径路径路径。其中 ,为图 中的边，如果 是有向图，则 ,为图 中的有向边。例如，在图(a)所示的无向图 中，顶点序列(0,1,4,3)是从顶点0到顶点3的路径，其中(0,1),(1,4),(4,3)都是图 中的边；另外，顶点序列(0,2,3)也是顶点0到顶点3的路径。本讲稿

16、第二十一页，共六十八页在图(b)所示的有向图 中，顶点序列(2,4,1,5)是顶点2到顶点5的路径，其中,都是图 中的边；而顶点6到顶点0没有路径。本讲稿第二十二页，共六十八页简单路径简单路径简单路径简单路径：若路径上各顶点 ,均不互相重复，则这样的路径称为简单路径简单路径简单路径简单路径。例如，在图 中，路径(0,1,4,3)就是一条路径。回路回路回路回路：若路径上第一个顶点 与最后一个顶点 重合，则称这样的路径为回路回路回路回路。例如，图 中的路径(1,2,3,4,1)和图 中的路径(4,3,2,4)都是回路。本讲稿第二十三页，共六十八页1.1.9 连通性在无向图中，若从顶点从顶点 到到

17、有路径有路径，则称顶点 和 是连通连通连通连通的。如果无向图中任任任任意一对顶点都是连通意一对顶点都是连通意一对顶点都是连通意一对顶点都是连通的，则称此图是连通连通连通连通图图图图。如果一个无向图不是连通一个无向图不是连通的，则其极极大连通子图大连通子图称为连通分量连通分量连通分量连通分量。例如图(a)所示的无向图 就是一个连通图。在图 中，如果去掉边(1,5)，则剩下的图就是非连通的，且包含两个连通分量，一个是由顶点0,1,2,3,4组成的连通分量，另一个是由顶点5构成的连通分量。本讲稿第二十四页，共六十八页又如，图1.10所示的无向图就是非连通的。其中顶点A、B、C和E构成一个连通分量，顶

18、点D、F、G和H构成另一个连通分量。本讲稿第二十五页，共六十八页在有向图中，若对每一对顶点 和 ，都存在从 到 的路径，也存在从 到 的路径，则称此有向图为强连通图强连通图强连通图强连通图。例如图1.11所示的有向图就是强连通图。本讲稿第二十六页，共六十八页例如，图(a)所示的非强连通图包含4个强连通分量，如图(b)所示。其中，顶点1,2,3,4构成一个强连通分量，在这个子图中，每一对顶点 和 ，都存在从 到 的路径，也存在从 到 的路径；顶点0,5,6都自成一个强连通分量。对于非强连通图，其最大强连通子图最大强连通子图称为其强连通分量强连通分量强连通分量强连通分量。本讲稿第二十七页，共六十八

19、页1.1.10 权值、有向网与无向网权值权值：某些图的边具有与它相关的数，称为权值权值。这些权值可以表示从一个顶点到另一个顶点的距从一个顶点到另一个顶点的距离离、花费的代价花费的代价、所需的时间所需的时间等。如果一个图，如果一个图，其所有边都具有权值，其所有边都具有权值，则称为网络网络。根据网络中的边是否具有方向性，又可以分为有有向网向网和无向网无向网。网络可以用 表示。本讲稿第二十八页，共六十八页例如，图1.13(a)所示的无向网无向网可表示为 ，其中顶点集合为：边的集合为：在边的集合中，每个元素中的第第3个分量表个分量表示边的权值示边的权值。本讲稿第二十九页，共六十八页同样在边的集合中，每

20、个元素中的第第3个分量也表示边的权值个分量也表示边的权值。例如，图1.13(b)所示的有向网有向网可表示为 ，其中顶点集合为：边的集合为：本讲稿第三十页，共六十八页1.2 图的存储表示常用的存储表示方法有：1)邻接矩阵2)邻接表3)邻接多重表本讲稿第三十一页，共六十八页1.2.1 邻接矩阵在邻接矩阵中，除了一个记录各个顶点信息的顶点数组外，还有一个表示各顶点之间关系的矩阵，称为邻邻邻邻接矩阵接矩阵接矩阵接矩阵。本讲稿第三十二页，共六十八页1.有向图(无向图)的邻接矩阵设 是一个具有 个顶点的图，则图的邻接矩阵是一个二维数组 ，它的定义为：本讲稿第三十三页，共六十八页注意：注意：注意：注意：如果

21、图中存在环（连接某个顶点自身的边）和重边（多条边的起点一样，终点也一样）的情形，则无法用邻接矩阵存储。本讲稿第三十四页，共六十八页问题：问题：问题：问题：从图的邻接矩阵可以获得什么信息？(说明：邻接矩阵经过运算如乘方后，还可以获得更多的信息，具体请参见相关图论书籍)本讲稿第三十五页，共六十八页例例例例1.11.1 用邻接矩阵存储有向图，并输出各顶点的出度和入度。输入描述：输入描述：输入描述：输入描述：输入文件中包含多个测试数据，每个测试数据描述了一个有向图。每个测试数据的第一行为一个正整数正整数正整数正整数n n(1n100)，表示该有向图的顶点数目有向图的顶点数目有向图的顶点数目有向图的顶点

22、数目，顶点的序号从顶点的序号从顶点的序号从顶点的序号从1 1开始计起开始计起开始计起开始计起。接下来包含若干行，每行为两个正整数两个正整数两个正整数两个正整数，用空格隔开，分别表示一条边的起点和终点起点和终点起点和终点起点和终点。每条边出现一次且仅一次，图中不存在环和重边不存在环和重边不存在环和重边不存在环和重边。0 0代表该测试数据的结束。输入数据最后一行为最后一行为最后一行为最后一行为0 0，表示输入数据结束。输出描述：输出描述：输出描述：输出描述：对输入文件中的每个有向图，输出两行：第1行为n个正整数，表示每个顶点的出度；第2行也为n个正整数，表示每个顶点的入度。每两个正整数之间用一个空

23、格隔开两个正整数之间用一个空格隔开两个正整数之间用一个空格隔开两个正整数之间用一个空格隔开，每行的最后一个正整数之后没有空格。第二种输入方式!本讲稿第三十六页，共六十八页样例输出：样例输出：样例输出：样例输出：1 3 1 1 2 1 00 2 2 1 2 1 1样例输入：样例输入：样例输入：样例输入：71 22 32 52 63 54 35 25 36 50 00本讲稿第三十七页，共六十八页分析：分析：分析：分析：在程序中可以使用一个二维数组二维数组二维数组二维数组存储表示邻接矩阵。注意，输入文件中顶点的序号是从1开始计起的，而二维数组中的下标是从0开始计起，所以在将边的信息存入到邻接矩阵时，

24、需要将边的起点和终点的序号减1。在将有向边存储表示到邻接矩阵Edge中时，只需要将元素Edgeu-1v-1Edgeu-1v-1的值置为1。本题中的有向图都是无权图，邻接矩阵中每个元素要么为1，要么为0。第i个顶点的出度出度出度出度等于邻接矩阵中第i行所有元素中元素值为1的个数。把第i行所有元素值累加起来，得到的结果也是该顶点的出度。同理，在计算第i个顶点的入度入度入度入度时，也只需将第i列所有元素值累加起来累加起来即可。本讲稿第三十八页，共六十八页题目要求输出n个顶点的出度(入度)时，每两个正整数之间用一个空格每两个正整数之间用一个空格每两个正整数之间用一个空格每两个正整数之间用一个空格隔开隔

25、开隔开隔开，最后一个正整数之后没有空格。可以采取的策略是：输出第0个顶点的出度时前面没有空格，输出后面n-1个顶点的出度时输出一个空格。本讲稿第三十九页，共六十八页#include#include#define MAXN 100int EdgeMAXNMAXN;/邻接矩阵int main()int i,j;/循环变量int n;/顶点个数int u,v;/边的起点和终点int od,id;/顶点的出度和入度while(1)scanf(%d,&n);/读入顶点个数nif(n=0)break;memset(Edge,0,sizeof(Edge);while(1)scanf(%d%d,&u,&v);

26、/读入边的起点和终点if(u=0&v=0)break;Edgeu-1v-1=1;/构造邻接矩阵本讲稿第四十页，共六十八页for(i=0;in;i+)/求各顶点的出度od=0;for(j=0;jn;j+)od+=Edgeij;if(i=0)printf(%d,od);else printf(%d,od);printf(n);for(i=0;in;i+)/求各顶点的入度id=0;for(j=0;jn;j+)id+=Edgeji;if(i=0)printf(%d,id);else printf(%d,id);printf(n);return 0;本讲稿第四十一页，共六十八页例例例例1.2 1.2 青

27、蛙的邻居（Frogs Neighborhood）来源：POJ1659POJ1659题目描述：题目描述：题目描述：题目描述：未名湖附近共有n个大小湖泊L1,L2,.,Ln（其中包括未名湖），每个湖泊Li里住着一只青蛙Fi（1in）。如果湖泊Li和Lj之间有水路相连，则青青青青蛙蛙蛙蛙FiFi和和和和FjFj互称为邻居互称为邻居互称为邻居互称为邻居。现在已知每只青蛙的邻居数目已知每只青蛙的邻居数目已知每只青蛙的邻居数目已知每只青蛙的邻居数目x1,x2,.,xnx1,x2,.,xn，请你给出每两个湖泊之间的相连关系给出每两个湖泊之间的相连关系给出每两个湖泊之间的相连关系给出每两个湖泊之间的相连关系。

28、输出描述：输出描述：输出描述：输出描述：对输入的每组测试数据，如果不存在可能的相连关系，输出NO。否则输出YES，并用用用用nnnn的矩阵表示湖泊间的相邻关系的矩阵表示湖泊间的相邻关系的矩阵表示湖泊间的相邻关系的矩阵表示湖泊间的相邻关系，即如果湖泊i与湖泊j之间有水路相连，则第i行的第j个数字为1，否则为0。每两个数字之间输出一个空格。如果存在多种可能，只需给出一种符合条件的情形只需给出一种符合条件的情形只需给出一种符合条件的情形只需给出一种符合条件的情形。相邻两组测试数据之间输出一个空行。输入描述：输入描述：输入描述：输入描述：第一行是测试数据的组数t（0 t 20）。每组数据包括两行，第一

29、行是整数n（2 n 10），第二行是n个整数，x1,x2,.,xn（0 xi n）。本讲稿第四十二页，共六十八页样例输出：样例输出：样例输出：样例输出：YES0 1 1 1 1 0 01 0 0 1 1 0 01 0 0 0 0 0 01 1 0 0 1 1 11 1 0 1 0 1 00 0 0 1 1 0 00 0 0 1 0 0 0NO样例输入：样例输入：样例输入：样例输入：274 3 1 5 4 2 164 3 1 4 2 0本讲稿第四十三页，共六十八页分析分析分析分析1 1：本题的意思实际上是给定一个非负整数序列给定一个非负整数序列给定一个非负整数序列给定一个非负整数序列，问是不是一

30、个可图的序列是不是一个可图的序列是不是一个可图的序列是不是一个可图的序列，也就是说能不能根据这个序列构造一个图。这需要根据Havel-Hakimi定理中的方法来构图，并在构图中判断是否出现了不合理的情形。有以下两种不合理的情形：(1)某次对剩下序列排序后，最大的度数（设为某次对剩下序列排序后，最大的度数（设为某次对剩下序列排序后，最大的度数（设为某次对剩下序列排序后，最大的度数（设为d1d1）超过了剩下的顶点数）超过了剩下的顶点数）超过了剩下的顶点数）超过了剩下的顶点数；(2)对最大度数后面的d1个度数各减1后，出现了负数出现了负数出现了负数出现了负数。一旦出现了以上两种情形之一，即可判定该序

31、列不是可图的。分析分析分析分析2 2：如果一个序列是可图的，本题还要求输出构造得到的图的邻接矩阵，实现思路是：(1)为了确保顶点序号与输入时的度数顺序一致确保顶点序号与输入时的度数顺序一致确保顶点序号与输入时的度数顺序一致确保顶点序号与输入时的度数顺序一致，特意声明了一个vertex结构体，包含了顶点的度和序号两个成员。(2)每次对剩下的顶点按度数从大到小的顺序排序后，设最前面的顶点（即当前度数最大的顶点）序号为i、度数为d1，对后面d1个顶点每个顶点（序号设为j）度数减1，并连边，即在邻接矩阵在邻接矩阵在邻接矩阵在邻接矩阵EdgeEdge中设置中设置中设置中设置EdgeijEdgeij和和和

32、和EdgejiEdgeji为为为为1 1。本讲稿第四十四页，共六十八页#include#include#include#define N 15struct vertexint degree;/顶点的度int index;/顶点的序号vN;int cmp(const void*a,const void*b)return(vertex*)b)-degree-(vertex*)a)-degree;int main()int r,k,p,q;/循环变量int i,j;/顶点序号(用于确定图中边的两个顶点)int d1;/对剩下序列排序后第1个顶点(度数最大的顶点)的度数int T,n;/测试数据个数，

33、湖泊个数int EdgeNN,flag;/邻接矩阵，是否存在合理相邻关系的标志本讲稿第四十五页，共六十八页scanf(%d,&T);while(T-)scanf(%d,&n);for(i=0;in;i+)scanf(%d,&vi.degree);vi.index=i;/按输入顺序给每个湖泊编号memset(Edge,0,sizeof(Edge);flag=1;for(k=0;kn-k-1)flag=0;for(r=1;r=d1&flag;r+)j=vk+r.index;/后边d1个顶点每个顶点序号if(vk+r.degree=0)flag=0;vk+r.degree-;Edgeij=Edgej

34、i=1;本讲稿第四十六页，共六十八页if(flag)puts(YES);for(p=0;pn;p+)for(q=0;qn;q+)if(q)printf();printf(%d,Edgepq);puts();else puts(NO);if(T)puts();return 0;本讲稿第四十七页，共六十八页2.有向网(无向网)的邻接矩阵对于网络(即带权值的图)，邻接矩阵定义为：本讲稿第四十八页，共六十八页本讲稿第四十九页，共六十八页邻接矩阵的局限性尽管绝大多数图论的题目可以采用邻接矩阵存储图，但由于邻接矩阵无法表达环和重边的情形无法表达环和重边的情形无法表达环和重边的情形无法表达环和重边的情形，所

35、以有时不得不采用邻接表去存储图，详见欧拉回路的课件。另外，当图的边数图的边数图的边数图的边数(相对顶点个数相对顶点个数相对顶点个数相对顶点个数)较少较少较少较少时，使用邻接矩阵存储会浪费较多的存储空间，而用邻接表存储可以节省存储空间。本讲稿第五十页，共六十八页1.2.2 邻接表 邻接表：把同一个顶点发出的边链接在同一个称为边把同一个顶点发出的边链接在同一个称为边把同一个顶点发出的边链接在同一个称为边把同一个顶点发出的边链接在同一个称为边链表的单链表中链表的单链表中链表的单链表中链表的单链表中。(这种邻接表也称为出边表出边表出边表出边表)单链表的每个结点代表一条边，称为边结点边结点边结点边结点，

36、每个边结点有2个域。本讲稿第五十一页，共六十八页逆邻接表：也称为入边表入边表入边表入边表，顶点i的边链表中链接的是所有进入该顶点的边。适合求顶点的入度。本讲稿第五十二页，共六十八页无向图的邻接表v每条边在邻接表里出现2次。本讲稿第五十三页，共六十八页邻接表的实现以有向图为例介绍邻接表的实现方法。为了方便求解顶点的出度和入度，在实现时，把出边表和入边表同时包含在表示顶点的结构体中。#define MAXN 100struct ArcNode/边节点边节点 int adjvex;/边的另一个邻接点的序号边的另一个邻接点的序号ArcNode*nextarc;/指向下一个边节点的指针指向下一个边节点的

37、指针;struct VNode/顶点顶点int data;/顶点信息顶点信息ArcNode*head1;/出边表的表头指针出边表的表头指针ArcNode*head2;/入边表的表头指针入边表的表头指针;struct LGraph/图的邻接表存储结构图的邻接表存储结构VNode vertexsMAXN;/顶点数组顶点数组int vexnum,arcnum;/顶点数和边顶点数和边(弧弧)数数;LGraph lg;/图图(邻接表存储邻接表存储)本讲稿第五十四页，共六十八页采用邻接表存储图时构造有向图的方法void CreateLG()/采用邻接表存储表示采用邻接表存储表示,构造有向图构造有向图Gin

38、t i=0;/循环变量循环变量ArcNode*pi;/用来构造边链表的边结点指针用来构造边链表的边结点指针int v1,v2;/有向弧的两个顶点有向弧的两个顶点lg.vexnum=lg.arcnum=0;scanf(%d%d,&lg.vexnum,&lg.arcnum);/首先输入顶点个数和边数首先输入顶点个数和边数for(i=0;ilg.vexnum;i+)/初始化表头指针初始化表头指针lg.vertexsi.head1=lg.vertexsi.head2=NULL;/初始为空初始为空构造有向图G可以采取全局函数CreateLG()实现，代码如下：(在CreateLG()函数中，约定：构造邻

39、接表时，先输入顶点个数和边数，然后按“起点 终点”的格式输入每条有向边)本讲稿第五十五页，共六十八页for(i=0;iadjvex=v2;pi-nextarc=lg.vertexsv1.head1;/插入链表插入链表lg.vertexsv1.head1=pi;pi=new ArcNode;/假定有足够空间假定有足够空间pi-adjvex=v1;pi-nextarc=lg.vertexsv2.head2;/插入链表插入链表 lg.vertexsv2.head2=pi;/end of for/end of CreateLG本讲稿第五十六页，共六十八页释放各顶点边链表中的边结点void Delete

40、LG()/释放图释放图G的邻接表各顶点的边链表中的边结点所占的存储空间的邻接表各顶点的边链表中的边结点所占的存储空间int i;/循环变量循环变量ArcNode*pi;/用来指向边链表中各边节点的指针用来指向边链表中各边节点的指针for(i=0;inextarc;delete pi;pi=lg.vertexsi.head1;pi=lg.vertexsi.head2;while(pi!=NULL)/释放第释放第i个顶点入边表各边结点所占的存储空间个顶点入边表各边结点所占的存储空间lg.vertexsi.head2=pi-nextarc;delete pi;pi=lg.vertexsi.head2

41、;使用完有向图G的邻接表后，应该释放释放释放释放图G各顶点的边链表中的所有边结点所占的存储空间，可以使用DeleteLG()函数实现。本讲稿第五十七页，共六十八页例例例例1.3 1.3 用邻接表存储有向图，并输出各顶点的出度和入度。输入描述：输入描述：输入描述：输入描述：输入文件中包含多个测试数据，每个测试数据描述了一个无权有向图。每个测试数据的第一行为两个正整数n和m，1 n 100，1 m 500，分别表示该有向图的顶点数目和边数，顶点的序号从1开始计起。接下来有m行，每行为两个正整数，用空格隔开，分别表示一条边的起点和终点。每条边出现一次且仅一次，图中不存在自身环和重边。输入文件最后一行

42、为0 0，表示输入数据结束。输出描述：输出描述：输出描述：输出描述：对输入文件中的每个有向图，输出两行：第1行为n个正整数，表示每个顶点的出度；第2行也为n个正整数，表示每个顶点的入度。每两个正整数之间用一个空格隔开，每行的最后一个正整数之后没有空格。第二种输入方式!本讲稿第五十八页，共六十八页样例输出：样例输出：样例输出：样例输出：1 3 1 1 2 1 00 2 2 1 2 1 11 4 0 21 2 3 1样例输入：样例输入：样例输入：样例输入：7 91 22 32 52 63 54 35 25 46 74 71 42 12 22 32 34 24 30 0本讲稿第五十九页，共六十八页分

43、析：分析：分析：分析：用邻接表存储图，可以表示重边重边重边重边和环环环环的情形。例如，样例输入中第2个测试数据所描述的有向图及对应的邻接表如图1.22所示。本讲稿第六十页，共六十八页在图(a)所示的无向图中，有向边为环环环环，对应到图(b)所示的邻接表中，顶点1的入边表和出边表都有一个边结点，其adjvex分量也为1。另外，在图(a)所示的无向图中，和为重边重边重边重边，对应到图(b)所示的邻接表中，顶点1的出边表中，有两个边结点的adjvex分量均为2。统计第i个顶点的出度出度出度出度的方法是在其出边表中统计边结点的个数，统计第i个顶点的入度入度入度入度的方法是在其入边表中统计边结点的个数。

44、本讲稿第六十一页，共六十八页#include#include#define MAXN 100struct ArcNode/边结点int adjvex;/边(弧)的另一个邻接点的序号ArcNode*nextarc;/指向下一个边结点的指针;struct VNode/顶点int data;/顶点信息ArcNode*head1;/出边表的表头指针ArcNode*head2;/入边表的表头指针;struct LGraph/图的邻接表存储结构VNode vertexsMAXN;/顶点数组int vexnum,arcnum;/顶点数和边(弧)数;LGraph lg;/图(邻接表存储)本讲稿第六十二页，共六

45、十八页void CreateLG()/采用邻接表存储表示,构造有向图Gint i=0;/循环变量ArcNode*pi;/用来构造边链表的边结点指针int v1,v2;/有向弧的两个顶点for(i=0;ilg.vexnum;i+)/初始化表头指针lg.vertexsi.head1=lg.vertexsi.head2=NULL;/初始为“空”for(i=0;iadjvex=v2;pi-nextarc=lg.vertexsv1.head1;/插入链表lg.vertexsv1.head1=pi;pi=new ArcNode;/假定有足够空间pi-adjvex=v1;pi-nextarc=lg.vert

46、exsv2.head2;/插入链表 lg.vertexsv2.head2=pi;/end of for/end of CreateLG本讲稿第六十三页，共六十八页void DeleteLG()/释放图G的邻接表各顶点的边链表中的边结点所占的空间int i;/循环变量ArcNode*pi;/用来指向边链表中各边结点的指针for(i=0;inextarc;delete pi;pi=lg.vertexsi.head1;pi=lg.vertexsi.head2;while(pi!=NULL)/释放第i个顶点入边表各边结点所占的空间lg.vertexsi.head2=pi-nextarc;delete

47、pi;pi=lg.vertexsi.head2;本讲稿第六十四页，共六十八页int main()int i;/循环变量int id,od;/顶点的入度和出度ArcNode*pi;/用来遍历边链表的边结点指针while(1)lg.vexnum=lg.arcnum=0;/首先输入顶点个数和边数scanf(%d%d,&lg.vexnum,&lg.arcnum);if(lg.vexnum=0)break;/输入数据结束CreateLG();/构造有向图的邻接表结构for(i=0;inextarc;if(i=0)printf(%d,od);else printf(%d,od);本讲稿第六十五页，共六十八

48、页printf(n);for(i=0;inextarc;if(i=0)printf(%d,id);else printf(%d,id);printf(n);DeleteLG();/释放return 0;本讲稿第六十六页，共六十八页1.2.3 关于邻接矩阵和邻接表的进一步讨论1.1.存储方式对算法复杂度的影响存储方式对算法复杂度的影响存储方式对算法复杂度的影响存储方式对算法复杂度的影响本书后续章节会介绍图论里很多算法，存储方式的选择存储方式的选择存储方式的选择存储方式的选择对这些算法的时间复杂度和空间复杂度有直接影响。假设图中有n个顶点，e条边。时间复杂度：时间复杂度：时间复杂度：时间复杂度：邻

49、接表里直接存储了边的信息邻接表里直接存储了边的信息邻接表里直接存储了边的信息邻接表里直接存储了边的信息，浏览完所有的边，对有向图来说，时间复杂度复杂度是O(e)，对无向图是O(2e)。而邻接矩阵是间接邻接矩阵是间接邻接矩阵是间接邻接矩阵是间接存储边存储边存储边存储边，浏览完所有的边，复杂度是O(n2)。空间复杂度：空间复杂度：空间复杂度：空间复杂度：邻接表里除了存储e条边所对应的边结点外，还需要一个顶点数组，存储各顶点的顶点信息及各边链表的表头指针；而用邻接矩阵存储图，需要nn规模的存储单元。当边的数目相对于nn比较小时，邻接矩阵里存储了较多的无用信息，而用邻接表可以节省较多的存储空间。本讲稿

50、第六十七页，共六十八页2.2.在求解问题时可以灵活地存储表示图在求解问题时可以灵活地存储表示图在求解问题时可以灵活地存储表示图在求解问题时可以灵活地存储表示图在求解实际问题时，有时并不需要严格采用邻接矩阵或邻接表来存储图。例如，当图中顶点个数确定以后(这里假设顶点序号是连续的)，图的结构就唯一地取决于边的信息，因此可以把每条边的信息把每条边的信息把每条边的信息把每条边的信息(起点、终点、起点、终点、起点、终点、起点、终点、权值等权值等权值等权值等)存储到一个数组里存储到一个数组里存储到一个数组里存储到一个数组里，在针对该图进行某种处理时只需要访问该数组访问该数组访问该数组访问该数组中每个元素即