第12讲图的逻辑结构

1、第十二讲 图的逻辑结构 主要内容2. 图的基本术语图的基本术语3. 图的图的ADT4. 图的遍历操作图的遍历操作 图是由图是由顶点顶点的的有穷非空有穷非空集合和顶点之间集合和顶点之间边边的集合组的集合组成，通常表示为：成，通常表示为： G=(V，E)其中：其中：G表示一个图，表示一个图，V是图是图G中顶点的集合，中顶点的集合，E是是图图G中顶点之间边的集合。中顶点之间边的集合。 在线性表中，元素个数可以为零，称为空表；在线性表中，元素个数可以为零，称为空表；在树中，结点个数可以为零，称为空树；在树中，结点个数可以为零，称为空树；在图中，顶点个数不能为零，但可以没有边。在图中，顶点个数不能为零，

2、但可以没有边。图的定义 如果图的任意两个顶点之间的边都如果图的任意两个顶点之间的边都是无向边，则称该图为是无向边，则称该图为无向图无向图。若顶点若顶点vi和和vj之间的边没有方向，则之间的边没有方向，则称这条边为称这条边为无向边无向边，表示为，表示为(vi,vj)。若从顶点若从顶点vi到到vj的边有方向，则称这的边有方向，则称这条边为条边为有向边有向边，表示为，表示为。 如果图的任意两个顶点之间的边都如果图的任意两个顶点之间的边都是有向边，则称该图为是有向边，则称该图为有向图有向图。V1V2V3V4V5V1V2V3V4图的定义 主要内容1. 图的定义图的定义3. 图的图的ADT4. 图的遍历操

3、作图的遍历操作 简单图：简单图：在图中，若不存在顶点到其自身的边，且同在图中，若不存在顶点到其自身的边，且同一条边不重复出现。一条边不重复出现。V3V4V5V1V2V3V4V5V1V2非简单图非简单图 非简单图非简单图 简单图简单图V1V2V3V4V5v 数据结构中讨论的都是简单图。数据结构中讨论的都是简单图。图的基本术语 邻接、依附邻接、依附无向图无向图中，对于任意两个顶点中，对于任意两个顶点vi和顶点和顶点vj，若存在边，若存在边(vi，vj)，则称顶点，则称顶点vi和顶点和顶点vj互为邻接点，同时称边互为邻接点，同时称边(vi，vj)依附于顶点依附于顶点vi和顶点和顶点vj。V1V2V3

4、V4V5V1的邻接点：的邻接点： V2 、V4V2的邻接点：的邻接点： V1 、V3 、V5图的基本术语 邻接、依附邻接、依附有向图有向图中，对于任意两个顶点中，对于任意两个顶点vi和顶点和顶点vj，若存在弧，若存在弧，则称顶点，则称顶点vi邻接到顶点邻接到顶点vj，顶点，顶点vj邻接自顶邻接自顶点点vi，同时称弧，同时称弧依附于顶点依附于顶点vi和顶点和顶点vj 。 V1V2V3V4V1的邻接点：的邻接点： V2 、V3V3的邻接点：的邻接点： V4图的基本术语 在线性结构中，数据元素之间仅具有线性关系；在线性结构中，数据元素之间仅具有线性关系；在树结构中，结点之间具有层次关系；在树结构中，

5、结点之间具有层次关系；在图结构中，任意两个顶点之间都可能有关系。在图结构中，任意两个顶点之间都可能有关系。 FECBAD线性结构线性结构ABCDEF树结构树结构V1V2V3V4V5图结构图结构不同结构中逻辑关系的对比不同结构中逻辑关系的对比 在线性结构中，元素之间的关系为在线性结构中，元素之间的关系为前驱前驱和和后继后继；在树结构中，结点之间的关系为在树结构中，结点之间的关系为双亲双亲和和孩子孩子；在图结构中，顶点之间的关系为在图结构中，顶点之间的关系为邻接邻接。 FECBAD线性结构线性结构ABCDEF树结构树结构V1V2V3V4V5图结构图结构不同结构中逻辑关系的对比不同结构中逻辑关系的对

