当前位置：文档之家 › 数据结构 第6章 图

数据结构 第6章 图

  • 格式：ppt
  • 大小：2.67 MB
  • 文档页数：83

下载文档原格式

  / 83

合集下载

计算机导论-第6章 数据结构

计算机导论-第6章 数据结构

⑴集合结构。在集合结构中，数据元素间的关系是“属于 同一个集合”。集合是元素关系极为松散的一种结构。
单击此处添课程名 ⑵线性结构。该结构的数据元素之间存在着一对一的关系。
⑶树型结构。该结构的数据元素之间存在着一对多的关系。
⑷图型结构。该结构的数据元素之间存在着多对多的关系， 图形结构也称作网状结构。
具有特殊的意义，称为栈顶。相应地，表尾 称为栈底。不含任何元素的栈称为空栈。
2. 栈的数学性质
假设一个栈S中的元素为an,an-1,..,a1，则 称a1为栈底元素，an为栈顶元 素。栈中的
元 时素 候按 ，单出a ,a栈击2,的..此,元an素-处1,都an添是的栈次课顶序程元进素栈名。。换在句任话何
第六章 数单据击结此构处添课程名
第6章 数据结构
• 数据结构是计算机软件和计算机应用专业的 核心课程之一，对于学习计算机专业的其他 课程，如操作系统、编译原理、数据库管理
系的统 。、 数软 据单件 结击工 构程主此、要处人研工究添智数能据课等表程都示是 与名十 存储分的有方益
法、抽象的逻辑结构及其上定义的各种基本 操作。数据的逻辑结构常常采用数学描述的 抽象符号和有关的理论。如使用串、表、数 组、图等结构和理论来表示数据在存储时的 逻辑结构，研究这些结构上定义的各种操作 。
本章内容
• 6.1 数据结构的概念 • 6.2 几种典型的数据结构 • 6.3 查找
• 6.4 单排序击此处添课程名
6.1 数据结构的概念
• 在系统地学习数据结构知识之前，先对一 些与数据结构相关的基本概念和术语赋予 确切的含义。
• 数 算机据单识（别D击at、a此）存是储处信和添息加的工课载处体理程，。名它它能是够计被算计机 程序加工的原料，应用程序处理各种各样 的数据。
数据结构(C语言版)严蔚敏第6章 树和二叉树

数据结构(C语言版)严蔚敏第6章 树和二叉树

如图6-1(b)中结点H、I、J、K、L、M、N是叶子 结点，而所有其它结点都是分支结点。
⑷ 孩子结点、双亲结点、兄弟结点
一个结点的子树的根称为该结点的孩子结点(child) 或子结点；相应地，该结点是其孩子结点的双亲结点 (parent)或父结点。
4
如图6-1(b)中结点B 、C、D是结点A的子结点，而结 点A是结点B 、C、D的父结点；类似地结点E 、F是结 点B的子结点，结点B是结点E 、F的父结点。
这是树的递归定义，即用树来定义树，而只有 一个结点的树必定仅由根组成，如图6-1(a)所示。
2
2 树的基本术语
⑴ 结点(node)：一个数据元素及其若干指向其子树的分支。 ⑵ 结点的度(degree) 、树的度：结点所拥有的子树
的棵数称为结点的度。树中结点度的最大值称为树的度。
A
B
C
D
A
E
F G HI J
同一双亲结点的所有子结点互称为兄弟结点。
如图6-1(b)中结点B 、C、D是兄弟结点；结点E 、 F是兄弟结点。
⑸ 层次、堂兄弟结点
规定树中根结点的层次为1，其余结点的层次等于 其双亲结点的层次加1。
若某结点在第l(l≧1)层，则其子结点在第l+1层。
双亲结点在同一层上的所有结点互称为堂兄弟结点。 如图6-1(b)中结点E、F、G、H、I、J。
(a) 只有根结点
K
LM N
图6-1 树的示例形式
(b) 一般的树
3
如图6-1(b)中结点A的度是3 ，结点B的度是2 ，结点 M的度是0，树的度是3 。
⑶ 叶子(left)结点、非叶子结点：树中度为0的
结点称为叶子结点(或终端结点)。相对应地，度不为 0的结点称为非叶子结点(或非终端结点或分支结点)。 除根结点外，分支结点又称为内部结点。
数据结构(CC++语言版)第六章new

数据结构(CC++语言版)第六章new

