数据结构 第七章-图2

每次调整的对象都是“最小不平衡子树”
插入操作
在插入操作，只要将最小不平衡子树调整平衡，则其他祖先结点都会恢复平衡
在A的左孩子的左子树中插入导致不平衡
由于在结点A的左孩子（L）的左子树（L）上插入了新结点，A的平衡因子由1增
至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作。
LL
将A的左孩子B向右上旋转代替A成为根节点 将A结点向右下旋转成为B的右子树的根结点
RR平衡旋转（左单旋转）
而B的原左子树则作为A结点的右子树
在A的左孩子的右子树中插入导致不平衡
由于在结点A的左孩子（L）的右子树（R）上插入了新结点，A的平衡因子由1增
LR
至2，导致以A为根的子树失去平衡，需要两次旋转操作，先左旋转再右旋转。
将A的左孩子B的右子树的根结点C向左上旋转提升至B结点的位置
本质：永远保证 子树0<关键字1<子树1<关键字2<子树2<...
当左兄弟很宽裕时，用当前结点的前驱、前驱的前驱来填补空缺 当右兄弟很宽裕时，用当前结点的后继、后继的后继来填补空缺
兄弟够借。若被删除关键字所在结点删除前的关键字个数低于下限，且与此结点 右（或左）兄弟结点的关键字还很宽裕，则需要调整该结点、右（或左）兄弟结 点及其双亲结点及其双亲结点（父子换位法）
LL平衡旋转（右单旋转）
而B的原右子树则作为A结点的左子树
在A的右孩子的右子树中插入导致不平衡
由于在结点A的右孩子（R）的右子树（R）上插入了新结点，A的平衡因子由-1
减至-2，导致以A为根的子树失去平衡，需要一次向左的旋转操作。
RR
将A的右孩子B向左上旋转代替A成为根节点 将A结点向左下旋转成为B的左子树的根结点

例
a c G1
b d
vexdata firstarc adjvex next 1 4 ^ a 2 3 4 b c d 1 1 3 ^ ^ ^
19
7.3 图的遍历
深度优先遍历(DFS) 深度优先遍历
方法：从图的某一顶点 出发，访问此顶点； 方法：从图的某一顶点V0出发，访问此顶点；然后依 次从V 的未被访问的邻接点出发，深度优先遍历图， 次从 0的未被访问的邻接点出发，深度优先遍历图， 直至图中所有和V 相通的顶点都被访问到； 直至图中所有和 0相通的顶点都被访问到；若此时图 中尚有顶点未被访问， 中尚有顶点未被访问，则另选图中一个未被访问的顶 点作起点，重复上述过程， 点作起点，重复上述过程，直至图中所有顶点都被访 问为止。 问为止。
ω ij , 若(v i , v j )或 < v i , v j >∈ E(G) A[i, j ] = 0，其它
11
例
1 3
5
2
8 4 7 5 1 6 3 4 2
0 5 7 0 3
5 0 0 4 8
7 0 0 2 1
0 4 2 0 6
3 8 1 6 0
12
关联矩阵——表示顶点与边的关联关系的矩阵 表示顶点与边的关联关系的矩阵 关联矩阵
1
7.1 图的定义和术语
是由两个集合V(G)和E(G)组成的 组成的, 图(Graph)——图G是由两个集合 图 是由两个集合 和 组成的 记为G=(V,E) 记为
其中： 其中：V(G)是顶点的非空有限集 是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或有序对 是边的有限集合， 是边的有限集合
有向图——有向图 是由两个集合 有向图G是由两个集合 有向图 有向图 是由两个集合V(G)和E(G)组成的 和 组成的

