计算机软件技术基础3-3 数据结构及算法(树与图)

常用数据结构及其运算第三章1§3.1概述§3.2线性表§3.3栈与队

§3.4树与二叉树§3.5图§3.6查找与排序目录23.4.1树的定义及其存储结构3.4.2二叉树及其性质3.4.3二叉树的遍历3.4.4二叉树的应用3.4.5小结3.4树与二叉树3非线性数据结构元素结点之间存在分支和层次关系。(一对多)应用：家谱 社会组织机构书的章节划分 操作系统中的多级目录结构 高级语言中源程序的语法结构等。

什么是树？3.4.1树的定义及其存储结构4树的定义(递归定义) 树是由n(n≥0)个结点组成的有限集合T：

有且仅有一个结点称为根结点(root)

其余结点分为m(m≥0)个各互不相交的有限集合 T1、T2、…、Tm，其中每一个集合Ti本身又是一棵树，称为根结点root的子树。

n=0时，为空树。ABDKEFLMJIHGCT1T2T3root3.4.1树的定义及其存储结构52.常用术语 1）结点：表示树中的元素。 2）度：结点拥有的子树数。如A的度为3，B 的度为2。树的度＝树中最大的结点度数。 3）叶子(终端结点)：度为0的结点。 4）孩子：结点的子树的根(后继结点)。每个结点 均是其前驱结点的孩子。 5）双亲：一个结点的前驱结点。ABDKEFLMJIHGCT1T2T3root12343.4.1树的定义及其存储结构66）子孙：以某结点为根的子树中的任一结点。7）祖先：从根到该结点所经分支上的所有结点。8）兄弟：同一双亲的孩子。9）结点的层次：根为第一层，根的直接后继结点为 第二层，以此类推。10）深度：树中结点的最大层次数。ABDKEFLMJIHGCT1T2T3root12343.4.1树的定义及其存储结构7 11）森林：是m(m≥0)棵互不相交的树的集合 12）有序树：树中结点在同层中按从左到右有序排 列、不能互换的称为有序树；反之称为无序树。例：ABDKEFLMJIHGCT1T2T3root1234ABCT1ACBT2有序树：T1!=T2无序树：T1=T23.4.1树的定义及其存储结构8例：用有序树表示算术表达式 (A+B)×5/(2×(C-D))/**+5AB2-CD3.4.1树的定义及其存储结构9结点的结构类型：1)异构型－根据结点的度数设置相应的指针域。

特点：节省空间、运算不便。2)同构型－每个结点的指针域个数均为树的度数。

特点：运算方便、浪费空间。·A···B·^^E^^^F^^^C^·^D^^^G^^

例(空链域问题)：一棵具有n个结点的k叉树，采用同构型存储结构，问有多少个空链域？解：总链域=nk；非空链域=n-1；

所以，空链域=n(k-1)+1。若树度为k,k=1为线性表，k=2时空链域最低，即二叉树。3.4.1树的定义及其存储结构3.树的存储结构(链式)103.4.2二叉树及其性质1.二叉树的定义及其存储结构

二叉树是n(n≥0)个结点的有限集合，它或为空 树(n=0)， 或由一个根结点和两棵分别称为左子树和右子树的互不 相交的二叉树构成。(递归定义。)即：度<=2的有序树 特点：每个结点至多有2个孩子，结点度数最大为2； 结点子树有左右之分。

存储结构：采用二叉链表存储。BADFEC

A^

B

^F^

^E^

D

^C^

Data

Lchild

Rchild结点结构：111.二叉树的定义及其存储结构

二叉树的五种形态

AABABABC思考：二叉树与二叉有序树的区别？二叉树可以是空的，而二次有序树至少有一个结点的度为2。3.4.2二叉树及其性质121265743121110983.4.2二叉树及其性质2.二叉树的基本性质（1）二叉树的第i层上至多有2i-1(i≥1)个结点。(可用归纳法证明)证明：当k=1时，命题显然成立。假定k=n-1时命题成立，则第n层（k=n）的结点数最多是第n-1层的2倍，所以第n层最多有2*2n-2=2n-1个结点。命题成立。（2）深度为h的二叉树中至多含有2h-1个结点(h>=1)。证明：根据性质1容易知道深度为h的二叉树最多有20+21+…+2h-1个结点，即最多有2h-1个结点。13（3）包含n(n>0)个结点的二叉树总的分支数为n-1证明：二叉树中除了根结点之外每个元素有且只有一个父结点。在所有子结点与父结点间有且只有一个分支，即除根外每个结点对应一个分支，因此二叉树总的分支数为n-1。3.4.2二叉树及其性质（4）任何一棵二叉树，若含有n0个叶子结点、n2个度为2的结点，则必存在关系式n0=n2+1证明：设二叉树含有n1个度为1的结点，则二叉树结点总数显然为：

n0+n1+n2 （2-2）再看看树的分支数，n2个度为2的结点必然有2n2个分支，n1个度为1的结点必然有n1个分支。又因为除根结点外，其余每个结点都有一个分支进入。因此二叉树的分支数加1就是结点总数。即结点总数为： 1+n1+2n2 （2-3）

由（2-2）（2-3）两式可知：n0=n2+114126574315141312111098满二叉树：深度为h且含有2h-1个结点的二叉树。结点编号是自上至下、自左至右。

特点：每一层上的结点都达到了最大值，即不存在度为1的结点，叶子结点均在最底一层

完全二叉树：一棵有n个结点的二叉树，按与满二叉树相同的编号方式对结点进行编号，若树中n个结点和满二叉树1～n编号完全一致。

性质：具有n个结点的完全二叉树的深度为：[Log2n]+1

证明：假设二叉树的深度为h，则必有2h-1-1<n≤2h-1，于是有2h-1<n+1≤2h，也就是2h-1≤n<2h，从而得到h-1≤log2(n)<h，于是h=[log2(n)]+1。1265743121110981265743121110983.4.2二叉树及其性质3.几种特殊形式的二叉树15平衡二叉树：又称AVL树，（Adelson-VerskiiandLandis,阿德尔逊-弗斯基-兰迪斯树），它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。 平衡因子＝(结点的)左子树深度－右子树深度) 平衡二叉树上所有结点的平衡因子只可能是-1、0、1。1254376非平衡二叉树1256437平衡二叉树3.4.2二叉树及其性质163.4.2二叉树及其性质（1）将一般树转换为二叉树4.森林与二叉树的转换②对每个结点，除了与它的第一个孩子保持联系外，去除与其它孩子的联系；EACBDIHGF

③以树根为轴心，将整棵树顺时针旋转45°。

①在兄弟结点之间加一连线；EACBDIHGFEACBDIHGF17（2）将森林转换为二叉树--把森林中第二棵树的根结点看成是第一棵树转化成的二叉树的左孩子的兄弟ACBDEFIHGJEFACBDIHGJACBDEFIHGJ3.4.2二叉树及其性质18（1）顺序存储结构--用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。5.二叉树的存储结构162345完全二叉树123456其顺序存储3.4.2二叉树及其性质19（1）顺序存储结构例：5.二叉树的存储结构123456712345ØØØØ67注意：对于一般二叉树，尤其是单支二叉树，采用顺序存储，按完全二叉树方式编号，虽能反映结点间的逻辑关系，但造成存储空间的浪费。3.4.2二叉树及其性质20（1）链式存储结构结点结构：5.二叉树的存储结构LchilddataRchildAEBGCDFA^B6^C6^D6^E6^F6^^G6^3.4.2二叉树及其性质213.4.3二叉树的遍历 ---遍历是指循某条搜索路线依次访问某数据构中的 全部结点，而且每个结点只被访问一次。1.遍历二叉树的定义

依次遍历根结点（D）、左子树（L）、右子树（R） 三部分。

按先左后右，有以下3种形式：

DLR：先序遍历（前序遍历）

LDR：中序遍历

LRD：后序遍历

说明：其中的序是针对根结点来说的。22（1）先序遍历：根->左->右二叉树为空，则空操作;访问根结点;先序遍历左子树;先序遍历右子树。1.遍历二叉树的定义PreOrder(t)

{

if(t!=NULL){

访问根结点；

PreOrder(lchild(t));

PreOrder(rchild(t));

}

}遍历算法3.4.3二叉树的遍历23（2）中序遍历：左->根->右二叉树为空，则空操作;中序遍历左子树;访问根结点;中序遍历右子树。1.遍历二叉树的定义InOrder(t)

{

if(t!=NULL){

InOrder(lchild(t));

访问根结点； InOrder(rchild(t));

}

}遍历算法3.4.3二叉树的遍历24（3）后序遍历：左->右->根二叉树为空，则空操作;后序遍历左子树;后序遍历右子树;访问根结点。1.遍历二叉树的定义PostOrder(t)

{

if(t!=NULL){

PostOrder(lchild(t));

PostOrder(rchild(t));

访问根结点；

}

}遍历算法3.4.3二叉树的遍历25例：ABABABCDABGDEFC先序：AB中序：BA后序：BAABABBAABCDACBDCDBAABDCEFGDBAECFGDBEGFCA3.4.3二叉树的遍历26例：已知先序序列为：ABFGCHDEIJLK，中序序列为：FGBHCDILJKEA，求此二叉树及后序序列。ABEFHDCGILKJ则后序序列为：GFHLKJIEDCBA3.4.3二叉树的遍历27例：已知中序序列为：DCBGEAHFIJK，后序序列为：DCEGBFHKJIA，求此二叉树及先序序列。则后序序列为：ABCDGEIHFJKABKCHJIDEFG3.4.3二叉树的遍历28如果给出一棵二叉树的先序遍历结果和中序遍历结果，或者给出后序遍历结果和中序遍历结果，我们就可画出该二叉树；如果只给此二叉树出先序遍历结果和后序遍历结果，就无法画出该二叉树。有两棵二叉树T1和T2，它们的先序和后序遍历结果完全相同。显然只凭先序和后序遍历结果无法确定到底是哪一棵二叉树。3.4.3二叉树的遍历29 求二叉树中的叶子数：

CountLeaf(t,count)

{

if(t!=NULL){

if(lchild(t)==NULL&&rchild(t)==NULL)

count++;

CountLeaf(lchild(t));

CountLeaf(rchild(t));

}2.遍历的应用3.4.3二叉树的遍历303.3.4二叉树的应用（1）定义：二叉排序树是一棵二叉树，满足下列条件：空树；左子树上的结点值<根结点的值；右子树上的结点值>=根结点的值；左、右子树也是二叉排序树。1031598921134218

在二叉排序树中，若按中序遍历就可以得到由小到大的有序序列。上图中序遍历得到： {2，3，4，8，9，9，10，13，15，18，21}1.二叉排序树311.二叉排序树 （2）二叉排序树的插入（生成）

在给定的二叉排序树中插入值为b的结点

若树为空，则作为根结点； 若树不空，则将b与根结点值r作比较：

b<r，插入左子树；

b>=r，插入右子树；

（注：新插入的结点一定是新添的叶子结点）3.3.4二叉树的应用321.二叉排序树

插入算法： InsertBet(t,b)

{

if(t==NULL){

GETNODE(t)；

t->data=b; t->lchild=NULL; t->rchild=NUILL;

}

elseif(b<t->data) InsertBet(t->lchild,b);

elseInsertBet(t->rchild,b);

} 3.3.4二叉树的应用33二叉排序树是一种动态表结构，即二叉排序树的生成过程是不断地向二叉排序树中插入新的结点。

1018371282310101810183101883101812831018128231018712823序列{10，18，3，8，12，2，7，3}构成一棵二叉排序树的过程。3.3.4二叉树的应用34 （3）二叉排序树的删除：删除结点P，使删除后的二 叉树仍是二叉排序树：DelNode(t,p,f)1.二叉排序树P为叶子结点P只有左或右子树直接删除将P的左子树或右子树直接成为其双亲结点的左右子树循着P的左子树的根C找其右子树分支，找到第一个无右子树的结点S，将S的左子树改为其双亲结点Q的右子树，用S取代P。YYNN3.3.4二叉树的应用35

DelNode(*t,*p,*f)

{

fag=0;

if(p->lchild==NULL)f=p->rchild;

elseif(p->rchild==NULL)f=p->lchild;

else{

q=p;s=p->lchild;

while(s->rchild!=NULL){q=s;s=s->rchild;}

if(q==p)q->lchild=s->lchild;

elseq->rchild=s->lchild;

p->data=s->data;free(s);fag=1;

}

if(fag==0){if(f==NULL)t=s;

elseif(f->lchild==p)f->lchild=s;

elsef->rchild=s;

free(p);

}

}删除算法：3.3.4二叉树的应用36FCLPRfPCQSQLSLpqsFCLPRfSCQQLpqSL例：1.二叉排序树3.3.4二叉树的应用37例：1.二叉排序树1018412231576删71018412231561018423156删1210154236删181015426删361524删103.3.4二叉树的应用382.哈夫曼树

----又称最优树，是一类带权路径长度最短的树。 (1)基本术语

路径：从树中一个结点到另一个结点之间 的分支构成两个结点之间的路径。

路径长度：路径上的分支数目。

树的路径长度：从树根到每一结点的路径长 度之和（PL）。3.3.4二叉树的应用39164532

PL=0+1×2+2×2+3=9例：436251

PL=0+1+2×2+3＋4=12推论：对n个结点的二叉树，满足：最小路径长度的树称为完全二叉树3.3.4二叉树的应用40

树的带权路径长度：树中叶子结点的带权路 径长度之和。

wk---叶子结点的权值，

lk---叶子结点到根结点的路径长度。结点的带权路径长度：从该结点到树根之间的路径长度与该结点上权值的乘积。3.3.4二叉树的应用41

(a)WPL=7*2+5*2+2*2+4*2=36 (b)WPL=7*3+5*3+2*1+4*2=46 (c)WPL=7*1+5*2+2*3+4*3=35(哈夫曼树)abcd7524dacb7542abcd7524例：(a)(b)(c)3.3.4二叉树的应用42哈夫曼树：WPL最小的二叉树称最优二叉树或哈 夫曼（huffman）树。注意：加权路径最小的二叉树并非完全二叉树。哈夫曼树中没有度为1的结点，因此一棵有n 个叶子结点的哈夫曼树共有2n-1个结点。3.3.4二叉树的应用433.3.4二叉树的应用

①由给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn}，每棵树只有一个权值为Wi的根结点；

②在F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和；

③将新二叉树加入F中，并去除原两棵树；

④重复②、③，直到F中只含一棵树，即huffman树（2）哈夫曼树的构造abcdab75c2d4b5c2d4ac2d4ab752475671118(a)(b)(c)(d)44（3）哈夫曼树的应用

最佳判定树 在解决某些判定问题时，利用哈夫曼树可以得到 最佳判定算法。例：一批数据结构，a<＝20为第一类，概率为2/20; 20<a<＝50为第二类，概率为3/20; 50<a<＝100为第三类，概率为4/20; 其余为第四类，概率为11/20;a≤20NY第一类a≤50NY第二类a≤100YN第三类第四类WPL=2/20+2×3/20+(4/20+11/20)×3 =53/20a>100NY第四类a>50NY第三类a>20YN第二类第一类WPL=11/20+2×4/20+(2/20+3/20)×3 =34/20Huffman树的判定过程是最佳的3.3.4二叉树的应用453.4.5小结

理解树的定义、术语及存储结构 掌握二叉树的概念和性质

熟悉满二叉树、完全二叉树和平衡二叉树的特点 会将一般树（森林）与二叉树进行相互转换 掌握二叉树的遍历算法 理解二叉排序树的概念并会构造，了解插入 和删除算法 掌握哈夫曼树 了解最佳判定算法463.5.1图的定义及基本术语3.5.2图的存储结构3.5.3图的遍历3.4.4图的应用3.4.5小结3.5图47 图比树更复杂、更一般，树是一种简单的图。 图的应用---范围非常广，如语言学、逻辑学、数 学、物理、化学、计算机科学以及各种工程学科 领域。 在图中，结点之间的关系可以是任意的多对多的关 系。3.5图481.图的定义 1）图：由顶点集合V和顶点之间关系集合R组成。 G=(V,R)， 其中V={v1,v2,…,vn}，是顶点的非空有限集合； R＝{<vi,vj>},是顶点的有序对，

或{(vi,vj)},是顶点的无序对。 2）无向图：当图中顶点间的关系为无序对。 (vi,vj)=(vj,vi)，称为边E。

无向图记作：G=(V,E)，35241无向图3.5.1图的定义及基本术语例如上图：G1=(V,E)，

V(G1)={1，2，3，4，5}

E(G1)={(1,2),(1,3),(1,4),(2,3),(3,5)}49vivj弧头弧尾 3）有向图：图中顶点间的关系为有序对 <vi,vj>称为弧A， 注意：<vi,vj>≠<vj,vi>，

有向图记作：G=(V,A)，例如右图： G2=(V,A)，V(G2)={1,2,3,4,5,6}

A(G2)={<1,2>,<2,1>,<2,4>,<2,3>,<3,5>,<5,6>,<6,3>}有向图3241563.5.1图的定义及基本术语503426751192718331410511216无向网3426751706469584430804375180313260有向网 4）网：若图中每一条边附有反映该边特征的数据，则 称为网，与边相关的数据称为权。 边上带权的无向图称为无向网。 弧上带权的有向图称为有向网。3.5.1图的定义及基本术语512.图的基本术语 1）子图：两个图G和G′，G=(V,E),G’=(V’,E’)

若， 则称G′为G的子图。 例：3241G3G3的子图：321132413.5.1图的定义及基本术语522）度、入度和出度： 度：无向图中，与某个顶点相连的边的数目。

入度：有向图中，以某个顶点为头的弧的数目。 出度：以某个顶点为尾的弧的数目。35241无向图3241有向图3.5.1图的定义及基本术语例：有N个顶点的有向图中，每个顶点的度最大可达多少？

2(N－1)533）路径和回路：

路径：在无向图中，从顶点vp到vq的路径---- 是顶点序列(vp,vi1,vi2,…,vik,vq)，且(vp,vi1)， (vi1,vi2)，…，(vik,vp)均是E中的边。

有向路径：在有向图中，由顶点的弧组成。

路径长度：路径上边或弧的数目。 网的路径长度---路径上权值的和。

简单路径：除第一个和最后一个顶点外，序列中其余 顶点各不相同的路径。

简单回路：第一个顶点和最后一个顶点相同的简单路径。3.5.1图的定义及基本术语543.5.1图的定义及基本术语4）连通图和连通分量：(对于无向图定义) 在无向图G中:

连通：若从顶点vi到vj存在路径，则称vi和vj是连通的。35421连通图(a)6776541非连通图(b)11855555G1G2G3注意：连通图只有一个连通分量，即本身。 非连通图有多个连通分量连通图：顶点集合V中任意两个顶点vi和vj都连通， 则称G为连通图。连通分量：G中的极大连通子图称为该图的连通分量。 如上图，(a)为连通图，(b)不是连通图，但它有3个 连通分量：G1、G2、G3555）强连通图和强连通分量：(对于有向图定义) 在有向图G中:

连通：从顶点vi到vj有路径，则称从vi到vj是连通的。

强连通图：任意两个顶点vi和vj都连通， 则称G为强连通图。 强连通分量：G中的极大强连通子图称为该图的 强连通分量。

3.5.1图的定义及基本术语561.邻接矩阵（表示顶点之间的关系） 有n个顶点的图G=(V,E)，可用n×n的矩阵来表示，矩阵元素为：若(vi,vj)或<vi,vj>是E中的边或弧反之3.5.2图的存储结构若G是网，则邻接矩阵中每个元素定义为：若(vi,vj)或<vi,vj>是E中的边或弧反之57 无向图和无向网的邻接矩阵为对称矩阵。例：3241有向图↓0110

0000

0001

100035241无向图↓01110

10100

11001

10000

001000270019210

270560110

05010000

061000140

1900003318

21110143300

00001800342675119271833141011216网↓53426751706469584430804375180313260有向网↓080006400

000310600

03000000

032440000

70000018058

750043000

00006900582.邻接表

邻接表是图的一种链式存储结构,在邻接表中,对图中每个顶点建立一个单链表，并将它们的表头指针用向量存储（邻接向量）。 第i个单链表中的结点依附于顶点vi的边(有向图为弧)，故其结点数等于vi的度(有向图为出度)。3.5.2图的存储结构59

链结点结构：adjvex：邻接域,存储邻接顶点 的序号；data：数据域，存储和边或弧的 权值信息；nextarc：链域指示下一条边或弧 的结点adjvexnextarcdata表结点vexdatafirarc头结点vexdata：数据域,存储vi 信息；firarc：链域，指向表中 第一个结点。3.5.2图的存储结构601034267511927183314112165342675170646958443080437518031326032413524112345672271272526119121518^51935410^310633211621^46614^718^414611^533^1234567280431230^232170175569^564^660^344^6180443^758^12^3424^1^3^123452121^3^33^14^5^61注意：

表头结点有序，以向量存储(邻接向量)； 无向图的邻接矩阵唯一，但其邻接表不唯一（次序与邻接表建立时输入次序有关）；

对于无向图，n个顶点，e条边，有n个表头结点，2e个表结点，空间复杂度为O(n+e)； n个顶点的无向图至多n(n-1)/2条边（完全图）。3.5.2图的存储结构62 从图的某一顶点出发，沿某条路径，依次对其余顶点进行访问，为了避免重复访问，设一个辅助数组visited[n]：3.5.3图的遍历初值，未访问已访问631.深度优先搜索(DFS)：树的前序遍历推广 1）基本思想：从图的某一个顶点v0出发进行遍历，首先访问起始点v0，然后选择v0的一个尚未访问过的邻接点w，从w出发继续深度优先搜索，即访问w之后选择w的一个尚未访问过的邻接点作为出发点继续作深度优先搜索，直到被访问的顶点其邻接点均被访问过为止，这时需要回溯到该顶点访问前的顶点，继续访问其尚未访问的邻接点。这样不断回溯，直到回溯到起始点v0，使所有和v0有路径相通的顶点都被访问到为止。3.5.3图的遍历642）算法描述：以邻接矩阵作为图的存储结构

DFS(A,n,v)

{

visit(v); //访问顶点v

visited[v]=TRUE;//置已访问标志

for(j=0;j<n;j++)

if(A[v][j]==1&&!visited[j])

DFS(A,n,j);

}3.5.3图的遍历6531856942735241(a) (b)图(a)：v1,v2,v3,v5,v4 v3,v1,v2,v4,v5

v2,v1,v3,v5,v4 v4,v1,v2,v3,v5图(b)：v1,v2,v3,v6,v5,v7,v8,v4,v9

v9,v4,v1,v2,v3,v6,v5,v7,v8

v3,v1,v2,v4,v9,v6,v5,v7,v8例：662.广度优先搜索(BFS)(类似于树的层次遍历) 1）基本思想：访问了起始点v0之后，首先依次访问v0的各个邻接点，然后再依次访问这些顶点中未被访问过的邻接点，以此类推，直到所有被访问到的顶点的邻接点都被访问过为止。 2）算法描述：为了搜索需要，应设置一个循环队列，存放已被访问过的顶点。3.5.3图的遍历67

BFS(AdjList,n,v)//以邻接表作为图的存储结构

{

访问顶点v;visited[v]=TRUE;

front=n-1;rear=0;CQ[rear]=v;

while(rear！=front){front=(front+1)%n;v=CQ[front];

p=AdjList[v].firarc;

while(p！=NULL){if(!visited[p->adjvex]){访问p->adjvex;visited[p->adjvex]=TRUE;

rear=(rear+1)%n;CQ[rear]=p->adjvex;

}/*endif*/