为简单路径。
回路 若路径上第一个顶点 v1 与最后一个顶点vm 重合, 则称这样的路径
为回路或环。
路径长度
非带权图的路径长度是指此路径上边的条数。 带权图的路径长度是指路径上各边的权之和。
▪图的连通 在无向图G中，若两个顶点vi和vj之间有 路径存在，则称vi 和vj 是连通的。若G中任意两 个顶点都是连通的，则称G为连通图。非连通图的 极大连通子图叫做连通分量。
5 9
1
12
63
8
15
76
6
3
4
16
7
60
A
B 40 80 C
30
75
35
D
E
45
▪子图 设有两个图 G＝(V, E) 和 G‘＝(V’, E‘)。若 V’ V 且 E‘E, 则称 图G’ 是 图G 的子图。
路径 在图 G＝(V, E) 中, 若从顶点 vi 出发, 沿一些边经过一些顶点 vp1,
种带权图叫做网。
▪生成树 一个连通图的生成树是它的极小 连通子图，在n个顶点的情形下，有n-1条 边。生成森林
不予讨论的图 包含顶点到其自身的边； 一条边在图中重复出现
6.2 图的存储结构
一. 图的数组表示法 (邻接矩阵表示法)
基本思想：
✓ 图需要存储的信息：顶点和弧。 ✓ 引入两个数组，一个记录各个顶点信息的顶点表，还
有一个表示各个顶点之间关系的邻接矩阵。
设图 A = (V, E)是一个有 n 个顶点的图，则图的 邻接矩阵是一个二维数组 A.arcs[n][n]，定义：
1 arcs[i][j] = 0
若<vi, vj> 或 (vi, vj) E 反之
2
1
数据结构第六章 哈夫曼树

数据结构第六章 哈夫曼树

6.3哈夫曼树6.3.1基本术语1.路径和路径长度若在一棵中存在着一个结点序列k1 ,k2,…,kj，使得ki是k1+i 的双亲(1ji<≤)，则称此结点序列是从k1～kj的路径，因树中每个结点只有一个双亲结点，所以它也是这两个结点之间k 1～kj所经过的分支数称为这两点之间的路径长度，它等于路径上的结点数减1(实际就是边数)。

如在图5-19(a)所示的二叉树中，从树根结点L到叶子结点P的路径为结点序列L、M、S、P，路径长度为3。

(a) (b)(c) (d)图5-19 二叉排序树的删除2.结点的权和带权路径长度在许多应用中，常常将树中的结点赋上一个有着某种意义的实数，我们称此实数为该结点的权。

结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点上权的乘积3.树的带权路径长度树的带权路径长度定义为树中所有叶子结点的带权路径长度这和，通常记为：2 WPL = ∑=n i i i lw 1其中n 表示叶子结点的数目，i w 和i l 分别表示叶子结点i k 的权值和根到i k 之间的路径长度 。

4.哈夫曼树哈夫曼(Huffman)树又称最优二叉树。

它是n 个带权叶子结点构成的所有二叉树中，带权路径长度 WPL 最小的二叉树。

因为构造这种树的算法是最早由哈夫曼于1952年提出的，所以被称之为哈夫曼树。

例如，有四个叶子结点a 、b 、c 、d ，分别带权为9、4、5、2，由它们构成的三棵不同的二叉树（当然还有其它许多种）分别如图5-20(a)到图5-20(c)所示。

b ac a b cd d c a b d(a) (b) (c)图5-20 由四个叶子结点构成的三棵不同的带权二叉树 每一棵二叉树的带权路径长度WPL 分别为：(a) WPL = 9×2 + 4×2 + 5×2 + 2×2 = 40(b) WPL = 4×1 + 2×2 + 5×3 + 9×3 = 50(c) WPL = 9×1 + 5×2 + 4×3 + 2×3 = 37其中图5-20(c)树的WPL 最小，稍后便知，此树就是哈夫曼树。

北邮数据结构第六章答案详解 图(1)

北邮数据结构第六章答案详解 图(1)


1
5
1
54 3
42
5 66
图 6-8 图 G 答案：根据不同算法构造的最小生成树如图 6-9 所示的图(a)和(b)
2
④
⑤ 5
1
①
4 3
②
③
6
2
⑤
③ 5
1
①
4 3
④
②
6
(a) Prim 生成树
(b) Kruskal 生成树
图 6-9 最小生成树
5、算法设计
（1）以邻接表为存储结构，设计实现深度优先遍历的非递归算法。
int top = -1; cout<<v<<’\t’; bVisited[v] = true; stack[++top] = v;
//访问结点 v //设置访问标记 //结点 v 入栈
while (top!=-1)
{
v=stack[top];
ArcNode<T> *p = adjlist[v]. firstarc; ①
)
A.1
B. n/2
C.n-1
D.n
解析：若超过 n-1，则路径中必存在重复的顶点
答案：C
(5) 若一个图中包含有 k 个连通分量，若按照深度优先搜索的方法访问所有顶点，则必
须调用(
)次深度优先搜索遍历的算法。
A.k
B.1
C.k-1
D.k+1
解析：一次深度优先搜索可以访问一个连通分量中的所有结点，因此 k 个连通分量需要 调用 k 次深度优先遍历算法。
④
} if (p==NULL) top--;
⑤//若是找不到未访问的结点，出栈
数据结构-C语言描述(第三版)(陈慧南)章 (6)