7.5 树的应用
➢判定树
在实际应用中，树可用于判定问题的描述和解决。
•设有八枚硬币，分别表示为a，b，c，d，e，f，g，h，其中有一枚且 仅有一枚硬币是伪造的，假硬币的重量与真硬币的重量不同，可能轻， 也可能重。现要求以天平为工具，用最少的比较次数挑选出假硬币， 并同时确定这枚硬币的重量比其它真硬币是轻还是重。
的第i棵子树。 ⑺Delete（t，x，i）在树t中删除结点x的第i棵子树。 ⑻Tranverse（t）是树的遍历操作，即按某种方式访问树t中的每个
结点，且使每个结点只被访问一次。
7.2.2 树的存储结构
顺序存储结构 链式存储结构 不管哪一种存储方式，都要求不但能存储结点本身的数据 信息，还要能够唯一的反映树中各结点之间的逻辑关系。 1.双亲表示法 2.孩子表示法 3.双亲孩子表示法 4.孩子兄弟表示法
21
将二叉树还原为树示意图
A BCD
EF
A
B
C
E
D
F
A
B
C
E
D
F
22
练习：将下图所示二叉树转化为树
1 2
4
5
3
6
2 4
1 53
6
23
7.3.2 森林转换为二叉树
由森林的概念可知，森林是若干棵树的集合，只要将森林中各棵树 的根视为兄弟，森林同样可以用二叉树表示。 森林转换为二叉树的方法如下：
⑴将森林中的每棵树转换成相应的二叉树。 ⑵第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树 的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来 后，此时所得到的二叉树就是由森林转换得到的二叉树。
相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）本身又是 一棵树。树T1，T2，…，Tm称为这个根结点的子树。 • 可以看出，在树的定义中用了递归概念，即用树来定义树。因此， 树结构的算法类同于二叉树结构的算法，也可以使用递归方法。

6.2 图的存储结构
➢图的邻接矩阵存储表示
6.2 图的存储结构
➢采用数组表示法构造无向网G
• 输入顶点数、边数等基本数据 • 输入各顶点信息，构造顶点向量 G.vexs[n] • 初始化邻接矩阵 G.arcs • 输入各条边所依附的顶点及权值，写入邻接矩阵G.arcs
6.2 图的存储结构
➢采用邻接矩阵表示法，创建无向网G
图的定义和术语
• 对于有n个顶点的图，最多有多少条弧？ （不考虑自身到自身的弧）
每个顶点最多向其它n-1个顶点分别发出一条弧 所以
• n个顶点的有向图最多可以有 n（n-1）条弧 • 考虑无向图的情况： • n个顶点的无向图最多可以有n(n-1)/2 条边
• 弧（边）数达到最大的图称作完全图
• 有很少（如e<nlogn）弧（边）的图称为稀疏图 • 反之称为稠密图
图的定义和术语
• 无向图G=（V，{E}） • 从顶点v到顶点v’的路径 是由v出发到达v’的顶点序列 • 若为有向图，则路径也是有向的 • 第一个顶点和最后一个顶点相同的路径叫做回路或环 • 序列中顶点不重复出现的路径称为简单路径 • 除了第一个顶点和最后一个顶点之外，其余顶点不重复
出现的回路称为简单回路或简单环
图的定义和术语
• 无向图G中，如果从顶点v到v’有路径， 则称v和v’是连通的
• 对于任意两个顶点都连通的图，叫做连通图 • 无向图中的极大连通子图叫做连通分量
v1
v2
v3
v4
v5
图的定义和术语
• 有向图中， • 对于任意两个顶点都存在双向路径的图，叫做强连通图 • 有向图中的极大强连通子图叫做强连通分量
6.2 图的存储结构
➢数组表示法