6、比 无向完全图无向完全图：在无向图中，如果任意两个顶点之间：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。都存在边，则称该图为无向完全图。有向完全图有向完全图：在有向图中，如果任意两个顶点之间：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图都存在方向相反的两条弧，则称该图为有向完全图。 V1V2V3V1V2V3V4图的基本术语 含有含有n个顶点的无向完全图有多少条边？个顶点的无向完全图有多少条边？含有含有n个顶点的有向完全图有多少条弧？个顶点的有向完全图有多少条弧？ 含有含有n个顶点的无向完全图有个顶点的无向完全图有n(n-1)/2条边。条边。

7、含有含有n个顶点的有向完全图有个顶点的有向完全图有n(n-1)条边。条边。 V1V2V3V1V2V3V4图的基本术语 稀疏图：稀疏图：称边数很少的图为稀疏图；称边数很少的图为稀疏图；稠密图：稠密图：称边数很多的图为稠密图。称边数很多的图为稠密图。顶点的度：顶点的度：在无向图中，顶点在无向图中，顶点v的的度度是指依附于该顶是指依附于该顶点的边数，通常记为点的边数，通常记为TD (v)。顶点的入度：顶点的入度：在有向图中，顶点在有向图中，顶点v的的入度入度是指以该顶是指以该顶点为弧头的弧的数目，记为点为弧头的弧的数目，记为ID (v)；顶点的出度：顶点的出度：在有向图中，顶点在有向图中，顶点v的的