p=p->nextarc;

}/*endwhile(p!=NULL)*/

}/*endwhile(rear!=front)*/

}3.5.3图的遍历68

例：图(a)：v2,v1,v5,v3,v4,v6

v1,v2,v3,v4,v5,v6图(b)：v1,v2,v3,v4,v6,v9,v5,v7,v8

v9,v4,v1,v2,v3,v6,v5,v7,v8318569427(a) (b)1364523.5.3图的遍历69

例：DFS：v1,

v2,v3,v6,v9,v5,v8,v4,v7BFS：v1,v2,v4,v5,v3,v7,v6,v8,v91364527893.5.3图的遍历703.复杂度分析空间复杂度：O(n)时间复杂度： 邻接表：O(e),e为边数 邻接矩阵：O(n2)3.5.3图的遍历71

1.单源最短路径

1）问题的提出

背景：从一个给定的城市出发，能否到达其它各城市？走哪条路花费最少？

数据结构：用有向网表示，顶点表示城市，弧代表路段，弧上的权值代表两城市间的距离或运输所需的代价。我们称出发点为源点，其它点为终点。则问题可描述为：从有向网的源点到其它各终点有否路径？最短路径是什么？最短路径的长度是多少？

3.5.4图的应用72

路径的三种情况：

①没有路径；