数据结构-C语言描述(第三版)(陈慧南)章 (6)


第6章 树 例如，设有序表为(21, 25, 28, 33, 36, 43)，若要在表中 查找元素36，通常的做法是从表中第一个元素开始，将待查元素 与表中元素逐一比较进行查找，直到找到36为止。粗略地说，如 果表中每个元素的查找概率是相等的，则平均起来，成功查找一 个元素需要将该元素与表中一半元素作比较。如果将表中元素组 成图6－3所示的树形结构，情况就大为改观。我们可以从根结点 起，将各结点与待查元素比较，在查找成功的情况下，所需的最 多的比较次数是从根到待查元素的路径上遇到的结点数目。当表 的长度n很大时，使用图6－3所示的树形结构组织表中数据，可 以很大程度地减少查找所需的时间。为了查找36，我们可以让36 与根结点元素28比较，36比28大，接着查右子树，查找成功。显 然，采用树形结构能节省查找时间。
第6章 树
E
E
A
F
B
G
CD
LJ
M
N
T1
X
YZ
U T2
B
F
A
DC
G
JL
T3 N
M
(a)
(b)
图6－2 树的例子
(a) 树T1和T2组成森林；(b) 树T3
第6章 树
6.2 二 叉 树
二叉树是非常重要的树形数据结构。很多从实际问题中抽 象出来的数据都是二叉树形的，而且许多算法如果采用二叉树 形式解决则非常方便和高效。此外，以后我们将看到一般的树 或森林都可通过一个简单的转换得到与之相应的二叉树，从而 为树和森林的存储及运算的实现提供了有效方法。
第6章 树
图6－1描述了欧洲部分语言的谱系关系，它是一个后裔图， 图中使用的描述树形结构数据的形式为倒置的树形表示法。在 前几章中，我们学习了多种线性数据结构，但是一般来讲，这 些数据结构不适合表示如图6－1所示的层次结构的数据。为了 表示这类层次结构的数据，我们采用树形数据结构。在本章中 我们将学习多种不同特性的树形数据结构，如一般树、二叉树、 穿线二叉树、堆和哈夫曼树等。
6-5-数据结构——从概念到C++实现(第3版)-王红梅-清华大学出版社

6-5-数据结构——从概念到C++实现(第3版)-王红梅-清华大学出版社


Dijkstra算法——运行实例
v1
10
50
v0
v2
30 10
100
20
v4
v3
60
初始化：S={v0} dist(v, vi)：<v0,v1>10 <v0,v2>∞ <v0,v3>30 <v0,v4>100
第一次迭代：S={v0, v1}
数 据 结
构
dist(v, vi)：<v0,v1,v2>60 <v0,v3>30 <v0,v4>100
2.1 dist(v, vk) = min{dist(v, vj), (j=1..n)}； 2.2 S = S + {vk}； 2.3 dist(v, vj)=min{dist(v, vj), dist(v, vk) + w<vk, vj>}；
V-S vi
数 据 结 构 （ 从 概 念 到 实 现 ） 清 华 大 学 出 版 社
Dijkstra算法——运行实例
v1
10
50
v0
v2
30 10
100
20
v4
v3
60
v1 10
当前的最短路径：
v0
∞
v2
30
<v0,v1>10 <v0,v2>∞
100
<v0,v3>30
数 据 结
构
v4
v3
<v0,v4>100
（ 从 概
念
dist[n] 0 10 ∞ 30 100
到 实
现
v1
10
50
数据结构第六章图理解练习知识题及答案解析详细解析(精华版)

数据结构第六章图理解练习知识题及答案解析详细解析(精华版)

图1. 填空题⑴设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。

【解答】0，n(n-1)/2，0，n(n-1)【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。

⑵任何连通图的连通分量只有一个，即是（）。

【解答】其自身⑶图的存储结构主要有两种，分别是（）和（）。

【解答】邻接矩阵，邻接表【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。

⑷已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。

【解答】Ｏ(n+e)【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。

⑸已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。

【解答】求第j列的所有元素之和⑹有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。

【解答】出度⑺图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。

【解答】前序，栈，层序，队列⑻对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。

【解答】Ｏ(n2)，Ｏ(elog2e)【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。

⑼如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。

【解答】回路⑽在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。

【解答】vi, vj, vk【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。

《数据结构——C语言描述》第6章：树

《数据结构——C语言描述》第6章：树