8、出度出度是指以该顶是指以该顶点为弧尾的弧的数目，记为点为弧尾的弧的数目，记为OD (v)。图的基本术语 V1V2V3V4V5在具有在具有n个顶点、个顶点、e条边的无向图条边的无向图G中，各顶点中，各顶点的度之和与边数之和的关系？的度之和与边数之和的关系？=niievTD12)(图的基本术语 V1V2V3V4在具有在具有n个顶点、个顶点、e条边的有向图条边的有向图G中，各顶点中，各顶点的入度之和与各顶点的出度之和的关系？与边的入度之和与各顶点的出度之和的关系？与边数之和的关系？数之和的关系？evODvIDiiii=11)()(nn图的基本术语 权：权：是指对边赋予的有意义的数值量。是指对边赋予的

9、有意义的数值量。网：网：边上带权的图，也称网图。边上带权的图，也称网图。V1V2V3V42785图的基本术语 路径：路径：在无向图在无向图G=(V, E)中，从顶点中，从顶点vp到顶点到顶点vq之间的之间的路径路径是一个顶点序列是一个顶点序列(vp=vi0,vi1,vi2, , vim=vq)，其中，其中，(vij-1,vij)E（1jm）。若）。若G是有向图，则路径也是有是有向图，则路径也是有方向的，顶点序列满足方向的，顶点序列满足E。V1V2V3V4V5v一般情况下，图中的路径不惟一。一般情况下，图中的路径不惟一。V1 到到V4的路径：的路径： V1 V4 V1 V2 V3 V4 V1 V

10、2 V5V3 V4图的基本术语 非带权图非带权图路径路径上边的上边的个数个数带权图带权图路径上路径上各边的各边的权之和权之和V1V2V3V4V5V1 V4：长度为：长度为1V1 V2 V3 V4 ：长度为：长度为3V1 V2 V5V3 V4 ：长度为：长度为4图的基本术语 非带权图非带权图路径路径上边的上边的个数个数带权图带权图路径上路径上各边的各边的权之和权之和V1 V4：长度为：长度为8V1 V2 V3 V4 ：长度为：长度为7V1 V2 V5V3 V4 ：长度为：长度为15V1V2V3V4V5256328图的基本术语 V1V2V3V4V5V1V2V3V4图的基本术语 子图：子图：若图若图

11、G=（V，E），），G=（V，E），如果），如果V V 且且E E ，则称图，则称图G是是G的子图。的子图。V1V2V3V4V5V1V2V3V4V5V1V3V4图的基本术语 连通图：连通图：在无向图中，如果从一个顶点在无向图中，如果从一个顶点vi到另一个顶到另一个顶点点vj(ij)有路径，则称顶点有路径，则称顶点vi和和vj是连通的。如果图中是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。任意两个顶点都是连通的，则称该图是连通图。连通分量：连通分量：非连通图的极大连通子图称为连通分量。非连通图的极大连通子图称为连通分量。 如何求得一个非连通图的连通分量如何求得一个非连通图的连通分量

12、?1.含有极大含有极大顶点顶点数；数；2. 依附于这些顶点的所有依附于这些顶点的所有边边。图的基本术语 连通分量连通分量1 V1V2V3V4V5V6V7V1V2V4V5V3V6V7连通分量连通分量2v连通分量是对无向图的一种划分。连通分量是对无向图的一种划分。图的基本术语 强连通图：强连通图：在有向图中，对图中任意一对顶点在有向图中，对图中任意一对顶点vi和和vj (ij)，若从顶点，若从顶点vi到顶点到顶点vj和从顶点和从顶点vj到顶点到顶点vi均有路径均有路径，则称该有向图是强连通图。，则称该有向图是强连通图。强连通分量：强连通分量：非强连通图的极大强连通子图。非强连通图的极大强连通子图。

13、 如何求得一个非连通图的连通分量如何求得一个非连通图的连通分量?图的基本术语 V1V2V3V4强连通分量强连通分量1 强连通分量强连通分量2V1V3V4V2图的基本术语 生成树：生成树：n个顶点的连通图个顶点的连通图G的生成树是包含的生成树是包含G中中全全部顶点部顶点的一个极小连通子图。的一个极小连通子图。 生成森林：生成森林：在非连通图中，由每个连通分量都可以得在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分量的生成树就组成了一个到一棵生成树，这些连通分量的生成树就组成了一个非连通图的非连通图的生成森林生成森林。 如何理解极小连通子图如何理解极小连通子图?多多构成回路构成回路少少

14、不连通不连通含有含有n-1条边条边图的基本术语 V1V2V3V4V5V6V7V1V2V3V4V5V6V7V1V2V3V4V5V1V2V3V4V5生成树生成树生成森林生成森林图的基本术语 主要内容2. 图的基本术语图的基本术语1. 图的定义图的定义4. 图的遍历操作图的遍历操作 ADT GraphData 顶点的有穷非空集合和边的集合顶点的有穷非空集合和边的集合Operation InitGraph 前置条件：图不存在前置条件：图不存在 输入：无输入：无 功能：图的初始化功能：图的初始化 输出：无输出：无 后置条件：构造一个空的图后置条件：构造一个空的图图的抽象数据类型定义 DFSTravers

15、e 前置条件：图已存在前置条件：图已存在 输入：遍历的起始顶点输入：遍历的起始顶点v 功能：从顶点功能：从顶点v出发深度优先遍历图出发深度优先遍历图 输出：图中顶点的一个线性排列输出：图中顶点的一个线性排列 后置条件：图保持不变后置条件：图保持不变 BFSTraverse 前置条件：图已存在前置条件：图已存在 输入：遍历的起始顶点输入：遍历的起始顶点v 功能：从顶点功能：从顶点v出发广度优先遍历图出发广度优先遍历图 输出：图中顶点的一个线性排列输出：图中顶点的一个线性排列 后置条件：图保持不变后置条件：图保持不变图的抽象数据类型定义 DestroyGraph 前置条件：图已存在前置条件：图已存

16、在 输入：无输入：无 功能：销毁图功能：销毁图 输出：无输出：无 后置条件：释放图所占用的存储空间后置条件：释放图所占用的存储空间GetVex 前置条件：图已存在前置条件：图已存在 输入：顶点输入：顶点v 功能：在图中查找顶点功能：在图中查找顶点v的数据信息的数据信息 输出：顶点输出：顶点v的数据信息的数据信息 后置条件：图保持不变后置条件：图保持不变ADT Graph图的抽象数据类型定义 主要内容2. 图的基本术语图的基本术语1. 图的定义图的定义3. 图的图的ADT 图的遍历图的遍历是在从图中是在从图中某某一顶点出发，对图中所有顶点一顶点出发，对图中所有顶点访问一次且仅访问一次且仅访问访问

17、一次。一次。 抽象操作，可以是对结点进行的各种抽象操作，可以是对结点进行的各种处理，这里简化为输出结点的数据。处理，这里简化为输出结点的数据。图的遍历操作 在图中，如何选取遍历的起始顶点？在图中，如何选取遍历的起始顶点？在在线性表线性表中，数据元素在表中的编号就是元素在序列中中，数据元素在表中的编号就是元素在序列中的位置，因而其编号是唯一的；的位置，因而其编号是唯一的；在在树树中，将结点按层序编号，由于树具有层次性，因而中，将结点按层序编号，由于树具有层次性，因而其层序编号也是唯一的；其层序编号也是唯一的；在在图图中，任何两个顶点之间都可能存在边，顶点是没有中，任何两个顶点之间都可能存在边，顶

18、点是没有确定的先后次序的，所以，顶点的编号不唯一。确定的先后次序的，所以，顶点的编号不唯一。为了定义操作的方便，将图中的顶点按任意顺序排列起为了定义操作的方便，将图中的顶点按任意顺序排列起来，比如，按顶点的存储顺序。来，比如，按顶点的存储顺序。解决方案：从编号小的顶点开始解决方案：从编号小的顶点开始 。图的遍历操作要解决的关键问题 从某个起始点可能到达不了所有其它顶点从某个起始点可能到达不了所有其它顶点，怎么办？怎么办？解决方案：多次调用从某顶点出发遍历图的算法。解决方案：多次调用从某顶点出发遍历图的算法。v下面仅讨论从某顶点出发遍历图的算法。下面仅讨论从某顶点出发遍历图的算法。图的遍历操作要

19、解决的关键问题 因图中可能存在回路，某些顶点可能会被重复访问，因图中可能存在回路，某些顶点可能会被重复访问，那么如何避免遍历不会因回路而陷入死循环。那么如何避免遍历不会因回路而陷入死循环。 在图中，一个顶点可以和其它多个顶点相连，当这样在图中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，如何选取下一个要访问的顶点？的顶点访问过后，如何选取下一个要访问的顶点？ 解决方案：附设访问标志数组解决方案：附设访问标志数组visitedn 。解决方案：解决方案：深度深度优先遍历和优先遍历和广度广度优先遍历。优先遍历。图的遍历操作要解决的关键问题 约翰约翰霍普克洛夫特霍普克洛夫特1939年生于西年

20、生于西雅图。雅图。1961年进入斯坦福大学研究年进入斯坦福大学研究生院深造，生院深造，1962年获硕士学位，年获硕士学位，1964年获博士学位。毕业后先后在年获博士学位。毕业后先后在普林斯顿大学、斯坦福大学等著名普林斯顿大学、斯坦福大学等著名学府工作，也曾任职于一些科学研学府工作，也曾任职于一些科学研究机构如究机构如 NSF（美国科学基金会（美国科学基金会）和）和 NRC（美国国家研究院）。（美国国家研究院）。罗伯特罗伯特陶尔扬陶尔扬1948年年4月月30日生于日生于加利福尼亚州加利福尼亚州 。1969年本科毕业年本科毕业，进入斯坦福大学研究生院，进入斯坦福大学研究生院，1972年获得博士学位

21、。年获得博士学位。1986年图灵奖获得者 基本思想基本思想 ： 访问顶点访问顶点v； 从从v的未被访问的邻接点中选取一个顶点的未被访问的邻接点中选取一个顶点w，从从w出发进行深度优先遍历；出发进行深度优先遍历； 重复上述两步，直至图中所有和重复上述两步，直至图中所有和v有路径相通有路径相通的顶点都被访问到。的顶点都被访问到。 深度优先遍历 深一层递归深一层递归递归返回递归返回深度优先遍历序列深度优先遍历序列?入栈序列入栈序列?出栈序列出栈序列?V1V3V2V4V5V6V7V8 V1遍历序列：遍历序列：V1V2 V2V4 V4V5 V5深度优先遍历 深一层递归深一层递归递归返回递归返回深度优先遍历序列深度优先遍历序列?入栈序列入栈序列?出栈序列出栈序列?V1V3V2V4V5V6V7V8 V1遍历序列：遍历序列：V1V2 V2V4 V4V5V8 V8深度优先遍历 深一层递归深一层递归递归返回递归返回深度优先遍历序列深度优先遍历序列?入栈序列入栈序列?出栈序列出栈序列?V1V3V2V4V5V6V7V8 V1遍历序列：遍历序列：V1V2 V2V4 V4V5V8深度优先遍历 深一层递归深一层递归递归返回递归返回深度优先遍历序列深度优先遍历序列?入栈