②只有一条路径，即为最短路径；

③有多条路经，存在最短的。12534620101515350203530501045设顶点v2为源点，则：v2到v6：没有路径v2到v1：只有一条，长度35v2到v4：有三条，最短为303.5.4图的应用73

定义：

给定有向图网G=(V,A)和源点v0,求从v0到G中其余各顶点的最短路径。125346741412982524510186例：以v6为源点，则各最短路径为：v6->v1:21(v6->v2->v3->v1)v6->v2:5v6->v3:12(v6->v2->v3)v6->v4:25(v6->v4)v6->v5:无路径3.5.4图的应用743.5.4图的应用2）算法思想：先找出从源点v0到各终点vk的直达路径<v0,vk>，从这些路径中找出一条长度最短的路径<v0,u>，然后对其余各条路径进行适当调整：若在图中存在弧<u,vk>，且<u,vk>和<v0,u>两条弧上权之和小于弧<v0,vk>的权，则以路径<v0,u,vk>代替<v0,vk>。在调整后的各条路径中，再找长度最短的路径，以此类推。3）过程： ①初始化 设AS[n][n]为有向网的带权邻接矩阵，AS[i][j]表示弧<vi,vj>上的权值，若<vi,vj>不存在，则AS[i][j]为∞06∞8∞∞1807∞∞109∞015∞∞∞∞120∞∞∞∞4∞0∞245∞25∞01234561