边（edge） 无向图中两条弧<x,y>和<y,x>可用一条边（ x,y ）来表示 。
完全图（completed graph） 具有 n*(n-1)/2 条边的无向图称为完全图。
有向完全图（completed directed graph） 具有 n*(n-1) 条弧的有向图称为有向完全图。
稀疏图（sparse graph） 边数很少的图称为稀疏图。
第七章. 图 （Chapter 7. Graph)
图型结构是一种非常重要的、比线性和树型结构更复 杂的非线性数据结构，可广泛用于描述自然界各种关系。
§7.1 图的定义及基本操作
Graph = （V,R） 其中：V={ ai | ai∈D0, i=1,2,…,n, n≥0 }
R={ E } E={ <x,y> | P(x, y)∧（x, y∈V) }
vtx = 1.. vtxnum; edge = 1.. edgenum; bit = -1.. 1; graph = ARRAY[ vtx , edge ] OF bit;
链式存储结构：
A
B
C
√ 1、邻接表（adjacency list)
F
E
D
按结点出度建立：
TYPE
头结点 vexdata firstarc
ENDP;
PROC dfs ( g : graph; v : vtx ); visit ( v ); visited[ v]:=true; w:=FIRSTADJ ( g , v ); While w≠0 Do Begin If Not visited[ w] Then dfs ( g , w); w:= NEXTADJ ( g , v , w) End

