哈工大数据结构课件第4章图结构及其应用算法

第4章图结构及其应用算法数据结构与算法数据结构与算法数据结构与算法数据结构与算法DataStructuresandAlgorithmsg张岩张岩海量数据计算研究中心哈工大计算机科学与技术学院张岩Slide4-12013/11/62013/11/6哈工大计算机科学与技术学院第第44章章图结构及其应用算法图结构及其应用算法第第44章章图结构及其应用算法图结构及其应用算法2013/11/6Slide4-2第4章图结构及其应用算法图论图论————欧拉欧拉图论图论欧拉欧拉欧拉1707年出生在瑞士的巴塞尔城，19岁开始发表论文直到76岁几乎每个数学领域都可以表论文，直到76岁。几乎每一个数学领域都可以看到欧拉的名字，从初等几何的欧拉线，多面体的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法到数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数，变分学的欧拉方程，复变函数的欧拉公式等等。据统计他那拉方程，复变函数的欧拉公式等等。据统计他那不倦的一生，共写下了886本书籍和论文，其中分析、代数、数论占40%，几何占18%，物理和力学占28%天文学占11%弹道学航海学力学占28%，天文学占11%，弹道学、航海学、建筑学等占3%。1733年，年仅26岁的欧拉担任了彼得堡科学院数学教授。1741年到柏林担任科了彼得堡科学院学教授年到林担任科学院物理数学所所长，直到1766年，重回彼得堡，没有多久，完全失明。欧拉在数学上的建树很多，对著名的哥尼斯堡七桥问题的解答开创了图论的哈工大计算机科学与技术学院张岩Slide4-32013/11/6对著名的哥尼斯堡七桥问题的解答开创了图论的研究。第4章图结构及其应用算法哥尼斯堡七桥问题哥尼斯堡七桥问题能否从某个地方出发，穿过所有的桥仅一次后再回到出发点?哈工大计算机科学与技术学院张岩Slide4-42013/11/6能否从某个地方出发，穿过所有的桥仅一次后再回到出发点?第4章图结构及其应用算法学习目标学习目标图结构是一种非线性结构，反映了数据对象之间的任意关系，在计算机科学、数学和工程中有着非常广泛的应用。，在计算机科学、数学和工程中有着非常广泛的应用。了解图的定义及相关的术语，掌握图的逻辑结构及其特点；了解图的存储方法，重点掌握图的邻接矩阵和邻接表存储结了解图的存储方法，重点掌握图的邻接矩阵和邻接表存储结构；掌握图的遍历方法，重点掌握图的遍历算法的实现；掌握图的遍历方法，重点掌握图的遍历算法的实现；了解图的应用，重点掌握最小生成树、双连通性、强连通性、最短路径、拓扑排序和关键路径算法的基本思想、算法原、最短路径、拓扑排序和关键路径算法的基本思想、算法原理和实现过程。哈工大计算机科学与技术学院张岩Slide4-52013/11/6第4章图结构及其应用算法本章主要内容本章主要内容本章主要内容本章主要内容4.1图的基本概念4.2图的存储结构4.3图的遍历(搜索)4.4最小生成树算法4.5最短路径算法4.5最短路径算法4.6拓扑排序算法4.7关键路径算法4.7关键路径算法4.8双连通性算法4.9强连通性算法本章小结哈工大计算机科学与技术学院张岩Slide4-62013/11/6本章小结第4章图结构及其应用算法本章的知识点结构本章的知识点结构本章的知识点结构本章的知识点结构基本的数据结构（ADT）图无向图有向图加权图网络图（无向图、有向图；加权图----网络）知识点结构定义及相关术语ADT定义定义及相关术语逻辑结构及其特征基本操作（算法）ADT定义A逻辑结构静态的结构动态的操作基本操作（算法）存储结构（描述）存储结构特点ADT实现ADT基本数据动态的操作静态的结构存储结构特点操作（算法）实现存储结构的定义ADT实现数据结构存储结构静态的结构动态的操作操作（算法）实现算法的性能应用:最小生成树,最短路径,拓扑排序和关键路径动态的操作哈工大计算机科学与技术学院张岩Slide4-72013/11/6,,图的遍历(搜索)算法是有关图问题的重要核心算法！第4章图结构及其应用算法4.1基本定义4.1基本定义定义1图(Graph)图是由顶点（）的有穷非空集合和顶点之间边（图是由顶点（vertex）的有穷非空集合和顶点之间边（edge）的集合组成的一种数据结构，通常表示为：，G=(V，E)其中：G表示一个图，V是图G中顶点的集合，E是图G中顶点之间边的集合。之间边的集合。顶点表示数据对象；边表示数据对象之间的关系。v1v2v1v2v3v3哈工大计算机科学与技术学院张岩Slide4-82013/11/6v4v5v4v5第4章图结构及其应用算法4.1基本定义(cont.)4.1基本定义(cont.)定义1图无向图：无向图：若顶点vi和vj之间的边没有方向，则称这条边为无向边，表示为(vi,vj)。v1v2这条边为无向边，表示为(vi,vj)。如果图的任意两个顶点之间的边都是无向边，则称该图为无向图。v3无向边，则称该图为无向图。有向图：若顶点v和v之间的边有方向，则称这vvv4v5若顶点vi和vj之间的边有方向，则称这条边为有向边(弧)，表示为vi,vj：弧尾，弧首(头)v1v2弧尾，弧首(头)如果图的任意两个顶点之间的边都是有向边，则称该图为有向图。v3vv哈工大计算机科学与技术学院张岩Slide4-92013/11/6有向边，则称该图为有向图。v4v5第4章图结构及其应用算法4.1基本定义(cont.)4.1基本定义(cont.)无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。，则称该图为无向完全图。有向完全图：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。向相反的两条弧，则称该图为有向完全图。v1v2v1v2v3v4v3v4含有n个顶点的无向完全图有多少条边？含有个顶点的有向完全图有多少条弧？哈工大计算机科学与技术学院张岩Slide4-102013/11/6含有n个顶点的有向完全图有多少条弧？第4章图结构及其应用算法4.1基本定义(cont.)4.1基本定义(cont.)定义1图邻接、依附在无向图中，对于任意两个顶点vi和顶点vj，若存在边(vi，vj)，则称顶点vi和顶点相邻，互为邻接点，同时称v1v2和顶点vj相邻，互为邻接点，同时称边(vi，vj)依附于顶点vi和顶点vj。如：的邻接点：v3如：v2的邻接点：v1,v3,v5在有向图中，对于任意两个顶点和v4v5v1v2在有向图中，对于任意两个顶点vi和顶点vj，若存在有向边vi，vj，则称顶点v邻接到顶点v，顶点v邻接于顶v3顶点vi邻接到顶点vj，顶点vj邻接于顶点vi，同时称弧vi，vj依附于顶点vi和顶点vj。哈工大计算机科学与技术学院张岩Slide4-112013/11/6v4v5j如：v1的邻接到v2，v1邻接于v4第4章图结构及其应用算法4.1基本定义(cont.)4.1基本定义(cont.)定义2度(Dgree)v1v2v1v2v3v4v5v3v4v5顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数，通常记为D(v)。4545数，通常记为()。顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID(v)；头的弧的数目，记为()；顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD(v)。哈工大计算机科学与技术学院张岩Slide4-122013/11/6尾的弧的数目，记为()。在有向图中，D(v)=ID(v)+OD(v)第4章图结构及其应用算法4.1基本定义(cont.)4.1基本定义(cont.)定义2度(Dgree)v1v2v1v2v3v4v5v3v4v5在具有n个顶点、e条边的无向图G中，各顶点的度之和与边数之和的关系？4545数之和的关系？在具有n个顶点、e条边的有向图G中，各顶点的入度之和与2evDii1)(n在具有n个顶点、e条边的有向图G中，各顶点的入度之和与各顶点的出度之和的关系？与边数之和的关系？nn哈工大计算机科学与技术学院张岩Slide4-132013/11/6evIDii1)(nvODii1)(n第4章图结构及其应用算法4.1基本定义(cont.)4.1基本定义(cont.)定义3路径（Path）和路径长度、简单路和简单回路在无向图G(VE)中，若存在一个顶点序列在无向图G=(V,E)中，若存在一个顶点序列vp,vi1,vi2,…vim,vq，使得（vp,vi1）,（vi1,vi2）,…,（vim,vq）∈E(G)，则称顶点v路到v有一条路径。称顶点vp路到vq有一条路径。在有向图G=(V,E)中，若存在一个顶点序列vp,vi1,vi2,…vim,vq，使得有向边vp,vi1,vi1,vi2,…,vim,vq∈E(G)，则称,q，使得有向边p,i1,i1,i2,,im,q()，则称顶点vp路到vq有一条有向路径。非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。简单路径：若路径上各顶点v1,v2,...,vm均互不相同,则称这样1,2,,m,的路径为简单路径。简单回路：若路径上第一个顶点v1与最后一个顶点vm重合,则称这样的简单路径为简单回路或环。哈工大计算机科学与技术学院张岩Slide4-142013/11/6称这样的简单路径为简单回路或环。第4章图结构及其应用算法4.1基本定义(cont.)4.1基本定义(cont.)定义4图的连通性连通图与连通分量连通图与连通分量顶点的连通性：在无向图中,若从顶点vi到顶点vj(i≠j)有路径则称顶点与是连通的。,则称顶点vi与vj是连通的。连通图：如果一个无向图中任意一对顶点都是连通的,则称此图是连通图。此图是连通图。连通分量：非连通图的极大连通子图叫做连通分量。1.含有极大顶点数；有边v1v2v12.依附于这些顶点的所有边.v1v1哈工大计算机科学与技术学院张岩Slide4-152013/11/6v3v4第4章图结构及其应用算法4.1基本定义(cont.)4.1基本定义(cont.)定义4图的连通性强连通图与强连通分量强连通图与强连通分量顶点的强连通性：在有向图中,若对于每一对顶点vi和vj都存在一条从到和从到的有向路径则称顶点与(i≠j),都存在一条从vi到vj和从vj到vi的有向路径,则称顶点vi与vj是强连通的。强连通图：如果一个有向图中任意一对顶点都是强连通的强连通图：如果一个有向图中任意一对顶点都是强连通的,则称此有向图是强连通图。强连通分量非强连通图的极大强连通子图叫做强连通分量强连通分量:非强连通图的极大强连通子图叫做强连通分量v1v2v3哈工大计算机科学与技术学院张岩Slide4-162013/11/6v4v5第4章图结构及其应用算法4.1基本定义(cont.)4.1基本定义(cont.)图的操作设图G(VE)，图上定义的基本操作如下：设图G=(V,E)，图上定义的基本操作如下：NEWNODE(G)：建立一个新顶点，V=V∪{v}DELNODE(Gv)：删除顶点v以及与之相关联的所有边DELNODE(G,v)：删除顶点v以及与之相关联的所有边SETSUCC(G,v1,v2):增加一条边，E=E∪(v1,v2),V=VDELSUCC(Gv1v2)：删除边（v1v2）V不变DELSUCC(G,v1,v2)：删除边（v1,v2）,V不变SUCC(G,v1,v2)：求出v的所有直接后继结点PRED(Gv)：求出v的所有直接前导结点PRED(G,v)：求出v的所有直接前导结点ISEDGE(G,v1,v2)：判断（v1,v2）∈EFirstAdjVex(Gv):顶点v的第一个邻接顶点FirstAdjVex(G,v):顶点v的第一个邻接顶点NextAdjVex(G,v,w)：顶点v的某个邻接点w的下一个邻接顶点。哈工大计算机科学与技术学院张岩Slide4-172013/11/6点。第4章图结构及其应用算法4.1基本定义(cont.)4.1基本定义(cont.)不同逻辑结构之间的比较F