图形表示与数据结构57页PPT

二叉树的性质
二叉树具有五种基本形态，即空二叉树、只有一个根节点的二叉树、只有左子树或右子 树的二叉树、以及左右子树均有的二叉树。此外，二叉树还具有一些重要性质，如二叉
树的第i层最多有2^(i-1)个节点（i>=1），深度为k的二叉树最多有2^k-1个节点 （k>=1）等。
二叉树的遍历算法
先序遍历
先访问根节点，然后遍 历左子树，最后遍历右
05
图论基础及图的存储结构
图论基础概念介绍
图的基本概念
由顶点（Vertex）和边（Edge）组成的数 据结构，表示对象及其之间的关系。
图的遍历
通过某种方式访问图中所有顶点的过程， 常见的遍历算法有深度优先遍历（DFS）和 广度优先遍历（BFS）。
有向图与无向图
根据边是否有方向，图可分为有向图和无 向图。
时间复杂度
平均时间复杂度和最坏时 间复杂度均为O(n)。
适用场景
适用于数据量较小或数据 无序的情况。
查找算法设计之二分查找法
算法思想
在有序数组中，取中间元素与目标元素比较，若相等则查找成功；若目标元素小于中间元素， 则在左半部分继续查找；若目标元素大于中间元素，则在右半部分继续查找。
时间复杂度
平均时间复杂度和最坏时间复杂度均为O(log n)。
连通图与连通分量
在无向图中，任意两个顶点之间都存在路 径，则称该图是连通图；否则，称该图的 极大连通子图为连通分量。
顶点的度
在无向图中，顶点的度是与该顶点相关联 的边的数目；在有向图中，顶点的度分为 入度和出度。
图的存储结构之邻接矩阵法
邻接矩阵表示法
用一个二维数组表示图中顶点之 间的关系，若顶点i与顶点j之间 存在一条边，则数组元素值为1

Page 4
2020/11/24
哥尼斯堡七桥问题
能否从某个地方出发，穿过所有的桥仅一次 后再回到出发点？
Page 5
2020/11/24
七桥问题的图模型
欧拉回路的判定规则：
1.如果通奇数桥的地方多于
C
两个，则不存在欧拉回路；
2.如果只有两个地方通奇数
桥，可以从这两个地方之一
A
B 出发，找到欧拉回路；
V4 是有向边，则称该图为有向图。
Page 9
2020/11/24
简单图：在图中，若不存在顶点到其自身的边，且同 一条边不重复出现。
V1
V2
V3
V4
V5
非简单图
V1
V2
V3
V4
V5
非简单图
V1
V2
V3
V4
V5
简单图
❖ 数据结构中讨论的都是简单图。
Page 10
2020/11/24
图的基本术语
邻接、依附
DeleteVex(&G, v); 初始条件：图 G 存在，v 是 G 中某个顶点。 操作结果：删除 G 中顶点 v 及其相关的弧。
Page 34
2020/11/24
InsertArc(&G, v, w); 初始条件：图 G 存在，v 和 w 是 G 中两个顶点。 操作结果：在 G 中增添弧<v,w>，若 G 是无向的，则还
Page 2
2020/11/24
• 知识点
– 图的类型定义 – 图的存储表示 – 图的深度优先搜索遍历和广度优先搜索遍历 – 无向网的最小生成树 – 拓扑排序 – 关键路径 – 最短路径
Page 3

