[清华大学-数据结构-王红梅]第6章-专题1-图的逻辑结构

数据结构（C＋＋版）清华大学出版社专题1：图的逻辑结构123图的定义图的基本术语图的抽象数据类型定义4图的遍历操作数据结构（C＋＋版）清华大学出版社欧拉1707年出生在瑞士的巴塞尔城，19岁开始发表论文，直到76岁。几乎每一个数学领域都可以看到欧拉的名字，从初等几何的欧拉线，多面体的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法到数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数，变分学的欧拉方程，复变函数的欧拉公式等等。据统计他一生共写下了886本书籍和论文，其中分析、代数、数论占40%，几何占18%，物理和力学占28%，天文学占11%，弹道学、航海学、建筑学等占3%。欧拉对著名的哥尼斯堡七桥问题的解答开创了图论的研究。图论——欧拉数据结构（C＋＋版）清华大学出版社能否从某个地方出发，穿过所有的桥仅一次后再回到出发点？哥尼斯堡七桥问题数据结构（C＋＋版）清华大学出版社CADB七桥问题的图模型哥尼斯堡七桥问题欧拉回路的判定规则：1.如果通奇数桥的地方多于两个，则不存在欧拉回路；2.如果没有一个地方是通奇数桥的，则无论从哪里出发，都能找到欧拉回路。数据结构（C＋＋版）清华大学出版社图的定义6.1图的逻辑结构图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G=(V，E)其中：G表示一个图，V是图G中顶点的集合，E是图G中顶点之间边的集合。在线性表中，元素个数可以为零，称为空表；在树中，结点个数可以为零，称为空树；在图中，顶点个数不能为零，但可以没有边。数据结构（C＋＋版）清华大学出版社6.1图的逻辑结构如果图的任意两个顶点之间的边都是无向边，则称该图为无向图。若顶点vi和vj之间的边没有方向，则称这条边为无向边，表示为(vi,vj)。若从顶点vi到vj的边有方向，则称这条边为有向边，表示为vi,vj。如果图的任意两个顶点之间的边都是有向边，则称该图为有向图。V0V1V2V3V4V0V1V2V3数据结构（C＋＋版）清华大学出版社6.1图的逻辑结构图的基本术语简单图：在图中，若不存在顶点到其自身的边，且同一条边不重复出现。非简单图非简单图简单图数据结构中讨论的都是简单图。V0V1V2V3V4V0V1V2V3V4V0V1V2V3V4数据结构（C＋＋版）清华大学出版社6.1图的逻辑结构图的基本术语邻接、依附无向图中，对于任意两个顶点vi和顶点vj，若存在边(vi，vj)，则称顶点vi和顶点vj互为邻接点，同时称边(vi，vj)依附于顶点vi和顶点vj。V0的邻接点：V1、V3V1的邻接点：V0、V2、V4V0V1V2V3V4数据结构（C＋＋版）清华大学出版社6.1图的逻辑结构图的基本术语邻接、依附有向图中，对于任意两个顶点vi和顶点vj，若存在弧vi，vj，则称顶点vi邻接到顶点vj，顶点vj邻接自顶点vi，同时称弧vi，vj依附于顶点vi和顶点vj。V0V1V2V3V0的邻接点：V1、V2V2的邻接点：V3数据结构（C＋＋版）清华大学出版社在线性结构中，数据元素之间仅具有线性关系；在树结构中，结点之间具有层次关系；在图结构中，任意两个顶点之间都可能有关系。FECBAD线性结构ABCDEF树结构不同结构中逻辑关系的对比V0V1V2V3V4图结构数据结构（C＋＋版）清华大学出版社在线性结构中，元素之间的关系为前驱和后继；在树结构中，结点之间的关系为双亲和孩子；在图结构中，顶点之间的关系为邻接。FECBAD线性结构ABCDEF树结构不同结构中逻辑关系的对比V0V1V2V3V4图结构数据结构（C＋＋版）清华大学出版社无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。有向完全图：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。图的基本术语V0V1V2V0V1V2V36.1图的逻辑结构数据结构（C＋＋版）清华大学出版社含有n个顶点的无向完全图有多少条边？含有n个顶点的有向完全图有多少条弧？6.1图的逻辑结构含有n个顶点的无向完全图有n×(n-1)/2条边。含有n个顶点的有向完全图有n×(n-1)条边。V0V1V2V3V0V1V2数据结构（C＋＋版）清华大学出版社稀疏图：称边数很少的图为稀疏图；稠密图：称边数很多的图为稠密图。顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数，通常记为TD(v)。6.1图的逻辑结构图的基本术语顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID(v)；顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD(v)。数据结构（C＋＋版）清华大学出版社6.1图的逻辑结构图的基本术语在具有n个顶点、e条边的无向图G中，各顶点的度之和与边数之和的关系？==niievTD12)(V0V1V2V3V4数据结构（C＋＋版）清华大学出版社V0V1V2V36.1图的逻辑结构图的基本术语在具有n个顶点、e条边的有向图G中，各顶点的入度之和与各顶点的出度之和的关系？与边数之和的关系？evODvIDiiii====11)()(nn数据结构（C＋＋版）清华大学出版社权：是指对边赋予的有意义的数值量。网：边上带权的图，也称网图。6.1图的逻辑结构图的基本术语V0V1V2V32785哈夫曼树中的权与网图的权有何区别？7423数据结构（C＋＋版）清华大学出版社路径：在无向图G=(V,E)中，从顶点vp到顶点vq之间的路径是一个顶点序列(vp=vi0,vi1,vi2,…,vim=vq)，其中，(vij-1,vij)∈E（1≤j≤m）。若G是有向图，则路径也是有方向的，顶点序列满足vij-1,vij∈E。6.1图的逻辑结构图的基本术语一般情况下，图中的路径不惟一V0到V3的路径：V0V3V0V1V2V3V0V1V4V2V3V0V1V2V3V4数据结构（C＋＋版）清华大学出版社路径长度：6.1图的逻辑结构图的基本术语非带权图——路径上边的个数带权图——路径上各边的权之和V0V3：长度为1V0V1V2V3：长度为3V0V1V4V2V3：长度为4V0V1V2V3V4数据结构（C＋＋版）清华大学出版社路径长度：6.1图的逻辑结构图的基本术语非带权图——路径上边的个数带权图——路径上各边的权之和V0V3：长度为8V0V1V2V3：长度为7V0V1V4V2V3：长度为15V0V1V2V3V4256328数据结构（C＋＋版）清华大学出版社回路（环）：第一个顶点和最后一个顶点相同的路径。简单路径：序列中顶点不重复出现的路径。简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。6.1图的逻辑结构图的基本术语V0V1V2V3V4V0V1V2V3数据结构（C＋＋版）清华大学出版社子图：若图G=（V，E），G'=（V'，E'），如果V'V且E'E，则称图G'是G的子图。6.1图的逻辑结构图的基本术语V0V1V2V3V4V0V1V2V3V4V0V2V3数据结构（C＋＋版）清华大学出版社连通图：在无向图中，如果从一个顶点vi到另一个顶点vj(i≠j)有路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。连通分量：非连通图的极大连通子图称为连通分量。6.1图的逻辑结构图的基本术语如何求得一个非连通图的连通分量?1.含有极大顶点数；2.依附于这些顶点的所有边。数据结构（C＋＋版）清华大学出版社6.1图的逻辑结构V0V1V3V4V2V6V5V0V1V4V2V3V6V5图的基本术语连通分量是对无向图的一种划分数据结构（C＋＋版）清华大学出版社强连通图：在有向图中，对图中任意一对顶点vi和vj(i≠j)，若从顶点vi到顶点vj和从顶点vj到顶点vi均有路径，则称该有向图是强连通图。强连通分量：非强连通图的极大强连通子图。6.1图的逻辑结构图的基本术语如何求得一个非连通图的连通分量?数据结构（C＋＋版）清华大学出版社6.1图的逻辑结构图的基本术语V0V1V2V3V0V2V3V1数据结构（C＋＋版）清华大学出版社生成树：n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。生成森林：在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分量的生成树就组成了一个非连通图的生成森林。如何理解极小连通子图?6.1图的逻辑结构图的基本术语多——构成回路少——不连通含有n-1条边数据结构（C＋＋版）清华大学出版社V0V1V3V4V2V6V5V0V1V3V4V2V6V5V0V1V2V3V4V0V1V2V3V4生成树生成森林6.1图的逻辑结构数据结构（C＋＋版）清华大学出版社图的抽象数据类型定义ADTGraphData顶点的有穷非空集合和边的集合Operation6.1图的逻辑结构图是一种与具体应用密切相关的数据结构，它的基本操作往往随应用不同而有很大差别。下面给出一个图的抽象数据类型定义的例子，简单起见，基本操作仅包含图的遍历，针对具体应用，需要重新定义其基本操作。数据结构（C＋＋版）清华大学出版社InitGraph前置条件：图不存在输入：无功能：图的初始化输出：无后置条件：构造一个空的图DestroyGraph前置条件：图已存在输入：无功能：销毁图输出：无后置条件：释放图所占用的存储空间6.1图的逻辑结构数据结构（C＋＋版）清华大学出版社DFSTraverse前置条件：图已存在输入：遍历的起始顶点v功能：从顶点v出发深度优先遍历图输出：图中顶点的一个线性排列后置条件：图保持不变BFSTraverse前置条件：图已存在输入：遍历的起始顶点v功能：从顶点v出发广度优先遍历图输出：图中顶点的一个线性排列后置条件：图保持不变endADT6.1图的逻辑结构数据结构（C＋＋版）清华大学出版社图的遍历操作图的遍历是在从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次。6.1图的逻辑结构抽象操作，可以是对结点进行的各种处理，这里简化为输出结点的数据。数据结构（C＋＋版）清华大学出版社图的遍历操作要解决的关键问题①在图中，如何选取遍历的起始顶点？6.1图的逻辑结构在线性表中，数据元素在表中的编号就是元素在序列中的位置，因而其编号是唯一的；在树中，将结点按层序编号，由于树具有层次性，因而其层序编号也是唯一的；在图中，任何两个顶点之间都可能存在边，顶点是没有确定的先后次序的，所以，顶点的编号不唯一。为了定义操作的方便，将图中的顶点按任意顺序排列起来，比如，按顶点的存储顺序。解决方案：从编号小的顶点开始。数据结构（C＋＋版）清华大学出版社②从某个起点始可能到达不了所有其它顶点，怎么办？6.1图的逻辑结构图的遍历操作要解决的关键问题解决方案：多次调用从某顶点出发遍历图的算法。下面仅讨论从某顶点出发遍历图的算法。数据结构（C＋＋版）清华大学出版社③因图中可能存在回路，某些顶点可能会被重复访问，那么如何避免遍历不会因回路而陷入死循环。④在图中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，如何选取下一个要访问的顶点？6.1图的逻辑结构图的遍历操作要解决的关键问题解决方案：附设访问标志数组visited[n]。解决方案：深度优先遍历和广度优先遍历。数据结构（C＋＋版）清华大学出版社约翰·霍普克洛夫特1939年生于西雅图。1961年进入斯坦福大学研究生院深造，1962年获硕士学位，1964年获博士学位。毕业后先后在普林斯顿大学、斯坦福大学等著名学府工作，曾任职于一些科学研究机构，如NSF（美国科学基金会）和NRC（美国国家研究院）。罗伯特·陶尔扬1948年4月生于加利福尼亚州。1969年本科毕业，进入斯坦福大学研究生院，1972年获得博士学位。1986年图灵奖获得者6.1图的逻辑结构数据结构（C＋＋版）清华大学出版社1.深度优先遍历基本思想：⑴访问顶点v；⑵从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；⑶重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。6.1图的逻辑结构数据结构（C＋＋版）清华大学出版社深一层递归递归返回深度优先遍历序列?入栈序列?