《电子科大研究生图论课件-第1-2章基本概念-树.pptx》由会员分享，可在线阅读，更多相关《电子科大研究生图论课件-第1-2章基本概念-树.pptx（35页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、电子科大研究生图论电子科大研究生图论课件课件 制作人：时间：2024年X月CONTENTS目录目录第第1 1章章 基本概念基本概念第第2 2章章 树树第第3 3章章 图的遍历和最短路径图的遍历和最短路径 01010101第第1章章 基本概念基本概念 什么是图什么是图什么是图什么是图?图是用来描述事物之间关系的一种数学模型，由若干个点（顶点）和连接这些图是用来描述事物之间关系的一种数学模型，由若干个点（顶点）和连接这些图是用来描述事物之间关系的一种数学模型，由若干个点（顶点）和连接这些图是用来描述事物之间关系的一种数学模型，由若干个点（顶点）和连接这些点的线（边）构成。点的线（边）构成。点的线（
2、边）构成。点的线（边）构成。无向图和有向图无向图和有向图边没有方向无向图无向图边有方向有向图有向图 顶点和边顶点和边顶点和边顶点和边图中的顶点表示事物，边表示它们之间的关系。顶点之间的边可以有权值，也图中的顶点表示事物，边表示它们之间的关系。顶点之间的边可以有权值，也图中的顶点表示事物，边表示它们之间的关系。顶点之间的边可以有权值，也图中的顶点表示事物，边表示它们之间的关系。顶点之间的边可以有权值，也可以没有权值。可以没有权值。可以没有权值。可以没有权值。030102树中不存在环路没有回路没有回路其中有一个节点被指定为根节点有根有根对于任意两个节点，它们之间都有一条唯一路径连连通通树的应用树的
3、应用树是很多数据结构的基础，比如二叉树、平衡树、trie树等数据结构数据结构很多经典的算法都是建立在树的基础之上的，比如贪心算法、动态规划等算法设计算法设计树在网络协议中也有很多应用，比如生成树协议、路由选择算法等网络协议网络协议语法树是编译原理中重要的概念，它用于表示代码的语法结构编译原理编译原理非连通图非连通图非连通图非连通图存在一部分点无法到达其他点存在一部分点无法到达其他点连通分量连通分量连通分量连通分量图中的极大连通子图图中的极大连通子图 无向图和连通性无向图和连通性连通图连通图连通图连通图图中任意两点都能相互到达图中任意两点都能相互到达生成树生成树生成树是一种无向树，它包含了图中的
4、所有顶点，生成树是一种无向树，它包含了图中的所有顶点，并且可以通过去除任意一条边得到一颗不同的树。并且可以通过去除任意一条边得到一颗不同的树。非强连通图非强连通图非强连通图非强连通图存在一部分点无法到达其他点存在一部分点无法到达其他点强连通分量强连通分量强连通分量强连通分量图中的极大强连通子图图中的极大强连通子图 有向图和强连通性有向图和强连通性强连通图强连通图强连通图强连通图任意两点之间都有一条有向路径任意两点之间都有一条有向路径极大强连通子图极大强连通子图极大强连通子图极大强连通子图在一个有向图中，极大强连通子图是指强连通子图，它不能再加入任何一个新在一个有向图中，极大强连通子图是指强连通
5、子图，它不能再加入任何一个新在一个有向图中，极大强连通子图是指强连通子图，它不能再加入任何一个新在一个有向图中，极大强连通子图是指强连通子图，它不能再加入任何一个新的点或边而成为一个更大的强连通子图。的点或边而成为一个更大的强连通子图。的点或边而成为一个更大的强连通子图。的点或边而成为一个更大的强连通子图。02020202第第2章章 树树 树的定义和性质树的定义和性质树的定义树的定义树的性质树的性质二叉树、满二二叉树、满二叉树和完全二叉树和完全二叉树叉树 二叉树的遍历二叉树的遍历前序遍历前序遍历中序遍历中序遍历后序遍历后序遍历层次遍历层次遍历二叉树的性质二叉树的性质高度和深度高度和深度节点数、
6、叶子节点数、叶子节点数和非叶节点数和非叶节点数节点数平衡二叉树和平衡二叉树和AVLAVL树树 二叉搜索树二叉搜索树二叉搜索树的二叉搜索树的定义定义二叉搜索树的二叉搜索树的操作操作平衡二叉搜索平衡二叉搜索树和红黑树树和红黑树 树的定义树的定义树的定义树的定义树是一种重要的数据结构，它由一组节点和连接这些节点的边组成。在树中，树是一种重要的数据结构，它由一组节点和连接这些节点的边组成。在树中，树是一种重要的数据结构，它由一组节点和连接这些节点的边组成。在树中，树是一种重要的数据结构，它由一组节点和连接这些节点的边组成。在树中，每个节点最多有一个父节点，并可以有多个子节点。除根节点外，每个节点都每个
7、节点最多有一个父节点，并可以有多个子节点。除根节点外，每个节点都每个节点最多有一个父节点，并可以有多个子节点。除根节点外，每个节点都每个节点最多有一个父节点，并可以有多个子节点。除根节点外，每个节点都有且只有一个父节点。有且只有一个父节点。有且只有一个父节点。有且只有一个父节点。030102从根节点开始，先遍历左子树，再遍历右子树前序遍历前序遍历从根节点开始，先遍历左子树，再遍历右子树，最后遍历根节点后序遍后序遍历历从根节点开始，先遍历左子树，再遍历根节点，最后遍历右子树中序遍中序遍历历节点数、叶子节点数和非叶节点数节点数、叶子节点数和非叶节点数节点数、叶子节点数和非叶节点数节点数、叶子节点数
8、和非叶节点数节点数：树中所有节点的数量节点数：树中所有节点的数量叶子节点数：没有子节点的节点叶子节点数：没有子节点的节点非叶节点数：有子节点的节点非叶节点数：有子节点的节点平衡二叉树和平衡二叉树和平衡二叉树和平衡二叉树和AVLAVLAVLAVL树树树树平衡二叉树：任意节点的左右子树高度之差不超过平衡二叉树：任意节点的左右子树高度之差不超过1 1AVLAVL树：一种自平衡的二叉搜索树，满足任意节点的左右子树高度之差不超树：一种自平衡的二叉搜索树，满足任意节点的左右子树高度之差不超过过1 1，并且左右子树都是，并且左右子树都是AVLAVL树树 二叉树的性质二叉树的性质高度和深度高度和深度高度和深度
9、高度和深度高度：从根节点到最远的叶子节点的距离高度：从根节点到最远的叶子节点的距离深度：从根节点到某个节点的距离深度：从根节点到某个节点的距离二叉搜索树的定义二叉搜索树的定义二叉搜索树是一种二叉树，具有以下性质：二叉搜索树是一种二叉树，具有以下性质：1.1.若左子树不为空，则左子树上所有节点的值均若左子树不为空，则左子树上所有节点的值均小于它的根节点的值。小于它的根节点的值。2.2.若右子树不为空，则右子树上所有节点的值均若右子树不为空，则右子树上所有节点的值均大于它的根节点的值。大于它的根节点的值。3.3.左、右子树都是二叉搜索树。左、右子树都是二叉搜索树。4.4.没有键值相等的节点。没有键
10、值相等的节点。二叉搜索树的操作二叉搜索树的操作从根节点开始，按照左小右大的原则查找指定值查找查找从根节点开始，按照左小右大的原则找到插入位置，并将新节点插入插入插入分为三种情况：删除叶子节点、删除只有一个子节点的节点、删除有两个子节点的节点删除删除 030102保证二叉搜索树的左右子树高度差不超过1平衡二叉搜索树平衡二叉搜索树 保证二叉搜索树的左右子树高度差不超过2，并且应用广泛红红黑黑树树 03030303第第3章章 图图的遍的遍历历和最短路径和最短路径 图的遍历图的遍历概念深度优先搜索深度优先搜索概念广度优先搜索广度优先搜索概念应用：拓扑排应用：拓扑排序序 最短路径问题最短路径问题概念单源
11、最短路径单源最短路径问题问题算法过程DijkstraDijkstra算法算法概念负权边和负权负权边和负权回路问题回路问题 最小生成树问题最小生成树问题概念最小生成树问最小生成树问题的定义题的定义算法过程PrimPrim算法算法算法过程KruskalKruskal算法算法 二分图和匹配二分图和匹配概念二分图的定义二分图的定义概念最大匹配和最最大匹配和最大独立集大独立集算法过程匈牙利算法匈牙利算法 图的遍历图的遍历图的遍历图的遍历在图中从一个节点出发遍历图形成的过程叫做图的遍历。其中深度优先搜索和在图中从一个节点出发遍历图形成的过程叫做图的遍历。其中深度优先搜索和在图中从一个节点出发遍历图形成的过
12、程叫做图的遍历。其中深度优先搜索和在图中从一个节点出发遍历图形成的过程叫做图的遍历。其中深度优先搜索和广度优先搜索是两种常用的遍历方法。广度优先搜索是两种常用的遍历方法。广度优先搜索是两种常用的遍历方法。广度优先搜索是两种常用的遍历方法。030102将起点到各点的最短距离初始化为无穷大，起点到自身的距离为0初始化初始化如果通过当前节点前往邻居节点能够获得更短的距离，就更新邻居节点的距离更新距离更新距离寻找当前节点的所有邻居节点，并计算他们与起点的距离遍遍历邻历邻居居节节点点PrimPrim算法算法在一张连通加权图中，找出一棵生成树，使得树的所有边的权值之和最小概念概念从一个节点出发，每次选择当
13、前集合距离最近的点加入集合，直到所有点都加入集合为止算法过程算法过程 匈牙利算法匈牙利算法匈牙利算法匈牙利算法匈牙利算法是求解二分图最大匹配的经典算法。它在网络流中有着广泛的应用，匈牙利算法是求解二分图最大匹配的经典算法。它在网络流中有着广泛的应用，匈牙利算法是求解二分图最大匹配的经典算法。它在网络流中有着广泛的应用，匈牙利算法是求解二分图最大匹配的经典算法。它在网络流中有着广泛的应用，在实际中常用于解决婚姻稳定匹配等问题。在实际中常用于解决婚姻稳定匹配等问题。在实际中常用于解决婚姻稳定匹配等问题。在实际中常用于解决婚姻稳定匹配等问题。最大匹配和最大独立集最大匹配和最大独立集在二分图中，所匹配
14、的最大边数叫做最大匹配，最大独立集则是指不在同一条边上的最大节点集合概念概念匈牙利算法是最常用的解决二分图最大匹配问题的算法算法算法 Bellman-FordBellman-FordBellman-FordBellman-Ford算法算法算法算法适用于权重为负数的图适用于权重为负数的图时间复杂度为时间复杂度为O(nm)O(nm)属于属于DPDP算法算法FloydFloydFloydFloyd算法算法算法算法适用于任意权重的图适用于任意权重的图时间复杂度为时间复杂度为O(n)O(n)属于属于DPDP算法算法PrimPrimPrimPrim算法算法算法算法时间复杂度为时间复杂度为O(n)O(n)属于贪心算法属于贪心算法算法对比算法对比DijkstraDijkstraDijkstraDijkstra算法算法算法算法适用于权重为正数的图适用于权重为正数的图时间复杂度为时间复杂度为O(n)O(n)属于贪心算法属于贪心算法 谢谢观看！