数据结构与算法图

第4章图结构及其应用算法数据结构与算法Data Structures andgAlgorithms张岩海量数据计算研究中心哈工大计算机科学与技术学院第4章图结构及其应用算法2016/11/20Slide 4-2——图论欧拉欧拉1707年出生在瑞士的巴塞尔城，19岁开始发表论文，直到76岁。

几乎每一个数学领域都可以表论文直到76岁几乎每个数学领域都可以看到欧拉的名字，从初等几何的欧拉线，多面体的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法到数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数，变分学的欧拉方程，复变函数的欧拉公式等等。

据统计他那不倦的一生，共写下了886本书籍和论文，其中分析、代数、数论占40%，几何占18%，物理和力学占28%，天文学占11%，弹道学、航海学、力学占28%天文学占11%弹道学航海学建筑学等占3%。

1733年，年仅26岁的欧拉担任了彼得堡科学院学教授年到林担任科了彼得堡科学院数学教授。

1741年到柏林担任科学院物理数学所所长，直到1766年，重回彼得堡，没有多久，完全失明。

欧拉在数学上的建树很多，对著名的哥尼斯堡七桥问题的解答开创了图论的研究。

哥尼斯堡七桥问题能否从某个地方出发，穿过所有的桥仅一次后再回到出发点?学习目标图结构是一种非线性结构，反映了数据对象之间的任意关系，在计算机科学、数学和工程中有着非常广泛的应用。

了解图的定义及相关的术语，掌握图的逻辑结构及其特点；了解图的存储方法，重点掌握图的邻接矩阵和邻接表存储结构；掌握图的遍历方法，重点掌握图的遍历算法的实现；了解图的应用，重点掌握最小生成树、双连通性、强连通性、最短路径、拓扑排序和关键路径算法的基本思想、算法原理和实现过程。

本章主要内容4.1 图的基本概念4.2 图的存储结构4.3 图的遍历(搜索)4.4 最小生成树算法4.5 双连通性算法4.5双连通性算法4.6 强连通性算法4.7最短路径算法4.7 最短路径算法4.8 拓扑排序算法4.9 关键路径算法本章小结本章的知识点结构基本的数据结构（ADT）图无向图有向图加权图网络图（无向图、有向图；加权图----网络）知识点结构定义及相关术语逻辑结构及其特征ADT定义A逻辑结构静态的结构基本操作（算法）存储结构（描述）ADT基本动态的操作存储结构特点存储结构的定义ADT实现数据结构存储结构静态的结构操作（算法）实现算法的性能应用:最小生成树最短路径拓扑排序和关键路径动态的操作,,图的搜索(遍历)算法是有关图问题的重要核心算法！4.1基本定义4.1定义1 图(Graph)图是由顶点（vertex）的有穷非空集合和顶点之间边（edge）的集合组成的一种数据结构，通常表示为：G = (V，E)其中：G表示一个图，V是图G中顶点的集合，E是图G中顶点之间边的集合。

数据结构与算法课程设计报告课程设计题目：图的算法实现专业班级：信息与计算科学1002班目录摘要 (1)1、引言 (1)2、需求分析 (1)3、概要设计 (2)4、详细设计 (4)5、程序设计 (10)6、运行结果 (18)7、总结体会 (19)摘要(题目): 图的算法实现实验内容图的算法实现问题描述：（1）将图的信息建立文件；（2）从文件读入图的信息，建立邻接矩阵和邻接表；（3）实现Prim、Kruskal、Dijkstra和拓扑排序算法。

关键字:邻接矩阵、Dijkstra和拓扑排序算法1.引言本次数据结构课程设计共完成图的存储结构的建立、Prim、Kruskal、Dijkstra 和拓扑排序算法等问题。

通过本次课程设计，可以巩固和加深对数据结构的理解，通过上机和程序调试，加深对课本知识的理解和熟练实践操作。

（1）通过本课程的学习，能够熟练掌握数据结构中图的几种基本操作；（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。

使用语言：CPrim算法思想：从连通网N={V,E}中的某一顶点v0出发，选择与它关联的具有最小权值的边(v0,v)，将其顶点加入到生成树的顶点集合V中。

以后每一步从一个顶点在V中，而另一个顶点不在V中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合V中。

如此继续下去，直到网中的所有顶点都加入到生成树顶点集合V中为止。

拓扑排序算法思想：1、从有向图中选取一个没有前驱的顶点，并输出之；2、从有向图中删去此顶点以及所有以它为尾的弧；重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。

没有前驱-- 入度为零，删除顶点及以它为尾的弧-- 弧头顶点的入度减1。

2.需求分析1、通过键盘输入建立一个新的有向带权图，建立相应的文件；2、对建立的有向带权图进行处理，要求具有如下功能：（1）用邻接矩阵和邻接表的存储结构输出该有向带权图，并生成相应的输出结果；（2）用Prim、Kruskal算法实现对图的最小生成树的求解，并输出相应的输出结果；（3）用Dijkstra算法实现对图中从某个源点到其余各顶点的最短路径的求解，并输出相应的输出结果；（4）实现该图的拓扑排序算法。

数据结构与算法第一节数据结构及算法概述一、数据结构图、四类基本结构的示意图【要点】 1 .数据元素是数据的基本单位。

2 .数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

3 .4类基本的规律结构:集合、线性结构、树形结构和网状结构。

4 .4种数据存储方式：挨次、链式、索引和散列。

【例题•单选题】(2022年义省信用社聘请考试真题)下列说法不正确的是()OA.数据元素是数据的基本单位B.数据项是数据中不行分割的最小标志单位 C.数据可由若干个数据元素构成D.数据项可由若干个数据元素构成『正确答案』D『答案解析』数据元素是数据的基本单位，在计算机程序中通常被作为一个整体进 行考虑和处理。