2345612534674141298252451018675

S:最短路径的终点集合(初值为{v0}) DIST[n]:各终点当前找到的最短路径的长度 (初始值为DIST[i]=AS[v0][i])②选择u，使得：3.5.4图的应用76③对于所有不在S中的终点w，若：④重复操作②、③共n-1次，可求得从v0到各终点的 最短路径。几个量的说明：

S[n]：记录了从源点出发的最短路径的终点集合。

DIST[n]：记录各终点当前找到的最短路径的长度。

PATH[n]：PATH[i]表示从源点到顶点vi之间的最短路径的前驱顶点，初始值为源点v0,若不存在，则为空。3.5.4图的应用773.5.4图的应用例：245∞25∞0

DIST[1:6]123456

S

{6}

{6,2}

{6,2,3}

{6,2,3,1}

{6,2,3,1,4}6666

PATH[1:6]123456262663626636266362662351225∞02151225∞

02151225∞

02151225∞

006∞8∞∞1807∞∞109∞015∞∞∞∞120∞∞∞∞4∞0∞

245∞25∞01234561

23456125346741412982524510186则输出PATH和Distant:6->1:6->2->3->121;6->2:6->25;6->3:6->2->312;6->4:6->425;6->5:无路径; 6->6:6->60;782.拓扑排序(AOV网，顶点表示活动的有向网)1）问题的描述：