由于“弧”是有方向的，因此称由顶点集 和弧集构成的图为有向图。
例如: G1 = (V1, VR1)
其中 A
V1={A, B, C, D, E}
B
E VR1={<A,B>, <A,E>,
C
D
<B,C>, <C,D>, <D,B>, <D,A>, <E,C> }
若<v, w>VR 必有<w, v>VR, 则称 (v,w) 为顶点 v 和顶点 w 之间存在一条边。
A
B
EB
E
CF
CF
假设一个连通图有 n 个顶点和 e 条边， 其中 n-1 条边和 n 个顶点构成一个极小连 通子图，称该极小连通子图为此连通图的 生成树。
B A
F
C D
E
对非连通图，则 称由各个连通分 量的生成树的集 合为此非连通图 的生成森林。
基本操作
结构的建立和销毁 对顶点的访问操作
插入或删除顶点 插入和删除弧
7.2 图的存储表示
一、图的数组(邻接矩阵)存储表示 二、图的邻接表存储表示 三、有向图的十字链表存储表示 四、无向图的邻接多重表存储表示
一、图的数组(邻接矩阵)存储表示
定义:矩阵的元素为
{ 0 (i,j)VR
Aij= 1 (i,j)VR
B A
F
C D
E
010010 100010 000101 001001 110000 011100
含有 e=n(n-1) 条弧的有向图称作 有 向完全图;
若边或弧的个数 e<nlogn，则称作 稀疏图，否则称作稠密图。
假若顶点v 和顶点w 之间存在一条边， 则称顶点v 和w 互为邻接点， 边(v,w) 和顶点v 和w 相关联。

欧拉公式是检查实体有效性的一个必要条件（不是充 分条件）
简单多面体条件： （1）所在面是单连通的，上面没有洞 （2）立体是单连通的，而且没有孔洞 （3）每条棱边上恰好邻接两个面 （4）每一个顶点处至少有三条棱边相遇
其顶点数V、边数E和面数F满足如下关系：
V-E+F=2。
V-E+F=2
v=8
v=5
可以将实体模型的表示可分为以下方法： 边界表示法（BR） 扫描表示法 构造实体几何法（CSG） 空间位置枚举表示法 八叉树法 二叉空间分割法（BSP）
4.2.1 多边形表面模型
边界表示(B-reps)的最普遍方式是多边形表面模型，它 使用一组包围物体内部的平面多边形，也即平面多面 体，来描述实体。
拓扑信息：形体各分量（点、边、面）的数目及其相 互间的连接关系。
1. 几何信息 (1)几何分量的数学表示, 如： 点: (x, y, z) 直线：x=(y-y0)/a=(z-z0)/b 平面：ax+by+cz+b=0
(2)几何分量之间的相互关系(拓扑信息)
f1f2 f3
点v
v1 v2 v3
v1 v2 e1 e2
v
v
v 顶点相邻性 v:{v}
v e v
边 -顶 点 包 含 性 e:{v}
e
e
e
f e
面 -边 包 含 性 f:{e}
e ve e
顶 点 -边 相 邻 性 v:{e}
ee e ee
边 相 邻 性 e:{e:}
图4-3 平面立体的九种拓扑关系
4.1.3 坐标系
坐标系
建模坐标系 用户坐标系 观察坐标系 规格化的设备坐标
线框模型
由定义一个物体的直线和曲线组成，每一条直线和 曲线都是单独构造出来的，并不存在面的信息。

层次分明
02
通过节点和边的关系，数据结构图能够清晰地表示数据的层次
结构，有助于理解数据的组织方式。
易于修改
03
相比文本或表格，数据结构图更易于修改和更新，能够快速适
应数据的变化。
数据结构图的缺点
制作难度大
制作一份高质量的数据结构图需要花费较多的时间和精力，特别 是在处理复杂的数据结构时。
表达能力有限
解数据结构。
辅助设计数据结构
在设计复杂的数据结构时，可以使 用数据结构图来辅助设计，使设计 过程更加清晰和有条理。
方便交流和讨论
数据结构图是一种可视化的表达方 式，可以方便地展示给其他人，有 助于团队成员之间的交流和讨论。
数据结构图的分类
01
02
03
树形结构图
树形结构图是一种层次结 构的数据结构图，它通过 节点和子节点的关系来表 示数据的层次关系。
随着用户需求的多样化，未来 的数据结构图将更加注重个性 化定制，满足不同用户对数据 可视化的需求和偏好。
为了提高数据可视化的可解释 性和透明度，未来的数据结构 图将更加注重对数据的处理和 分析过程的可视化呈现，使用 户能够更好地理解数据的来源 和含义。
2023 WORK SUMMARY
THANKS
未来的数据结构图将更加注重用户的交互 性，使用户能够更深入地探索数据，提高 数据理解的效率和准确性。
动态数据的实时呈现
多维度的数据呈现
随着大数据和实时数据处理技术的发展， 数据结构图将能够实时呈现动态数据的变 化，帮助用户更好地理解和分析数据。
未来的数据结构图将能够呈现多维度的数 据，包括时间序列数据、空间数据等，满 足用户对不同类型数据的可视化需求。
详细描述

y
z
x
4.1 基本概念
•面
–R3中非空、连续、共平面且封闭的子集称 为面F， 其边界(记为∂F)是有限条线段的并集， Pt表示含有F的唯一平面。 面是形体表面的一部分，且具有方向性.
Pt F
4.1 基本概念
•环
–由有序、有向边组成的面的封闭边界称为环; –环中任意边都不能自交，相邻两条边共享一
个端点; –环又分为内环和外环:内环是在已知面中的
4.1 基本概念
图形信息又可以进一步分为包括： （欧氏）几何信息：形体在欧氏空间中的位置和
大小； 拓扑信息：形体各分量（点、边、面）的数目及
其相互间的连接关系。
4.1 基本概念
1、几何信息 几何信息的数学表示：点线面的公式
4.1 基本概念
2、拓扑信息： 平面立体的几何分量之间一共有九种拓扑
关系
• 三维空间中的物体是一个内部连通的三 维点集，是由其内部的点集及紧紧包着
这些点的表面组成的。
• 4.2.1 利用正则集定义实体－－使得实体 可计算
几个预备定义：
– 点的邻域：如果P是点集S的一个元素，那么 点P的以R（R>0）为半径的邻域指的是围绕 点P的半径为R的小球（二维情况下为小圆）。
– 内点为点集中的这样一些点，它们在实体内 部具有完全包含于该点集的充分小的邻域。
内孔，其边按顺时针方向。外环是已知面的 最大外边界的环，其边按逆时针方向，按定 义，在面上沿着边的方向前进，面的内部始 终在走向的左侧。
4.1 基本概念
•边
–形体内两个相邻面的交界称为边，一条边 是（正则形体情况下）两个邻面或者（非 正则形体）多个邻面的交界。两个端点确 定一条边，这两个端点分别称为该边的起 点和终点。

数据结构是计算机中存储、组织 数据的方式，它定义了数据元素 之间的逻辑关系以及如何在计算 机中表示这些关系。
数据结构分类
根据数据元素之间关系的不同， 数据结构可分为线性结构、树形 结构、图形结构等。
4
数据结构重要性
01
02
03
提高算法效率
合理的数据结构可以大大 提高算法的执行效率，减 少时间和空间复杂度。
33
案例三：最小生成树在通信网络优化中应用
Kruskal算法
基于并查集实现，按照边的权值从小到大依次添加边，直到生成 最小生成树。
Prim算法
从某一顶点开始，每次选择与当前生成树最近的顶点加入，直到 所有顶点都加入生成树。
通信网络优化
最小生成树算法可用于通信网络优化，通过选择最优的通信线路 和节点，降低网络建设和维护成本。
2024/1/28
简化程序设计
数据结构的设计和实现可 以简化程序设计过程，提 高代码的可读性和可维护 性。
解决实际问题
数据结构是解决实际问题 的基础，如排序、查找、 图论等问题都需要依赖于 特定的数据结构。
5
相关术语解析
数据元素
数据元素是数据的基本 单位，通常作为一个整
体进行考虑和处理。
2024/1/28
02
队列的基本操作包括入队（enqueue）、出队（ dequeue）、查看队首和队尾元素等。
03
队列的特点
2024/1/28
04
数据从队尾入队，从队首出队。
05
队列中元素的插入和删除操作分别在两端进行，因此也称 为双端操作。
06
队列中没有明显的头尾标记，通常通过计数器或循环数组 等方式实现。
15
栈和队列应用举例

记录各个顶点信息
表示各个顶点之间关系
② 设图 A = (V, E) 有 n 个顶点，则图的邻接矩阵是一个二维数 组 A.Edge[n][n]，定义为：
1 , 如 < 果 i,j> E 或(i者 ,j) E A .Ed [i]g j[ ] e 0 , 否 则
例1：无向图的邻接矩阵如何表示顶？点表： （
邻接矩阵
但可用数组描述元素间关系。
链式存储结构： 可用多重链表
1. 邻接矩阵(数组)表示法
•邻接表 •十字链表 •邻接多重表
2. 邻接表(链式)表示法 3. 十字链表表示法 4. 邻接多重表表示法
各种表示法成立的原则： 存入电脑后能惟一复原
1. 邻接矩阵（数组）表示法
① 建立一个顶点表和一个邻接矩阵。
图：记为 G＝( V, E )
V=vertex E=edge
其中：V 是G 的顶点集合，是有穷非空集；
E 是G 的边集合，是有穷集。
问：当E(G)为空时，图G存在否？ 答：还存在！但此时图G只有顶点而没有边。
v1 v2
v3
v4
v5
v1 v2
有向图：图G中的每条边都是有方向的；
v3 v4
无向图：图G中的每条边都是无方任意一对顶点都是连通的, 则 称此图是连通图。 非连通图的极大连通子图叫做连通 分量。
强连通图：在有向图中, 若对于每一对顶点vi和vj,
都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。
A
B
CDE F GH
I
K
J
L
M
非强连通图的极大强连通子图叫做强连通分量。
无向图(树)
有向图
有向完全图 n(n-1) 条边

栈
一种后进先出（LIFO）的数据结构，用于实 现特定操作顺序。
链表
一种线性数据结构，通过指针将元素链接在 一起。
队列
一种先进先出（FIFO）的数据结构，用于实 现特定操作顺序。
图形数据结构分类
顶点数据结构
用于存储图形的顶点信息，如坐标、 颜色等。
边数据结构
用于存储图形之间的连接关系，如线 段、弧等。
虚拟现实中的图形学应用
场景建模
虚拟现实中的场景需要高度逼真，计算机图形学技术用于创建三 维模型，并进行纹理映射、光照计算等处理。
交互体验
虚拟现实中的物体需要能够与用户进行交互，计算机图形学可以 模拟物体的物理属性，如重量、质地等。
实时渲染
虚拟现实需要实现高帧率的实时渲染，计算机图形学技术能够快 速处理图像，提供流畅的虚拟现实体验。
光线追踪渲染技术能够生成高质量的图像，但计算量较大，实时性较差 。
扫描线渲染技术
扫描线渲染技术是一种基于光栅化的 渲染技术，它将三维场景中的物体进 行几何变换和光照计算，然后将其转 换成二维图像。
扫描线渲染技术计算量较小，实时性 较好，但生成的图像质量相对较低。
扫描线渲染的基本原理是从上到下、 从左到右扫描场景中的每个像素，并 根据像素所在区域内的物体和光照信 息计算出该像素的颜色值。
沉浸式体验。
01
图形数据结构
数据结构概述
01
数据结构是计算机中数据的组织方式，它涉及到数 据的逻辑关系和物理表示。
02
数据结构是计算机科学和软件工程领域的重要概念 ，它影响着程序的性能和可维护性。
03
数据结构主要分为两大类：线性数据结构和非线性 数据结构。
常见数据结构
数组

哈夫曼树的构建算法
根据给定的权值集合构建哈夫曼树的详细步骤和代码实现。
PART 04
图形结构图资料
图的基本概念和术语解释
图(Graph)
无向图和有向图
由顶点(Vertex)和边(Edge)组成的数据结构， 用于表示对象及其之间的关系。
根据边是否有方向，图可分为无向图和有 向图。无向图中的边没有方向，而有向图 中的边有方向。
ONE
KEEP VIEW
数据结构图资料课件
目 录
• 数据结构图基本概念 • 线性结构图资料
• 查找与排序相关知识点 • 数据结构图在实际问题中应用
PART 01
数据结构图基本概念
数据结构定义与分类
数据结构定义
数据结构是计算机存储、组织数 据的方式，包括数据的逻辑结构、 存储结构和运算三部分。
数据结构分类
常见查找排序算法代码示例
二分查找代码示例
通过不断缩小查找 范围，快速定位元 素位置。
插入排序代码示例
通过构建有序序列， 逐个插入元素并保 持有序性。
顺序查找代码示例
通过循环遍历数组， 逐个比较元素值。
哈希查找代码示例
设计哈希函数计算 关键字存储位置， 处理哈希冲突。
快速排序代码示例
选取基准元素，将 序列划分为两部分 并递归排序。
PART 06
数据结构图在实际问题中 应用
实际问题中数据结构选择策略
选择合适的数据结构
01
根据问题的特点，选择合适的数据结构，如数组、链表、栈、
队列、树、图等。
考虑数据规模
02
针对数据规模的大小，选择合适的数据结构以优化时间和空间
复杂度。
利用数据结构特性
03