数据结构图论部分.ppt

《数据结构图论部分.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、DataStructure第七章图100865109/21/20211学习目标领会图的类型定义。熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。熟练掌握图的两种遍历算法。理解各种图的应用问题的算法。重点和难点重点：图的各种应用问题的算法都比较经典，注意理解各种图的算法及其应用场合。9/21/20212知识点图的类型定义图的存储表示图的深度优先搜索遍历和广度优先搜索遍历无向网的最小生成树拓扑排序关键路径最短路径9/21/20213欧拉1707年出生在瑞士的巴塞尔城，19岁开始发表论文，直到76岁。几乎每一个数学

2、领域都可以看到欧拉的名字，从初等几何的欧拉线，多面体的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法到数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数，变分学的欧拉方程，复变函数的欧拉公式等等。据统计他那不倦的一生，共写下了886本书籍和论文，其中分析、代数、数论占40%，几何占18%，物理和力学占28%，天文学占11%，弹道学、航海学、建筑学等占3%。1733年，年仅26岁的欧拉担任了彼得堡科学院数学教授。1741年到柏林担任科学院物理数学所所长，直到1766年，重回彼得堡，没有多久，完全失明。欧拉在数学上的建树

3、很多，对著名的哥尼斯堡七桥问题的解答开创了图论的研究。图论——欧拉9/21/20214能否从某个地方出发，穿过所有的桥仅一次后再回到出发点？哥尼斯堡七桥问题9/21/20215CADB七桥问题的图模型欧拉回路的判定规则：1.如果通奇数桥的地方多于两个，则不存在欧拉回路；2.如果只有两个地方通奇数桥，可以从这两个地方之一出发，找到欧拉回路；3.如果没有一个地方是通奇数桥的，则无论从哪里出发，都能找到欧拉回路。9/21/20216图的定义图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G=(V，E)其中：G表示一个图，V是

4、图G中顶点的集合，E是图G中顶点之间边的集合。在线性表中，元素个数可以为零，称为空表；在树中，结点个数可以为零，称为空树；在图中，顶点个数不能为零，但可以没有边。7.1图的定义和术语9/21/20217线性表每个数据元素只有一个直接前驱和一个直接后继。树形结构每个数据元素只有一个直接前驱，但可能有多个直接后继。图形结构每个数据元素可能有多个直接前驱和多个直接后继。图是比线性表和树复杂的数据结构，广泛应用于语言学、逻辑学、物理、化学等领域。9/21/20218如果图的任意两个顶点之间的边都是无向边，则称该图为无向图。若顶点vi和vj

5、之间的边没有方向，则称这条边为无向边，表示为(vi,vj)。若从顶点vi到vj的边有方向，则称这条边为有向边，表示为。如果图的任意两个顶点之间的边都是有向边，则称该图为有向图。V1V2V3V4V5V1V2V3V4图的基本术语9/21/20219简单图：在图中，若不存在顶点到其自身的边，且同一条边不重复出现。V3V4V5V1V2V3V4V5V1V2非简单图非简单图简单图V1V2V3V4V5数据结构中讨论的都是简单图。9/21/202110图的基本术语邻接、依附无向图中，对于任意两个顶点vi和顶点vj，若存在边(vi，v

6、j)，则称顶点vi和顶点vj互为邻接点，同时称边(vi，vj)依附于顶点vi和顶点vj。V1V2V3V4V5V1的邻接点：V2、V4V2的邻接点：V1、V3、V59/21/202111图的基本术语邻接、依附有向图中，对于任意两个顶点vi和顶点vj，若存在弧，则称顶点vi邻接到顶点vj，顶点vj邻接自顶点vi，同时称弧依附于顶点vi和顶点vj。V1V2V3V4V1的邻接点：V2、V3V3的邻接点：V49/21/202112无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。有向完全

7、图：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。图的基本术语V1V2V3V1V2V3V49/21/202113含有n个顶点的无向完全图有多少条边？含有n个顶点的有向完全图有多少条弧？含有n个顶点的无向完全图有n×(n-1)/2条边。含有n个顶点的有向完全图有n×(n-1)条边。V1V2V3V1V2V3V49/21/202114稀疏图：称边数很少的图为稀疏图；稠密图：称边数很多的图为稠密图。顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数，通常记为TD(v)。图的基本术语顶点的入度：在有向图中

8、，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID(v)；顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD(v)。9/21/202115V1V2V3V4V5图的基本术语在具有n个顶点、e条边的无向图G中，各顶点的度之和与