Void paintleaf (Btree root) { if (root!=NULL) { if (root ->Lchild==NULL && root ->Rchild==NULL) printf (root ->data); paintleaf (root ->Lchild); paintleaf (root -遍历左子树； （2）访问根结点； （3）中根遍历右子树。 后根遍历二叉树 （1）后根遍历左子树； （2）后根遍历右子树； （3）访问根结点。
先根遍历: -+a*b–cd/ef 中根遍历: a+b*c–d–e/f 后根遍历: abcd-*+ef/-
typedef struct Node { datatype data; struct Node *Lchild; struct Node *Rchild; } BTnode,*Btree;
满二叉树：一棵深度为k且有2k-1个结 点的二叉树称为满二叉树。 完全二叉树：深度为k，有n个结点的 二叉树当且仅当其每一个结点都与深度 为k的满二叉树中编号从1至n的结点一一 对应时，称为完全二叉树。
1 2 4 8 9 10 5 11 12 6 13 14 3 7 15 4 6 2
1 3 5 7
树的度：树中最大的结点的度数即为 树的度。图6.1中的树的度为3。 结点的层次(level)：从根结点算起， 根为第一层，它的孩子为第二层……。 若某结点在第l层，则其孩子结点就在 第l+1层。图6.1中，结点A的层次为1， 结点M的层次为4。 树的高度(depth)：树中结点的最大层 次数。图6.1中的树的高度为4。 森林(forest)：m(m≥0)棵互不相交的 树的集合。
数据结构——用C语言描述(第3版)教学课件第6章 树与二叉树

数据结构——用C语言描述(第3版)教学课件第6章 树与二叉树


6.2 二叉树 6.2.1 二叉树的定义与基本操作 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构
6.2.1 二叉树的定义与基本操作 定义：我们把满足以下两个条件的树型结构叫做二 叉树（Binary Tree）： （1）每个结点的度都不大于2； （2）每个结点的孩子结点次序不能任意颠倒。
有序树：在树T中，如果各子树Ti之间是有先后次序的，则称为有序树。 森林：m（m≥0）棵互不相交的树的集合。将一棵非空树的根结点删去，树就变成一 个森林；反之，给森林增加一个统一的根结点，森林就变成一棵树。
同构：对两棵树，通过对结点适当地重命名，就可以使两棵树完全相等（结点对应相 等，对应结点的相关关系也像等），则称这两棵树同构。
二叉树的基本结构由根结点、左子树和右子树组成
如图示
LChild Data RChild
Data
LChild RChild
用L、D、R分别表示遍历左子树、访问根结点、遍 历右子树，那么对二叉树的遍历顺序就可以有：
(1) 访问根，遍历左子树，遍历右子树(记做DLR)。 (2) 访问根，遍历右子树，遍历左子树(记做DRL)。 (3) 遍历左子树，访问根，遍历右子树(记做LDR)。 (4) 遍历左子树，遍历右子树，访问根 (记做LRD)。 (5) 遍历右子树，访问根，遍历左子树 (记做RDL)。 (6) 遍历右子树，遍历左子树，访问根 (记做RLD)。
(8) NextSibling（Tree，x）： 树Tree存在，x是Tree中的某个结点。若x不 是其双亲的最后一个孩子结点，则返回x后面的下一个兄弟结点，否则 返回“空”。
基本操作:
(9) InsertChild（Tree，p，Child）： 树Tree存在，p指向Tree 中某个结点，非空树Child与Tree不相交。将Child插入Tree中， 做p所指向结点的子树。
数据结构与算法-第6章

数据结构与算法-第6章


如果 e=(u, v) 是 E(G) 中的一条边，则称 u 与 v
互为邻接点或相邻点;称边e与顶点u,v关联;
如果 a=<u, v> 是 E(G) 中的一条弧，则称u邻接到v
或v邻接于u,也称弧a与顶点u,v关联.
9
6.1 图的基本概念
顶点的度（与树中结点的度不同）: –无向图中，顶点的度是与每个顶点关联的边数, 记作TD(v) –有向图中，顶点的度分成入度与出度 •入度：以该顶点为终头的弧的数目,记为ID(v) •出度：以该顶点为始点的弧的数目,记为OD(v) 一个顶点的度等于该顶点的入度与出度之和,即 TD(v)=OD(v)+ID(v)
20
带权图的邻接矩阵
wij 若(vi，vj)∈E或<vi，vj>∈E
A[i][j]= ∞ 其它 0 i=j
21
用邻接矩阵表示的图的类的定义
class AdjMatrix { int n； int matrix[MaxSize][ MaxSize]； public: AdjMatrix(int m) { n=m； } }; // AdjMatrix class AdjMatrix { const int INFINITE=∞； int n； float matrix[MaxSize][MaxSize]； public: AdjMatrix(int m) { n=m；} }; // AdjMatrix // 非带权图 // 顶点的个数 // 邻接矩阵
回路——第一个顶点和最后一个顶点相同的路径。
简单回路——除了第一个顶点和最后一个顶点外，其
余顶点不重复出现的回路。
11
6.1 图的基本概念
V0V1V3V2
V0V1V3V0V1V2

第六章 树状结构


6.24
2006
线索二叉树的优点
搜寻线索二叉树节点的中序后继的C语言程序。 搜寻线索二叉树节点的中序后继的C语言程序。
Node_type *insuc(Node_type *ptr) { Node_type *this_n; *this_n; this_n = ptr->rlink; ptr->rlink; if(ptrif(ptr->rbit == 1) while(this_nwhile(this_n->lbit == 1) this_n=this_n->llink; this_n=this_n->llink; return this_n; this_n; }
6.18
2006
中序遍历的非递归的程序段
void inorder(struct node *T) { int i = -1; for(; for(; ;) { while(T != NULL) { i = i +1; if(i > n) printf("The stack is full"); ull"); else { STACK[i] = T; t= t->llink; >llink;
终端节点（ 终端节点 （ terminal node） 或叶节点 （ leaf node）： node）或叶节点（ node）
- 没有子节点的节点称为终端节点. 没有子节点的节点称为终端节点. - 图6-1中，J、K、L、G、M、N、I皆为叶节点。 皆为叶节点。
6.5
2006
树状结构的一些专有名词4 树状结构的一些专有名词4
- 树中某节点的高度表示此节点至叶节点的最长路径（Path） 树中某节点的高度表示此节点至叶节点的最长路径（Path） 长度。 长度。 - 如图6-1的A节点高度为3，C节点的高度为1。 如图6 节点高度为3 节点的高度为1

数据结构_第六章_图_练习题与答案详细解析(精华版)

图1. 填空题⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。

【解答】0，n(n-1)/2，0，n(n-1)【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。

⑵ 任何连通图的连通分量只有一个，即是（）。

【解答】其自身⑶ 图的存储结构主要有两种，分别是（）和（）。

【解答】邻接矩阵，邻接表【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。

⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。

【解答】Ｏ(n+e)【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。

⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。

【解答】求第j列的所有元素之和⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。

【解答】出度⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。

【解答】前序，栈，层序，队列⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。

【解答】Ｏ(n2)，Ｏ(elog2e)【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。

⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。

【解答】回路⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。

【解答】vi, vj, vk【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。

第6章 图4-算法与数据结构(第三版)-陈媛-清华大学出版社

基本思想： 假设求从顶点vi到v j的最短路径，如果从vi到vj 有弧，初则始从化vi时到vSj=存{}在，一于条是长a[度i，为j]c=ocsots[ti，[i，j]的j]接路着进 径 行n次试探，依次向集合S中加入v1，v2，...vn 用二维。数每组次A加的入元一素个a[顶i，点j]。存放从vi到vj中间只经 过集合首S先中S的=S顶∪点{v的1}所，有考可虑能路的径路(v径i，中v1，，有v最j)是短否存 长度的在路，径即的判长别度弧。(vi，v 1)和(v1，vj)是否存在，如
计算机科学与工程学院《数据结构》课程组
6
Dijkstra算法
S←{v1}； dist[j]←cost[1，j] j=2，...，n； 选择vj使得 dist[j]=min{dist[i]│vi∈V-S} vj就是当前求得的一条从v1出发的最短路径的终 点。令：S=S∪{j} 修改从v1出发到集合V-S上任一个顶点Vk可达的 最短路径长度，如果dist[j]+cost[j，k]<dist[k]， 则修改dist[k]为dist[k]=dist[j]+cost[j，k] 重复(2)、(3)共n-1次，由此求得从v到图上其余各 顶点的最短路径是依路径长度递增的序列 时间复杂度为O(n2)
20
计算机科学与工程学院《数据结构》课程组
3
单源最短路径-迪杰斯特拉(Dijkstra)算法思想
按路径长度递增次序产生最短路径算法： 把V分成两组：
S：已求出最短路径的顶点的集合 V-S=T：尚未确定最短路径的顶点集合 将T中顶点按最短路径递增的次序加入到S中， 保证： 从源点V0到S中各顶点的最短路径长度都不大于 从V0到T中任何顶点的最短路径长度 每个顶点对应一个距离值
计算机科学与工程学院《数据结构》课程组

数据结构 第6章 排序


判断某序列是否符合堆定义
只要将序列依次排成一棵完全二叉树，所有结点的 值都不大于（或不小于）其左右子树结点的值，那么该 序列就符合堆的定义。 例：序列：102、87、100、79、82、62、84
10 2 87 10 0 82
故： 此序列符 合堆定义。
84
79
62
若n个元素的排序码k1，k2，k3，…，kn满足堆，且让结点 按1、2、3、…、n顺序编号，根据完全二叉树的性质（若i为 根结点，则左孩子为2i，右孩子为2i+1）可知，堆排序实际与 一棵完全二叉树有关。若将排序码初始序列组成一棵完全二 叉树，则堆排序可以包含建立初始堆（使排序码变成能符合 堆的定义的完全二叉树）和利用堆进行排序两个阶段。
14
17
25 )
20
9
(3
14
17
20
25 )
9
第五次插入
(3
9
14
17
20
25)
图 9-1 直接插入排序示例
注意:
排正序时，要插入的元素先和有序表中最后 一个元素进行比较，即从后往前；排逆序时， 则刚相反，得从前往后进行比较。 当n很小时，直接插入排序的效率较高，时间 复杂度为o(n^2)。 正序时比较次数最少为n-1； 逆序时最大为(n+2)*(n-1)/2； 两者的平均值约为(n^2)/4。
例如，n=6，数组R的六个排序码分别为：17，3，25，14，20， 9。下面用图9-3给出冒泡排序算法的执行过程。
0 1 2 3 4 5
初始状态
（17
3
25
14
20
9)
第一趟排序
3
(17
9
25

王道数据结构 第六章 图思维导图


ve(源点)=0
ve(k)
=
Ma
x{ve(j)+Weight(vj
v, k ​ ​)}，vj
v 为 ​
k
的任意前驱
​
1.求所有事件的最早发生时间ve()
按逆拓扑排序序列，依次求各个顶点的vl(k):
vl(汇点)=ve(汇点)
vl(k)
=
Min{vl(j)-W
eight(vj
v, k ​ ​)}，vj
常见考点：
对于n个顶点的无向图G，
若G是连通图，则最少有n
-1条边，
若G是非连通图，则最多可能有Cn2−
1
条边
​
对于n个顶点的有向图G，
若G是强连通图，则最少有
n条边
子图/生成子图（子图包括所有顶点）
强连通分量：有向图中的极大强连通子图（必须强连通且保留尽可能多的边）
连通图的生成树是包含图中全部顶点的一个极小连通子图（边尽可能的少但要保 持连通）
n个顶点对应2Cn2
条边
​
几种特殊的图
稀疏图/稠密图 树：不存在回路，且连通的无向图
n个顶点的树必有n-1条边 常见考点：n个顶点的图，若|E|>n-1，则图中一定存在回路
有向树：一个顶点的入度为0，其余顶点的入度均为1的有向图
有向树不是强连通图
常见考点
邻接矩阵
图的存储
无向图
第i个结点的度 = 第i行（或第i列）的非零元素个数
每一轮时间复杂度：O(2n)
时间复杂度
最短路径问题
Dijkstra算法不适用于有负权值的带权图 算法思想：动态规划
Floyd算法（带权图，无权图）
各顶点间的最短路径

第6章 图3-算法与数据结构(第三版)-陈媛-清华大学出版社

权 14 2 6 5
12
PRIM算法
✓ 初始为任意一个顶点，置初始候选蓝边集 ✓ While(T中顶点数目<n) ✓{
✓ 从候选蓝边集合中选取最短蓝边(u,v); ✓ 将边(u,v)及结点涂成红色，扩充到T中； ✓ 调整候选蓝边集； ✓}
13
PRIM算法数据结构
✓ int dist[n][n]; //网络的邻接矩阵
✓ typedef struct ✓{
✓ int from,end; //边的起点和终点 ✓ int length; //边的权值 ✓ }edge; //边结构
✓ edge T[n-1]; //图的生成树
14
15
最小生成树——克鲁斯卡尔(Kruskal)算法
✓ 算法 ✓ 设连通网N={V，E}， ✓ 令最小生成树的初始状态为 ✓ 有n个顶点，无边的非连通图T=(V，Φ) ✓ 图中每一个顶点自成一个连通分量 ✓ 在E中选择权最小的边 ✓ 若此边依附的顶点落在T的不同的连通分量上，则将此边加入 到T中 ✓ 该边的加入将使两个连通分量合成一个连通分量 ✓ 否则该边的加入必然出现回路，所以舍去此边，选择下一条 代价最小的边 ✓ 依此类推，直到T 中所有顶点在同一连通分量上
✓ n个城市间建立通信网，只需n-1条线路 ✓ 如何在可能的线路中选择n-1条边，把所有城
市连起来，且总耗费(各边权值之和)最小 ✓ 找图中的最小生成树
8
PRIM算法
✓ 贪心法 ✓ 旅行推销员(TSP)问题
✓ 推销员从其中某一城市出发，唯一走遍n个城市， 再回到出发的城市，求最短的路线
✓ 在带权无向完全图中，访问每个顶点恰好一次、并且返 回出发点、总权数最小的回路
(d)
17
练习题
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
2015年12月30日
int LocateVex(MGraph G,VertexType u) { /* 初始条件:图G存在,u和G中顶点有相同特征 */ /* 操作结果:若G中存在顶点u,则返回该顶点在图中 位置;否则返回-1 */ int i; for(i=0;i<G.vexnum;++i) if(u==G.vexs[i]) return i; return -1; }
图：Graph=(V,E) V：顶点(数据元素)的有穷非空集合； E：边的有穷集合。 无向图： 每条边都是无方向的 有向图： 每条边都是有方向的
G1
V1 V2
V3
V4
G2
V1 V3 V4
2015年12月30日
V2
V5
完全图：任意两个点都有一条边相连
无向完全图 n(n-1)/2 条边
有向完全图 n(n-1) 条边
v2
v4
V4
空间效率为O(n+e) 出度 OD(Vi)＝单链出边表中链接的结点数 入度 ID(Vi)＝邻接点域为Vi的弧个数 度： TD(Vi) = OD( Vi ) + I D( Vi )
2015年12月30日
已知某网的邻接（出边）表，请画出该网络。
当邻接表 的存储结 构形成后， 图便唯一 确定！
数组（邻接矩阵）表示法
建立一个顶点表（记录各个顶点信息）和一个邻接矩 阵（表示各个顶点之间关系）。 设图 A = (V, E) 有 n 个顶点，则图的邻接矩阵是 一个二维数组 A.Edge[n][n]，定义为：
1, 如果 < i , j > E 或者 (i , j ) E A.Edge [i ][ j ] 0, 否则
V0 V3 V1 V2 V4 V5
2015年12月30日
有向图G 的极大强连通子图称为G的强连通分量。 极大强连通子图意思是：该子图是G的强连通子图 ，将D的任何不在该子图中的顶点加入，子图不再 是强连通的。 强连通分量
V0 V1 V0 V1
V2
V3
V2
V3
2015年12月30日
极小连通子图：该子图是G 的连通子图，在该子图 中删除任何一条边，子图不再连通。 生成树：包含无向图G 所有顶点的极小连通子图。 生成森林：对非连通图，由各个连通分量的生成树 的集合。
info
数据域，与 边有关信息 （如权值）
每个单链表有一个头结点（设为2个域），存vi信息；
每个单链表的头结点另外用顺序存储结构存储。
2015年12月30日
无向图的邻接表表示
v1 v3 v4 v5 v2 0 v1 1 v2 2 v3 3 v4 4 v5
3 1 ^
4
4 4
2
3 2
0
1 0
^
^ ^
2015年12月30日
无向图的邻接矩阵表示法
v1 v3 v4 v5 v2 顶点表： （ v1 v2 v3 v4 v5 ） 邻接矩阵：
0 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 0 0 0 1 0 1 1 0 0 v1 v2 v3 v4 v5
V0
V2 V3 (a) V4 V3 (b)
V1
V0
V2
V1
V0
V2
V1
V4
V3 (c)
2015年12月30日
V4
连通分量（强连通分量）
无向图G 的极大连通子图称为G的连通分量。 极大连通子图意思是：该子图是 G 连通子图，将G 的任何不在该子图中的顶点加入，子图不再连通。 非 V0 V1 V4 连 通 连通分量 V2 V5 图 V3
V2
V3
V2
非 强 连 通 V3 图 2015年12月30日
权与网 图中边或弧所具有的相关数称为权。表明从一个顶 点到另一个顶点的距离或耗费。带权的图称为网。 子图 设有两个图G=（V，{E}）、G1=（V1，{E1}）， 若V1 V，E1 E，则称 G1是G的子图。 例:(b)、(c) 是 (a) 的子图
V0 V2 V1 V0 V2 V1 V3 V0 V1
V3
V4
V3
V4
V2
V4
连通图 G1
G1的生成树
2015年12月30日
6.2 图的存储结构
顺序存储结构： 链式存储结构： 数组表示法（邻接矩阵） 多重链表
邻接表 邻接多重表 十字链表
重点介绍： 邻接矩阵(数组)表示法
邻接表(链式)表示法
2015年12月30日
//顶点信息 //指向第一条依附该顶点的边的指针 //AdjList表示邻接表类型 //邻接表 //图的当前顶点数和边数
A.Edge =
注：在有向图的邻接矩阵中， 第i行含义：以结点vi为尾的弧(即出度边）； 第i列含义：以结点vi为头的弧(即入度边）。
分析1：有向图的邻接矩阵可能是不对称的。 分析2：顶点的出度=第i行元素之和 顶点的入度=第i列元素之和 顶点的度=第i行元素之和+第i列元素之和
2015年12月30日
A.Edge =
分析1：无向图的邻接矩阵是对称的； 分析2：顶点i 的度＝第 i 行 (列) 中1 的个数； 特别：完全图的邻接矩阵中，对角元素为0，其余1。
2015年12月30日
有向图的邻接矩阵表示法
v1 v2 v4
A
v3
顶点表： 邻接矩阵：
( v1 v2 v3 v4 ) 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 v1 v2 v3 v4
2015年12月30日
稀疏图：有很少边或弧的图。 稠密图：有较多边或弧的图。 网：边/弧带权的图。 邻接：有边/弧相连的两个顶点之间的关系。 存在(vi, vj)，则称vi和vj互为邻接点； 存在<vi, vj>，则称vi邻接到vj， vj邻接于vi 关联(依附)：边/弧与顶点之间的关系。 存在(vi, vj)/ <vi, vj>， 则称该边/弧关联于vi和vj
2015年12月30日
邻接矩阵表示法的特点
优点：容易实现图的操作，如：求某顶点的度、判 断顶点之间是否有边、找顶点的邻接点等等。 缺点：n个顶点需要n*n个单元存储边;空间效率为 O(n2)。 对稀疏图而言尤其浪费空间。
2015年12月30日
邻接矩阵的存储表示
//用两个数组分别存储顶点表和邻接矩阵 #define MaxInt 32767 //表示极大值，即∞ #define MVNum 100 //最大顶点数 typedef char VerTexType; //假设顶点的数据类型为字符型 typedef int ArcType; //假设边的权值类型为整型 typedef struct{ VerTexType vexs[MVNum]; //顶点表 ArcType arcs[MVNum][MVNum]; //邻接矩阵 int vexnum,arcnum; //图的当前点数和边数 }AMGraph;
2015年12月30日
邻接表（链式）表示法
对每个顶点vi 建立一个单链表，把与vi有关联的边的信息链接 起来，每个结点设为3个域； 头结点 表结点
data
数据域，存 储顶点vi 信 息
firstarc
链域，指向 单链表的第 一个结点
adjvex nextarc
邻接点域，表 示vi一个邻接 点的位置 链域，指向 vi下一个边 或弧的结点
答：是树！而且是一棵有向树！
2015年12月30日
路径：接续的边构成的顶点序列。 路径长度：路径上边或弧的数目/权值之和。 回路(环)：第一个顶点和最后一个顶点相同的路径。 简单路径：除路径起点和终点可以相同外，其余顶点均不相同 的路径。 简单回路(简单环)：除路径起点和终点相同外，其余顶点均不 相同的路径。
3
2
1
^
注：邻接表不唯一，因各个边结点的链入顺序是任意的 空间效率为O(n+2e)。 若是稀疏图(e<<n2)，比邻接矩阵表示法O(n2)省空间。 TD(Vi)=单链表中链接的结点个数
2015年12月30日
有向图的邻接表表示
邻接表(出边) v1 v3 逆邻接表(入边)
1 ^
V1 V2 3 ^ 0 ^ V3 3 ^ 0 ^ 0 ^ 2 ^
网（即有权图）的邻接矩阵表示法
定义为： A.Edge[ i ][ j ]=
Wij ∞
<vi, vj> 或（vi, vj）∈VR 无边（弧）
v1 N 3 v6 7 6 v5
5
1
5
顶点表： ( v1 v2 v3 v4 v5 v6 ) ∞5 ∞5∞ 7 ∞ ∞∞ 邻接矩阵： ∞ ∞∞7∞ v2 ∞∞ ∞∞ ∞ 4 44 ∞∞∞∞∞ 8 N.Edge = ∞ ∞ 8∞ ∞ ∞9 9 8 ∞∞ ∞∞∞ v3 9 ∞∞ ∞∞ ∞ ∞ 55 ∞∞∞∞ 6 6 5 ∞∞ ∞∞ ∞ 5 ∞∞∞ ∞ 5∞ v4 ∞ 3 ∞∞ ∞1 ∞ 1∞ 3 ∞∞ ∞
2015年12月30日
顶点的度：与该顶点相关联的边的数目，记为TD(v) 在有向图中, 顶点的度等于该顶点的入度与出度之和。 顶点 v 的入度是以 v 为终点的有向边的条数, 记作 ID(v) 顶点 v 的出度是以 v 为始点的有向边的条数, 记作OD(v)
问：当有向图中仅1个顶点的入度为0,其 余顶点的入度均为1，此时是何形状？
2015年12月30日
采用邻接矩阵表示法创建无向网
【算法思想】
（1）输入总顶点数和总边数。 （2）依次输入点的信息存入顶点表中。 （3）初始化邻接矩阵，使每个权值初始化为极大值。 （4）构造邻接矩阵。
2015年12月30日
【算法描述】