用有向图描述工程的进行过程，子工程称为活动，在图中用顶点表示，两顶点间的弧表示活动间的优先关系，这种有向图称为作业活动网或AOV网。 顶点i到顶点j有路径，称i是j的前驱，j是i的后继；若从i到j只有一条弧，则称i是j的直接前驱，j是i的直接后继。3.5.4图的应用79引例：一个软件专业学生学习课程C1：程序设计 先修无C2：离散数学 C1C3：数据结构 C1C2C4：汇编语言 C1C5：语言设计与分析C3C4C1C2C4C5C33.5.4图的应用80拓扑有序序列及拓扑排序

死锁---在AOV网中不允许存在有向回路，否则某项活动的开工将以自己工作的完成作为先决条件，这种现象称为死锁。 拓扑有序序列---若有向图中没有回路出现，则可构造得到包含有向图中全部顶点的序列，这种序列称为拓扑有序序列。 拓扑排序---对AOV网构造拓扑有序序列的操作称为拓扑排序。3.5.4图的应用813.5.4图的应用2）拓扑排序方法： ①在有向图中选取一个没有前驱的顶点(入度为0) 输出； ②在图中删除该顶点和以它为尾的所有弧。 ③Repeat①,②,直到全部顶点输出。(答案不唯一)12543输出v62543输出v1253输出v425输出v3拓扑有序序列为：v6v1v4v3v2v5125643初态5输出v2输出v582例：12465314523可能的拓扑：