一个数据元素可由若干个数据项组成。

数据项是不行分割的、含有独立 意义的最小数据单位。

因此D 选项不正确。

二、算法O ——O ——O ——O ——O ⑹树型结构⑹线性结构 (d)图形结构算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。

算法的特性：有穷性、确定性、可行性、输入和输出。

【要点】评价算法优劣标准：正确性、可读性、健壮性、高效率与低存储量需求。

其次节线性表线性表是n (n≥0)个数据元素al, a2,…，an组成的有限序列,n=0时称为空表。

非空的线性表，有以下特征：L有且仅有一个开头结点al,没有直接前趋，有且仅有一个直接后继a2。

2.有且仅有一个终结结点an,没有直接后继，有且仅有一个直接前趋a-。

3.其余的内部结点ai (2WiWnT)都有且仅有一个直接前趋a-和一个直接后继3i+ι o线性表的链式存储包括单链表、循环链表和双链表。

head 头结点百结点尾结点【留意】与单链表的插入和删除操作不同的是，在双链表中插入和删除须同时修改两个方向上的指针。

第三节栈和队列一、栈栈是一种“特别的”线性表，这种线性表中的插入和删除运算限定在表的某一端进行。

不含任何数据元素的栈称为空栈。

数据结构与算法——克鲁斯卡尔（Kruskal）算法⽬录应⽤场景-公交站问题某城市新增 7 个站点(A, B, C, D, E, F, G) ，现在需要修路把 7 个站点连通，各个站点的距离⽤边线表⽰(权) ，⽐如 A – B 距离 12公⾥问：如何修路保证各个站点都能连通，并且总的修建公路总⾥程最短?如上图所⽰：要求和前⾯的普利姆算法中的修路问题是⼀样的要求，只是换了⼀个背景。

克鲁斯卡尔算法介绍克鲁斯卡尔(Kruskal)算法，是⽤来求加权连通图的最⼩⽣成树的算法。

基本思想：按照权值从⼩到⼤的顺序选择n-1条边，并保证这n-1条边不构成回路具体做法：⾸先构造⼀个只含 n 个顶点的森林然后依权值从⼩到⼤从连通⽹中选择边加⼊到森林中，并使森林中不产⽣回路，直⾄森林变成⼀棵树为⽌克鲁斯卡尔算法图解在含有 n 个顶点的连通图中选择 n-1 条边，构成⼀棵极⼩连通⼦图，并使该连通⼦图中 n-1 条边上权值之和达到最⼩，则称其为连通⽹的最⼩⽣成树。

例如，对于如上图 G4 所⽰的连通⽹可以有多棵权值总和不相同的⽣成树。

有多种不同的连通⽅式，但是哪⼀种权值才是最优的呢？下⾯是克鲁斯卡尔算法的图解步骤：以上图 G4 为例，来对克鲁斯卡尔进⾏演⽰(假设，⽤数组 R 保存最⼩⽣成树结果)。

第 1 步：将边E,F [2]加⼊ R 中。

边E,F的权值最⼩，因此将它加⼊到最⼩⽣成树结果 R 中。

第 2 步：将边C,D [3]加⼊ R 中。

上⼀步操作之后，边C,D的权值最⼩，因此将它加⼊到最⼩⽣成树结果 R 中。

第 3 步：将边D,E [4]加⼊ R 中。

同理，权值最⼩第 4 步：将边B,F [7]加⼊ R 中。

上⼀步操作之后，边C,E [5]的权值最⼩，但C,E会和已有的边构成回路；因此，跳过边C,E。

同理，跳过边C,F [6]。

将边B,F加⼊到最⼩⽣成树结果R中。

第 5 步：将边E,G [8]加⼊ R 中。

同理第 6 步：将边A,B [12]加⼊ R 中。

数据结构与算法算法定义特征类型时间复杂度空间复杂度数据结构逻辑结构线性结构线性表栈特征队列非线性结构树-二叉树满二叉树完全二叉树特征先序、中序、后序网状存储结构循序存储链式存储其他查找顺序二分排序希尔排序堆排序快速排序学习途径学习网站中国大学mooc哔哩哔哩CSDN 博客园PTA学习书籍《数据结构——用C语言描述》严蔚敏著《数据结构》《数据结构与算法分析：C语言描述《大话数据结构》《从问题到程序——程序设计与C语言引论》具体算法结构线性表顺序表必须掌握(增、删、改、查、销)静态顺序表动态顺序表链表必须掌握(增、删、改、查、销)单链表无头单链表有头单链表链表相关试题链表的逆序无头链表插入和删除链表带环问题(次)顺序表与链表的仇缺点栈和队列流程1、栈和队列的创建2、栈和队列的初始化3、栈的增容4、入栈，出栈，入队，出队5、取得栈顶，队头和队尾元索6、求栈和队列的大小、判断栈和队列是否为空说明栈是一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作栈顺序栈链栈栈的应用队列顺序队列循环队列优先级队列队列的应用树形结构树的基本概念1、节点2、节点呃度3、叶子节点4、分支节点5、祖先节点6、双亲节点7、兄弟节点8、孩子节点9、树的深度树的表示方法1、双亲表示法2、孩子表示法3、双亲孩子表示法4、孩子兄弟表示法树的存储形式树的应用二叉树二叉树的概念二叉树的性质二叉树的存储1、顺序存储结构2、链式存储结构二叉树的基本搡作二叉树的创建二叉树的遍历(递归和非递归)前序遍历中序遍历后序遍历二叉树的增、删、改、查、销二叉树相关试题线索化二叉树。