依此类推，直至T中所有顶点都在同一连通分量上为 止。
三、Kruskal算法
例
6
1
5
2
1
4
5
5
3
3 6
42
5
6
6
1
2 51
4
3
3
2 4
5
6
三、Kruskal算法
练习
12
A
B
A
8 21 13
19
F
9
C
33
14
9
E
D
E
18
边权值总和：8+9+12+13+18=60
12
B
13
8
F
9
C
18
D
四、Prim算法的计算机实现
二、Prim算法
❖算法思想
❖ 设G=(V,{E})是连通网，TE是G上最小生成树中边的集合， 则Prim算法通过以下步骤得到最小生成树：
初始状态：U = {u0}，TE = {}。其中u0是顶点集合 V中的某一个顶点；
在所有u∈U，v∈V-U的边(u,v)∈E中找一条权值最 小的边(u0，v0)，将这条边加进集合TE中，同时将 此边的另一顶点v0并入U；
小生成树。
7.5 最小生成树
❖问题分析
n个城市间，最多可修建n(n-1)/2条公路。 n个村镇间建立公路网，只需n-1条公路。 问题转化为：如何在可能的公路中选择n-1条，能把所有
村镇（顶点）均连起来，且总耗费（各边权 值之和）最小。
一、基本概念
1. 图的生成树 若G 是连通图G的子图，并有： V(G ') = V(G),
一、基本概念

v3
v4 v5 v4
v3
v5 v4
v3
v5 v4
v3
v5 v4
v3
v5
注
一个图可以有许多棵不同的生成树。 所有生成树具有以下共同特点： 生成树的顶点个数与图的顶点个数相同； 生成树是图的极小连通子图； 一个有 n 个顶点的连通图的生成树有 n-1 条边； 生成树中任意两个顶点间的路径是唯一的； 在生成树中再加一条边必然形成回路。 含 n 个顶点 n-1 条边的图不一定是生成树。
A1 = {< v1, v2>, < v1, v3>, < v3, v4>, < v4, v1>} v1 v2
有向图
v3
v4
制作：计算机科学与技术学院 徐振中
数据结构 边：若 <v, w>∈VR 必有<w, v>∈VR，则以 无序对 (v, w) 代表这两个有序对，表示 v 和 w 之 间的一条边，此时的图称为无向图。 G2 = (V2, E2) V2 = {v1, v2, v3, v4, v5}
第七章 图
E2 = {(v1, v2), (v1, v4), (v2, v3), (v2, v5) , (v3, v4), (v3, v5)} v1
G2
v3
v2
无向图
v4
v5
制作：计算机科学与技术学院 徐振中
数据结构
第七章 图
例：两个城市 A 和 B ，如果 A 和 B 之间的连线的涵义是 表示两个城市的距离，则<A, B> 和 <B, A> 是相同的， 用 (A, B) 表示。 如果 A 和 B 之间的连线的涵义是表示两城市之 间人口流动的情况，则 <A, B> 和 <B, A> 是不同的。 北京 <北京，上海> (北京，上海) <上海，北京> <北京，上海> 北京 上海 上海

7.2.1邻接矩阵
邻接矩阵是表示顶点之间相邻关系的矩阵。用二维数 组A[n][n]的矩阵存储图中顶点信息表示各顶点间的相邻 关系。矩阵元素A[i][j]的值表示为顶点vi(行)与顶点vj(列) 间的关系。 G的邻接矩阵是满足如下条件的n阶矩阵： 1 若(vi,vi+1)E 或 <vi,vi+1>E A[i][j]= 0 否则
v1
v2
v3
有向图G5
0 1 2 3
v4
v1 v2 v3 v4 顶点表 ^
2
1
^
0 1
v1 v2 v3 v4 顶点表
3 0 0 2
^ ^ ^ ^
3 0
^ ^
2 3
出边表
入边表
v1 v3
2
v2
v4
3 4 4 2 2 1
v5
0 1
0 1 2 3 4
v1 v2 v3 v4 v5
^ ^ ^
^
2 3 0 1
V0
V1
V2 G 图示
V3
图的应用举例： 例1 交通图（公路、铁路） 顶点：地点 边：连接地点的公路 交通图中的有单行道双行道，分别用有向边、无向边 表示； 例2 电路图 顶点：元件 V0 V1 边：连接元件之间的线路 V2 例3 通讯线路图 V3 V4 顶点：地点 边：地点间的连线 V0 V1 例4 各种流程图 如产品的生产流程图 顶点：工序 V2 V3 边：各道工序之间的顺序关系
V0 V2 V3 V4 V1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0
邻接矩阵的性质
(1) 图中各顶点序号确定后，图的邻接矩阵是唯一确定的； (2) 无向图和无向网的邻接矩阵是一个对称矩阵； (3) 无向图邻接矩阵中第i行（或第i列）的非0元素的个数 即为第i个顶点的度； (4) 有向图邻接矩阵第i行非0元素个数为第i个顶点的出度， 第i列非0元素个数为第i个顶点的入度，第i个顶点的度 为第i行与第i列非0元素个数之和； (5) 无向图的边数等于邻接矩阵中非0元素个数之和的一半， 有向图的弧数等于邻接矩阵中非0元素个数之和。 需要说明的是邻接矩阵表示法对于以图的顶点为主的运算 比较适用。此外，除完全图外，其他图的邻接矩阵有许 多零元素，特别是当n值较大，而边数相对完全图的边 (n-1)又少得多时，则此矩阵称为“稀疏矩阵”，浪费存 储空间。

7.2.1 冒泡排序
• 排序过程 – 将第一个和第二个元素的关键字进行比较，若为逆序 ，则将两个元素互换；接着比较第二个和第三个元素 的关键字，依次类推，直至最后两个元素的完成比较 ，这称为第一趟冒泡排序。第一趟排序分划出一组元 素个数为n-1的待排序列和一个关键字最大的元素。 – 第i趟对前n - i + 1个的元素进行类似的排序操作，得到 一组元素个数为n - i的待排序列和一个（在前n-i+1个元 素中）关键字最大的元素。 – 这样不断分划直至一趟分划时无元素互换为止。
34 28 81 79 63 28 34 81 79 63 28 34 79 81 63
第一趟
28 34 79 63 81
第二趟
28 34 63 79 81
初始
7.2.1 冒泡排序
• 冒泡排序算法
template<class ElemType> void BubbleSort(ElemType data[], int n) { int lastSwapIndex = n - 1; //用于记录最后一次交换的元素下标 int i, j; for (i = lastSwapIndex; i > 0;i = lastSwapIndex){ lastSwapIndex = 0; for (j = 0; j < i; j++) if (data[j] > data[j + 1]){ Swap(data[j],data[j + 1]); lastSwapIndex = j; } } }
数 据 结 构
第7章 排序
概述
• 什么是排序？ – 排序是计算机内经常进行的一种操作，其目的是将一 组“无序”的元素序列调整为“有序”的元素序列。 – 假设含n个记录的序列为{ R1, R2, …， Rn }，其相应的 关键字序列为 { K1, K2, …，Kn }。这些关键字相互之 间可以进行比较，即在它们之间存在着这样一个关系 ： Kp1≤Kp2≤…≤Kpn （或≥） 按此关系将上面记录序列重新排列为： { Rp1, Rp2, …，Rpn } 的操作称作排序。

9个顶点 个顶点
8个顶点的无向图最多有 条边且该图为连通图 个顶点的无向图最多有28条边且该图为连通图 个顶点的无向图最多有 连通无向图构成条件:边 顶点数 顶点数-1)/2 顶点数*(顶点数 连通无向图构成条件 边=顶点数 顶点数 顶点数>=1,所以该函数存在单调递增的单值反 顶点数 所以该函数存在单调递增的单值反 函数,所以边与顶点为增函数关系 所以28个条边 函数 所以边与顶点为增函数关系 所以 个条边 的连通无向图顶点数最少为8个 所以28条边的 的连通无向图顶点数最少为 个 所以 条边的 非连通无向图为9个 加入一个孤立点 加入一个孤立点) 非连通无向图为 个(加入一个孤立点
28
无向图的邻接矩阵为对称矩阵
2011-10-13
7.2
图的存储结构
Wij 若< vi,vj > 或<vj,v i > ∈E(G)
若G是网（有权图），邻接矩阵定义为 是网（有权图）， ），邻接矩阵定义为
A [ i，j ] = ， 0或 ∞
如图： 如图：
V1
若其它
V2
3 4
2
V3
2011-10-13
C
A
B
D 2011-10-13 (a )
3
Königsberg七桥问题
• Königsberg七桥问题就是说，能否从某点出发 通过每桥恰好一次回到原地？
C
C
A B
．
A D
B
D (a)
2011-10-13
(b)
4
第七章 图
7.1 图的定义 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路径
2011-10-13

非简单图
2020/9/30
3
7.1 图的逻辑结构
7.1.1 图的定义
● 相关概念 无向图和有向图
● 无向图：如果图中顶点 vi 和 vj 之间的边无方向，则称这条边为无向边， 用无序偶对 (vi, vj) 表示，称该图为无向图。
● 有向图：如果图中顶点 vi 和 vj 之间的边有方向，则称这条边为有向边， 用有序偶对 <vi, vj> 表示，称该图为有向图。
无论有向图还是无向图，顶点数 n、边 数 e 和度数之间满足：
2020/9/30
8
7.1 图的逻辑结构
7.1.1 图的定义
● 相关概念 权和网
● 权：权通常是指对图中边赋予的有意义的数值量。在实际应用中，权 可以有具体的含义。
● 网：如果将图中的每条边上都赋上一个权值，则称这种图为网，或称 为有权图 。
2020/9/30
6
7.1 图的逻辑结构
7.1.1 图的定义
● 相关概念 稀疏图和稠密图
● 稀疏图：边数很少的图称为稀疏图，如果 e 表示图中的边数，n 表示 图中的顶点数，则 e＜nlogn。
● 稠密图：边数很多的图称为稠密图，如果 e 表示图中的边数，n 表示 图中的顶点数，则 e≥nlogn。
2020/9/30
无向完全图
有向完全图
5
7.1 图的逻辑结构
7.1.1 图的定义
● 相关概念 邻接和依附
● 邻接：对图 G=(V, VR)，如果边 (vi, vj)∈VR，则称顶点 vi 和 vj 互为邻 接点；如果弧<vi, vj>∈VR，则称顶点 vi 邻接到 vj，vj 邻接自 vi。
● 依附：对图 G=(V, VR)，如果边 (vi, vj)∈VR 或弧 <vi, vj>∈VR，则称 边 (vi, vj) 或弧 <vi, vj> 依附于顶点 vi 和 vj。