6->1->4->3->2->5 1->3->2->6->4->5可能的拓扑：

1->2->3->4->5 1->4->2->3->5 1->2->4->3->53.5.4图的应用833）拓扑排序的邻接表和链栈：邻接表：

4^202^123^0指针入度顶点325^5^45^125643AOV网链栈：所有入度为零的顶点构成一链栈 3.5.4图的应用84操作：①建立一个入度为0的顶点的栈； ②选取一个入度为0的顶点输出； ③弧头顶点的入度减1； ④Repeat①～③，直到全部顶点输出3.5.4图的应用85051234例：5^1

1

3^4^5^V0V1V2V3V4V50202123^^020212初态010112000111000011000001000000012345下标v2出栈v0出栈v1出栈v3出栈v4出栈拓扑排序序列为：

2、0、1、3、4、5改用队列，则输出的拓扑序列0,2,1,3,4,5v0/v0v2//v1//v3//v4//v0、v2入栈v5//v2出栈v0出栈v1出栈V3入栈V3出栈V4入栈V4出栈V5入栈V5出栈栈的变化：v1入栈863.关键路径(以边表示活动的网：AOE)1）问题描述

AOE网：一个带权的有向无环图。

顶点vi：表示事件

弧ai：表示活动 权：表示活动的持续时间。

源点：一个入度为零的点(工程起点，只有一个)

汇点：一个出度为零的点(工程结束，只有一个)

研究的问题 ①完成整个工程需要多少时间？ ②哪些活动是影响工程进度的关键？3.5.4图的应用87关键路径：完成工程的最短时间是从源点到汇点的最长路径长度，这条最长的路径称作关键路径。事件vj最早发生时间ve(j)：从ve(1)=0开始向前递推活动ai由弧<i,j>表示，其持续时间记为dut(<i,j>),T是所有以j为头的弧的集合vjviai3.5.4图的应用88事件vj最迟发生时间vl(j)：从vl(n)=ve(n)

开始向后递推其中S是所有以j为尾的弧的集合vkvj注意：以上两个递推公式的计算必须在拓扑有序和逆拓扑有序的前提下进行，即：ve(j)必须在vj的所有前驱的最早发生时间求得之后才能确定，而vl(j)必须在vj的所有后继的最迟发生时间之后才能确定。3.5.4图的应用89活动最早开始时间e(i)：

e(i)=ve(j)vjai活动