01 3.1数据结构基本概念
3.2 抽象数据类型
3.3 线性表
3.4 栈和队列
3.5 树和二叉树
3.6 图
3.7 文件的组织
02
03
04
05
06
07
Con
tent
s 目录
1
树的定义
树（Tree）是n(n≥0)个结点的有限集合T，满足两个条件： 有且仅有一个特定的称为根（Root）的结点，它没有前趋； 其余的结点可分成m个互不相交的有限集合T1,T2,…,Tm，其中每个集合
又是一棵树，并称为根的子树。
树
树的定义
树（Tree）是n(n≥0)个结点的有限集合T，满足两个条件： 有且仅有一个特定的称为根（Root）的结点，它没有前趋； 其余的结点可分成m个互不相交的有限集合T1,T2,…,Tm，其中每个集合
又是一棵树，并称为根的子树。
树
树是递归结构—— 在树的定义中又用到了树的概念
树的逻辑结构
4
a
b d c e
f h g i j l m n k
层次结构
一多对
非线性
线性结构便不足以方便地 描述这样的复杂情形
树
树的相关术语
5
A
G
D C B
F E
指树中的一个元素，包含数据项及若干指向其子树的分支
结点的子树的根称为该结点的孩子
一个结点的直接上层结点称为该结点的双亲
同一双亲的孩子结点
B、C、D是A的孩子，E、F是B的孩子
A是B、C、D的双亲，B是E、F的双亲
B、C、D是兄弟关系
树的结点
孩子结点
双亲结点
兄弟结点
树的相关术语
6
A
G
D C B
F E
结点层
树的深度
树的度
叶子结点
分枝结点
有序树
森林
Level 1
Level 2
Level 3
根结点的层定义为1；根的孩子为第二层结点，依此类推；
树中最大的结点层
度不为0的结点
也叫终端结点，是度为0的结点
树中最大的结点度 结点子树的个数
不考虑子树的顺序 子树有序的树
互不相交的树集合
结点的度
无序树
树的基本术语——示例
7
E,K,L,G,
H,I,M
树的存储 顺序存储方式
顺序存储时，首先必须对树形结构的结点进行某种方式的线性化，
使之成为一个线性序列，然后存储。
链式存储方式
链式存储时，使用多指针域的结点形式，每一个指针域指向一棵
子树的根结点。
树的存储 顺序存储方式
顺序存储时，首先必须对树形结构的结点进行某种方式的线性化，
使之成为一个线性序列，然后存储。
链式存储方式
链式存储时，使用多指针域的结点形式，每一个指针域指向一棵
子树的根结点。
由于树的分支数不固定，很难给出一种固定的存储结构，所以本章的剩余内容将集中介绍二叉树
二叉树的基本概念
二叉树是n（n≥0）个结点的有限集，它或为空树（n=0），或由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树构成。
二叉树
说明：二叉树是每个结点最多有两个子树的有序树。二叉树的子树通常称为"左子树"（left subtree）和"右子树"（right subtree）。左、右子树的顺序不能互换。
A
F
G
E D
C B
二叉树是递归定义，在二叉树的定义中又用到了二叉树的概念
二叉树的概念
11
二叉树的概念
12
二叉树与树的区别是什么？
思考&讨论
二叉树的概念
13
二叉树与树的区别是什么？
思考&讨论
讨论：尽管二叉树与树有许多相似之处，树和二叉树的两个主要差别： （1）树中结点的最大度数没有限制，而二叉树结点的最大度数为2； （2）树的结点无左、右之分，而二叉树的结点有左、右之分，
二叉树的五种基本形态
R R
L-SubTree
R R-SubTree
R
L-SubTree
R-SubTree
根仅有一棵子树时，也要分辨是左子树还是右子树。
二叉树的特殊形态——满二叉树
15
一颗深度为k且有2k -1个结点的二叉树称为满二叉树
二叉树的特殊形态——完全二叉树
16
(a)满二叉树 (b)完全二叉树 (c) 不是完全二叉树
如果一个深度为k的二叉树，它的结点按照从根结点开始
，自上而下，从左至右进行连续编号后，得到的顺序与满二叉树相应结点编号顺序一致，则称这个二叉树为完全二叉树。
二叉树的存储——顺序存储
一般二叉树的存储
在一棵完全二叉树中，按照从根结点起，自上而下，从左至右的方式对
结点进行顺序编号，便可得到一个反映结点之间关系的线性序列。
一般二叉树的顺序存储是首先将二叉树映射为完全二叉树（通过虚结
点），然后再用完全二叉树的方式存储。
A
B C
D E F
G
A
B C
D E F
G
A B C D E F G
(a) 待存储二叉树 (b)转为完全二叉树（线性化） (c)顺序存储
二叉树的存储——链式存储
二叉树的链式存储
以类似单链表中的链表示树中的弧，
即可得到二叉链表。
A
B C
D E F
G
A
B C
D E F
G
^
^ ^ ^
^ ^
^ ^
(a)二叉树 (b)二叉链表
19
二叉树的运算——遍历
对结点的处理，如修改结点数据、输出结点数据。
按某种顺序访问数据结构中的结点，要求每个结点访问一次且仅
访问一次。
遍历对线性结构是容易解决的，而二叉树是非线性的，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历。
如何访问二叉树的
每个结点，而且每个结点仅被访问一次？
C B
A
D
F
E
访 问
二叉树的遍历
二叉树的运算——遍历
两种遍历的方法
——深度优先遍历
——广度优先遍历
遍历是二叉树中最主要的运算
二叉树的深度优先遍历
1
2 3
2
1 3
3
1 2
二叉树的深度优先遍历
规定左子树在右子树之前访问，则按照访问根的时机，定义出三
种次序：先序（前序）、中序和后序遍历。
(a)先序遍历 (b)中序遍历 (c)后序遍历
深度遍历策略——先序遍历
22
若二叉树非空，则依次进行以下操作
（1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树；
A
B C
D E F G
L
深度遍历策略——先序遍历
23
若二叉树非空，则依次进行以下操作
（1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树；
A
B C
D E F G
L
先序遍历：A B D E C F L G
深度遍历策略——中序遍历
24
若二叉树非空，则依次进行以下操作
（1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树；
A
B C
D E F G
L
深度遍历策略——中序遍历
25
若二叉树非空，则依次进行以下操作
（1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树；
A
B C
D E F G
L
中序遍历：D B E A L F C G
深度遍历策略——后序遍历
26
若二叉树非空，则依次进行以下操作
（1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点；
A
B C
D E F G
L
深度遍历策略——后序遍历
27
若二叉树非空，则依次进行以下操作
（1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点；
A
B C
D E F G
L
后序遍历：D E B L F G C A
二叉树的广度优先遍历
二叉树的广度优先遍历
按层次自根结点向下，每层自左向右进行处理。
A
B E
C D F
A
B E
C D F
A
B E
C D F
A
B E
C D F
二叉树的应用——引子
29
数字通信系统模型
信息发布者
信息接收者
信源编码——将信源发出的消息符号转换为适合信道传输的符号。
信源译码——按照编码的逆过程，将信息还原为原来的形式。
二元信道(常用)
信源编码 信源编码
•编码或代码（code）通常指一种在人和机器之间进行信息转换的系统（体系）。换句话说，编码便是交流。
•在信源编码中，除了使信息数字化，还强调使用尽量少的数据代表尽量多的信息。
定长与变长码
定长码与变长码
•信源编码可以采用定长码（每个字符用固定长度二进制码字表示），也可以采用变长码（每个字符使用不一样长度的二进制码字表示）。
a b c d e F
频率(千次) 45 13 12 16 9 5
定长码 000 001 010 011 100 101
变长码 0 101 100 111 1101 1100
文件中共有100000个字符,其中只有a,b,c,d,e共5种字符,每种字符出现的频率如下表.
例
采用定长码和变长码方案的文件编码总长度分别为300000位和224000位.
前缀码
前缀码
•任何一个字符的代码都不是其它字符代码的前缀,称这种性质为编码的前缀性质,简称为前缀码.
•编码的前缀性质保证了译码过程的正确性。
a b c d e F
频率(千次) 45 13 12 16 9 5
定长码 000 001 010 011 100 101
变长码 0 101 100 111 1101 1100
哈夫曼树的编码和译码示例
A B C D E
1
0
1
1
0 0 0 1
A：00 B:010 C：011 D：10 E：11
EAEBAECDEA
A：00 B:010 C：011 D：10 E：11
1100110100011011101100
ASC II码：10字节 22比特<3字节
编码
译码
哈夫曼树的概念
34
D
C
A B 4
7 5
2
路径
结点的权
结点的带权路径长度
树的带权路径长度
(Weighted Path Length)
若存在一个结点序列k1,k2,…,kj，可使k1到达kj,
则称这个结点序列是k1到达kj的一条路径
具有一定含义的比例系数。如"词频"
路径长度 路径经过的边的数目
结点的路径长度 从根到该结点的路径长度
从根到该结点的路径长度与该结点权的乘积
n
i i
i 1
WPL W L
n ——叶子结点的数目 Wi——第i个叶结点的权值，i=1,2,...n Li——第i个叶结点的路径长度，i=1,2,...n
哈夫曼树（Huffman Tree）
C D A B
4 7 5 2
在有n个带权叶子结点的所有二叉树中，带权路径长度WPL最
小的二叉树被称为最优二叉树或哈夫曼树。
哈夫曼树
哈夫曼树的构造
哈夫曼树的构造方法
(1)根据给定的n个权值{w1, w2,…,wn}构成n棵二叉树的集合F＝
{T1,T2,…,Tn }, 其中Ti中只有一个权值为wi的根结点，左、右子
树均为空。
(2)在F中选取两棵根结点的权值最小的树作为左、右子树构造一棵
新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结
点的权值之和。
(3)在F中删除这两个棵权值最小的树，同时将新得到的二叉树加入
F中。
(4) 重复(2)、(3)直到F中仅剩一棵树为止。这棵树就是哈夫曼树。
示例：权值为0.4、0.3、0.1、0.1、0.02、0.08的6个叶子结点A、B、C、D、E、F构造哈夫曼树。
哈夫曼编码和译码
哈夫曼编码
从哈夫曼树根结点开始，对左子树分配代码0，右子树分配代码1，一直
到达叶子结点为止，然后将从树根沿每条路径到达叶子结点的代码排列
起来，便得到了哈夫曼码。
A B C D E
1
0
1
1
0 0 0 1
A：00 B:010 C：011 D：10 E：11
EAEBAECDEA
A：00 B:010 C：011 D：10 E：11
1100110100011011101100
ASC II码：10字节 22比特<3字节
编码
译码
树-思考与练习
思考
•掌握二叉树的特点、基本性质、存储方法；
•理解二叉树的遍历方法；
•理解哈夫曼编码算法。
上机练习
•电子版(PDF)讲义4中的4-19,4-20,4-21,4-22
01 3.1数据结构基本概念
3.2 抽象数据类型
3.3 线性表
3.4 栈和队列
3.5 树和二叉树
3.6 图
3.7 文件的组织
02
03
04
05
06
07
Con
tent
s 目录
40
主要内容
• 图
• 图的应用
41
学习目标
• 理解图及图结构的描述
• 掌握图的遍历
• 掌握Dijkstra算法解决图的最短路径问
题
42
图引例1——地图染色问题
3
1
2
3
2 3
3
4
四色猜想 四色定理
1852年英国人 发现现象
1976年美国人 计算机证明
每幅地图最多可以用四种颜色着色，使得相邻区域不重色 43
图引例1——地图染色问题
44
图引例1——地图染色问题
信息与信息间的联系如何 抽象后存储到计算机中？
陕西 河南
安徽
湖北 四川
山西
贵州
湖南
广东 广西
福建
浙江
江西
江苏
山东
45
图引例2——搜索引擎与网站的结构
其他网站
频道页2
首页
频道页3
标签
频道页1
内容页2 内容页3内容页1
搜索引擎的工作原理是按照一定的搜索策略搜索网络并搜集信息，在对信息进行组织和处理后存储在自己的数据库中，以便为用户提供快速检索服务。完成网络信息搜索任务的软件俗称"网络蜘蛛"或"网络爬虫"，网络蜘蛛是通过网站的站内链接来遍历网站内容的。
网站内链接结构
46
图引例2——搜索引擎与网站的结构
（a）网站链接 （b）网站间的链接抽象
47
图引例3——最短路线问题
路线图 城市：顶点={a, b, c, d, e} 路线：顶点间连线={ab, ad, bc , be, de} 问题描述：求出从d到c的最短路线。
49
图的讨论
【思考与讨论】从实际问题中抽象出来的数据结构的"图"有什么特点？
50
图的讨论
【思考与讨论】从实际问题中抽象出来的数据结构的"图"有什么特点？
51
数据结构中的图是拓扑意义上的图，其特点为：
用点表示对象，有直接联系的对象用线连接起来。
图形中连线的长短曲直和结点的位置无关紧要，每一条线两端都
有结点。
图的概念
图(G)是一种非线性数据结构，它由两个集合V(G)和E(G)组成，形式上记
为：G=( V, E )。其中V(G)是顶点(Vertex)的非空有限集合，E(G)是V(G)中任意两
个顶点之间的关系集合，又称为边(Edge)的有限集合。
图
元素结点之间的关系可以是多对多的
52
图的类型
有向图
•当且仅当图G的每条边有方向，称G为有向图，如下图(a) 。有向边记为〈
起始顶点，终止顶点〉。有向边又称为弧，因此弧的起始顶点就称为弧尾，终止顶点称为弧头。
无向图
•G为无向图当且仅当G中的每条边是无方向的，如下图(b) 。记法：无向图用两个顶点组成的无序对表示，即(顶点1，顶点2)。
A
B C
A
B C
（a） （b）
顶点集合V={A,B,C}； 边集合E={(A,B),(B,C),(A,C)}；
顶点集合V={A,B,C}； 边集合E={<A,B>,<B,A>,<B,C>,<A,C>}；
53
图的基本术语——图
有很少条边或弧（如e<nlogn，n是图的顶点数，e是边数或者弧数）的图称为稀疏图；反之称为稠密图。
稀疏图与稠密图
54
图的基本术语——顶点与边
邻接点
关联边
边的两个顶点
55
若存在边e= (v, u), 则称顶点v、u 关联边e，或者称边e和顶点v、u 关联。
图的基本术语——度
度
•与树相似，图中的顶点也有度的概念：在无向图中关联于某一顶点vi的边
的数目称为vi的度，记为D(vi)。在有向图中，把以顶点vi为终点的边的数目
称为vi的入度，记为ID(vi)；把以顶点vi为起点的边的数目称为vi的出度，记
为OD(vi)；把顶点vi的度定义为该顶点的入度和出度之和。
A
B C
A
B C
（a） （b）
（a）A的出度为2，入度为1，度为3。 （b）A的度为2。
56
图的基本术语——权与网
网络
•图中的边还可以标注一个数值特征，称为该边的权值。图中的每条边都具
有权值时，这个带权图被称为网络，简称为网。
A
B C
5 1
3
A
B C
1 5
2
3
（a） （b）
57
图的基本术语——路径
路径
•若从顶点v1出发，沿着一些边经过顶点v1, v2, …, vn-1到达顶点vn，则称顶点
序列(v1,v2,v3, …,vn-1, vn)是从v1到vn的一条路径。
A
B C
A
B C
（a） （b）
图 (a)中，A,B,C是一条路径，在图 (b)中，A,B,C也是一条路径。
58
子图 设有两个图G=（V，E）、G1=（V1，E1），若V1 V，E1 E，E1关联的
顶点都在V1中，则称 G1是G的子图；
(b)、(c) 是 (a) 的子图
图的基本术语——子图
59
图的基本术语——连通图与强连通图
在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任
意两个顶点之间都连通，则称该图为连通图，否则，称该图为非连通图。
在有向图中的对应概念是强连通图与非强连通图。
连通图与非连通图
连通分量 无向图G的一个极大连通子图称为G的一个连通分量（或连通分支)。
有向图中的对应概念是强连通分量。 60
图的基本术语——生成树
生成树 包含无向图G 所有顶点的的极小连通子图称为G 的生成树。
61
图的存储方案讨论
• 邻接矩阵 • 邻接表 • 等
• 顶点值
• 顶点的数据 • 顶点间的关系
图的信息
顶点信息
边的信息
存得进 取得出
A
存数值 存联系
B 62
图的存储
图的存储方式
•图在计算机中的表示，即图中的顶点和边信息的表示。
– 可以将顶点和边视为两个集合分别进行，例如邻接矩阵表示法；
– 或者参考树的二叉链表方法，将边与顶点的表示结合起来，如邻接
表表示法。
1
3 4
2
1 2 3 4
V： E：
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 2 3 4
2 3
1 1
4 ^
3 4
1 ^
63
图的数组表示法——邻接矩阵
图 边 用一个二维数组存放
顶点 用一个一维数组存放
邻接矩阵
有向图邻接矩阵
无向图邻接矩阵
邻接矩阵
64
图的邻接矩阵存储
邻接矩阵表示法
•使用一个一维数组来存放图中每个顶点的数据信息，使用一个二维数组（
又称为邻接矩阵）来表示图中各顶点之间的关系。
1 2 3 4
V： E：
0 0 0 1
1 0 0 0
1 0 0 0
0 0 1 0
1 2 3 4
V： E：
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1
3 4
2
1
3 4
2
65
图的邻接表存储
邻接表表示法
•顶点表采用顺序存储：除了存储顶点信息，还引领一个与该顶点相邻接的
所有边的单链表(称为邻接链表)。
•注意对于有向图，根据引领的边以自身为出发顶点还是到达顶点不同，邻
接表表示方法有出边表和入边表两种。
1
3 4
2
66
1
3 4
2
1 2 3 4
^ 2 3 ^
4 ^ 1 ^
1 2 3 4
4 ^ 1 ^ 1 ^ 3 ^
出边表
入边表
1 2 3 4
2 3
1 1
4 ^
3 4
1 ^ ^ ^
图的遍历 图的遍历
•图的遍历是指从图中某一顶点出发，沿着某条搜索路径对图中每
个顶点进行一次访问。
对无向图，有向图都适用
广度优先遍历 Breadth-First Search
深度优先遍历Depth_FirstSearch
基本 遍历 策略
67
图的深度优先遍历
图的深度优先遍历
•假设初始状态是图中所有顶点都未被访问的前提下，这种方法从
图中某一顶点vi出发，访问此顶点，并进行标记，然后依次搜索vi
的每个邻接点vj；
•若vj未被访问过，则对vj进行访问和标记，然后依次搜索vj的每个
邻接点; ……直到图中和vi有路径相通的顶点都被访问。
•若图中尚有顶点未被访问过（非连通的情况下），则另选图中的
一个未被问的顶点作为出发点，重复上述过程，直到图中所有顶点
都被访问为止。
68
图的深度优先遍历
图的深度优先遍历
•深度优先遍历是一个递归的过程；
•在访问了顶点vi后，访问vi的一个邻接点vj ；访问vj之后，又访问vj的
一个邻接点；以此类推。在此过程中，尽可能地向纵深方向搜索，所
以称为深度优先遍历；
•如果顶点vi 的邻接点均被访问过，那么要回溯(类似递归调用返回)。
A
B E
D
C
A
B E
D
C
ABCED
69
深度优先遍历的结果不唯一
深度优先遍历算法——基本思想
深度优先遍历实现方法
需要一个栈来保存遍历经过的顶点顺序，以便按出栈的顺序返
回已走过的路线，回到上层以继续深度优先遍历其他分支。
70
图的广度优先遍历
图的广度优先遍历
•假设初始状态是图中所有顶点都未被访问的条件下，这种方法从
图中某一顶点vi出发，访问vi；
•然后依次访问vi的邻接点vj。在所有的vj都被访问之后，再访问vj的
邻接点vk，此次类推，直到图中所有和初始出发点vi有路径相通的
顶点都被访问为止。
•若图是非连通的，则选择一个未曾被访问的顶点作为起始点，重
复以上过程，直到图中所有顶点都被访问为止。
A
B E
D
C
A
B E
D
C
ABEDC
71
广度优先遍历的结果不唯一
广度优先遍历算法——基本思想
广度优先遍历实现方法
• 根据广度遍历思想，先访问的结点，其邻结点也会先被访
问。例如，如果vi在vj之前访问，那么vi的邻接点也应在vj
的邻接点之前访问。故采用队列来构造遍历顺序。
72
广度优先遍历算法示例
73
以左图为例说明，从结点1开始
2
1
3
4
5
6
7
8
9
visited[]
0 1 2 3 4 5 6 7 8
queue
初始状态
广度优先遍历算法示例
74
以左图为例说明，从结点1开始
2
1
3
4
5
6
7
8
9
visited[]
0 1 2 3 4 5 6 7 8
queue
初始状态
1visited[]
0 1 2 3 4 5 6 7 8
1queue
遍历结点1并将其入队
2
1
3
4
5
6
7
8
9
广度优先遍历算法示例
75
1visited[] 1 1
0 1 2 3 4 5 6 7 8
2 3queue
遍历结点2和3并将其入队
2
1
3
4
5
6
7
8
9
广度优先遍历算法示例
76
1visited[] 1 1
0 1 2 3 4 5 6 7 8
2 3queue
遍历结点2和3并将其入队
2
1
3
4
5
6
7
8
9
1visited[] 1 1 1 1
0 1 2 3 4 5 6 7 8
3 4 5queue
遍历结点4和5并将其入队
2
1
3
4
5
6
7
8
9
广度优先遍历算法示例
77
1visited[] 1 1 1 1 1
0 1 2 3 4 5 6 7 8
4 5 6queue
遍历结点6并将其入队
2
1
3
4
5
6
7
8
9
广度优先遍历算法示例
78
1visited[] 1 1 1 1 1
0 1 2 3 4 5 6 7 8
4 5 6queue
遍历结点6并将其入队
2
1
3
4
5
6
7
8
9
1visited[] 1 1 1 1 1 1
0 1 2 3 4 5 6 7 8
5 6 7queue
遍历结点7并将其入队
2
1
3
4
5
6
7
8
9
广度优先遍历算法示例
79
1visited[] 1 1 1 1 1 1 1
0 1 2 3 4 5 6 7 8
6 7 8queue
遍历结点8并将其入队
2
1
3
4
5
6
7
8
9
广度优先遍历算法示例
80
1visited[] 1 1 1 1 1 1 1
0 1 2 3 4 5 6 7 8
6 7 8queue
遍历结点8并将其入队
2
1
3
4
5
6
7
8
9
1visited[] 1 1 1 1 1 1 1
0 1 2 3 4 5 6 7 8
7 8queue
结点6的邻接点已遍历，只将6出队
2
1
3
4
5
6
7
8
9
广度优先遍历算法示例
81
1visited[] 1 1 1 1 1 1 1 1
0 1 2 3 4 5 6 7 8
8 9queue
遍历结点9并将其入队
2
1
3
4
5
6
7
8
9
广度优先遍历算法示例
82
1visited[] 1 1 1 1 1 1 1 1
0 1 2 3 4 5 6 7 8
8 9queue
遍历结点9并将其入队
2
1
3
4
5
6
7
8
9
1visited[] 1 1 1 1 1 1 1 1
0 1 2 3 4 5 6 7 8
queue
结点8和9的邻接点都以遍历，将其出队
2
1
3
4
5
6
7
8
9
图的应用
图的应用
•图可以应用于解决很多实际生活中的问题，例如，在交通网络中
，导航可以帮助我们选择一条从出发点到终点的最短路径。又例如
，在网络中传输数据时，路由算法可以找到一条从信源到信宿的最
短路径。上述的这些问题都归结为求最短路径问题。
83
网络中有效传输数据的问题
因特网中的路由选择
网络的作用是传输数据，数据从源端被传送到目的端往往要通过不止一个中间点，可能会有多条传输路径，采用何种机制传输数据以及如何选择最佳的传输路径，是网络通信中要解决的问题。
84
网络中数据包的传输
建立网络拓扑图，图中每一个顶点代表一台路由器，每条弧线代表路由器之
间的连接关系（链路），弧上的数字（即权值）表示链路的开销（如时
延）。
路由选择问题转换为图的最短路径问题。
85
图的最短路径问题
图的最短路径
•源点(Source)：路径的开始点
•终点(Destination)：路径的最后一个顶点
•路径的权值：路径经过的边的权值的和
•最短路径：自源点至终点的所有路径中权值最小的路径。
86
A
B
C
D
E
10
3
2
2
81 4 7 9
单源最短路径问题解法
1
87
单源最短路径问题：
已知有n个顶点的有向网络G=(V, E)，源点s，求s到其它节点的最短路径。
Dijkstra算法思想(Greedy)：
1. 维护一个结点集合U，源s到U中结点的最短路径已确定；(初始时，U为空集。)
2. 每次从V-U中挑选距离s最短的结点v加入到集合U中；
3. 更新v的邻结点和s的距离。
4. 若U=V，则结束；否则转2。
单源最短路径——Dijkstra算法示例
A
B
C
D
E
10
3
2
2
81 4 7 9
问题：求源点A到其它顶点的最短路径？
单源最短路径——Dijkstra算法
A
B
C
D
E
10
3
2
2
81 4 7 9
U = { } V-U = {A, B, C, D, E}
A B C D E
0 ∞ ∞ ∞ ∞
从源到顶点的距离
初始情况
A B C D E
0 -1 -1 -1 -1
从源到顶点路径的前趋
单源最短路径——Dijkstra算法
A
B
C
D
E
10
3
2
2
81 4 7 9
U = { } V-U = {A, B, C, D, E}
A B C D E
0 ∞ ∞ ∞ ∞
从源到顶点的距离
初始情况
A B C D E
0 -1 -1 -1 -1
从源到顶点路径的前趋
单源最短路径——Dijkstra算法
A
B
C
D
E
10
3
2
2
81 4 7 9
U = {A } V-U = {B, C, D, E}
A B C D E
0 10 3 ∞ ∞
从源到顶点的距离
第一轮计算后
A B C D E
0 A A -1 -1
从源到顶点路径的前趋
单源最短路径——Dijkstra算法
A
B
C
D
E
10
3
2
2
81 4 7 9
U = {A } V-U = {B, C, D, E}
A B C D E
0 10 3 ∞ ∞
从源到顶点的距离
第一轮计算后
A B C D E
0 A A -1 -1
从源到顶点路径的前趋
单源最短路径——Dijkstra算法
A
B
C
D
E
10
3
2
2
81 4 7 9
U = {A, C } V-U = {B, D, E}
A B C D E
0 7 3 11 5
从源到顶点的距离
第二轮计算后
A B C D E
0 C A C C
从源到顶点路径的前趋
单源最短路径——Dijkstra算法
A
B
C
D
E
10
3
2
2
81 4 7 9
U = {A, C } V-U = {B, D, E}
A B C D E
0 7 3 11 5
从源到顶点的距离
第二轮计算后
A B C D E
0 C A C C
从源到顶点路径的前趋
单源最短路径——Dijkstra算法
A
B
C
D
E
10
3
2
2
81 4 7 9
U = {A, C, E } V-U = {B, D}
A B C D E
0 7 3 11 5
从源到顶点的距离
第三轮计算后
A B C D E
0 C A C C
从源到顶点路径的前趋
单源最短路径——Dijkstra算法
A
B
C
D
E
10
3
2
2
81 4 7 9
U = {A, C, E } V-U = {B, D}
A B C D E
0 7 3 11 5
从源到顶点的距离
第三轮计算后
A B C D E
0 C A C C
从源到顶点路径的前趋
单源最短路径——Dijkstra算法
A
B
C
D
E
10
3
2
2
81 4 7 9
U = {A, C, E, B } V-U = {D}
A B C D E
0 7 3 9 5
从源到顶点的距离
第四轮计算后
A B C D E
0 C A B C
从源到顶点路径的前趋
单源最短路径——Dijkstra算法
A
B
C
D
E
10
3
2
2
81 4 7 9
U = {A, C, E, B } V-U = {D}
A B C D E
0 7 3 9 5
从源到顶点的距离
第四轮计算后
A B C D E
0 C A B C
从源到顶点路径的前趋
单源最短路径——Dijkstra算法
A
B
C
D
E
10
3
2
2
81 4 7 9
U = {A, C, E, B, D} V-U = { }
A B C D E
0 7 3 9 5
从源到顶点的距离
第五轮计算后
A B C D E
0 C A B C
从源到顶点路径的前趋
单源最短路径——Dijkstra算法
U = {A, C, E, B, D} V-U = { }
A B C D E
0 7 3 9 5
从源到顶点的距离
最短路径树
A B C D E
0 C A B C
从源到顶点路径的前趋
A
B
C
D
E
10
3
2
2
81 4 7 9
单源最短路径——Dijkstra算法
Dijkstra算法思想(Greedy)：
1. 维护一个结点集合U，源s到U中结点的最短路径已确定；
(初始时，U为空集。)
2. 每次从V-U中挑选距离s最短的结点v加入到集合U中；
3. 更新v的邻结点和s的距离：对于v的邻结点w，
如果Dist[w] > Dist[v] + AdjMatrix[v][w]，则
Dist[w] = Dist[v] + AdjMatrix[v][w],
其中， AdjMatrix[v][w]表示边<v,w>的权值。
4. 若U=V，则结束；否则转2。
101
单源最短路径——Dijkstra算法
Dijkstra算法思想(Greedy)：
1. 维护一个结点集合U，源s到U中结点的最短路径已确定；
(初始时，U为空集。)
2. 每次从V-U中挑选距离s最短的结点v加入到集合U中；
3. 更新v的邻结点和s的距离：对于v的邻结点w，
如果Dist[w] > Dist[v] + AdjMatrix[v][w]，则
Dist[w] = Dist[v] + AdjMatrix[v][w],
其中， AdjMatrix[v][w]表示边<v,w>的权值。
4. 若U=V，则结束；否则转2。
102
图-思考与练习
思考
•理解图及图结构；
•理解图的基本运算：深度搜索和广度搜索；
•理解并掌握求解单源最短路径的Dijkstra算法。
上机练习
•电子版(PDF)讲义4中的4-23,4-24,4-25,4-26,4-27,4-28
