6.1 树树形结构是一类重要的非线性结构，树形结构是结点之间有分支、分层关系的结构。
树的定义,树是 n(n≥0)个结点的有限集。
它满足以下两个条件,
（ 1）有且仅有一个特定的称为根的结点。
（ 2）其余的结点可分为 m个互不相交的有限集合 T1,
T2,…,T m,其中，每个集合又都是一棵树（子树）。
树的表示
6.1 树结点的度,一个结点的子树个数称为该结点的度。
树的度,一棵树中结点度的最大值。
叶子（终端结点）,度为 0的结点。
分支结点（非终端结点）,度不为 0的结点。
内部结点,除根结点之外的分支结点。
孩子,树中某个结点的子树的根称为个结点的孩子。
双亲,该结点则为孩子的双亲。
兄弟,同一个双亲的孩子。
路径,若树中存在一个结点序列 k1,k2,…,kj，使得 ki是 ki+1的双亲
(1≤i<j),称该结点序列是从 k1到 kj的一条路径。
祖先,若树中结点 k到 ks存在一条路径，则称 k是 ks的祖先。
子孙,ks是 k的子孙。
6.1 树层次,结点的层次是从根开始算起 (根为 1层 )。
高度,树中结点的最大层次称为树的高度或深度。
有序树,若将树中每个结点的各子树看成是从左到右有秩序的。
无序树,否则称为无序树。
森林,是 m(m≥0)棵互不相交的树的集合。
(树形结构的逻辑特征可用树中结点之间的父子关系来描述 )
6.1 树树的基本操作有下列几种：
（ 1）初始化操作。
（ 2）求根函数。
（ 3）求双亲函数。
（ 4）求孩子结点函数。
（ 5）求右兄弟函数。
（ 6）建树函数。
（ 7）插入子树操作。
（ 8）删除子树操作。
（ 9）遍历操作。
（ 10）清除结构操作。
6.2 二叉树
概念
性质
存储结构
遍历
线索化
6.2 二叉树
概念定义：二叉树是个结点的有限集，它或者是空集，
或者由一个根结点及两棵不相交的分别称作这个根的左子树和右子树的二叉树组成。
二叉树的五种基本形态
6.2 二叉树
二叉树的性质
1、二叉树第 i层上的结点数目最多为 2i-1(i≥0) 。
归纳法证明：
归纳基础,i=1时，有 2i-1=20=1。
归纳假设：假设对所有的 j(1≤j<i) 命题成立，即第 j层上至多有 2j-1个结点，证明 j=i时命题成立。
归纳步骤：根据归纳假设，第 i-1层上至多有 2i-2个结点，由于二叉树的每个结点至多有两个孩子，故第 i层上的结点至多是第 i层上的最大结点数的 2倍，即 j=i时该层上至多有 2*2i-2=2i-1个结点，故命题成立。
6.2 二叉树
2、深度为 k的二叉树至多有 2k-1个结点。
证明：在具有相同深度的二叉树中，仅当每一层都含有最多结点时，
其树中结点数最多。因此，利用性质 1可得，深度为的二叉树中至多含有的结点数为：
20+21+… +2k-1=2k-1
故命题正确。
3、在任意一棵二叉树中，若终端结点的个数为 n0，度为 2
的结点数为 n2，则 n0=n2+1。
证明：因为二叉树中所有结点的度数均不大于 2，所以结点总数应等于 0度结点数,1度结点数和 2度结点数之和，即：
n=n0+n1+n2 ①
6.2 二叉树另一方面,1度结点有一个孩子,2度结点有两个孩子。所以，
二叉树中孩子结点总数是 n1+2n2，二叉树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可以表示为：
n=n1+2n2+1 ②
由式①和式②得到,n0=n2+1
两种特殊形式的二叉树：
满二叉树,一棵深度为 k且有 2k-1个结点的二叉树。
完全二叉树,若一棵二叉树至多只有最下面两层上结点的度数可以小于 2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。
6.2 二叉树
4、具有 n个结点的完全二叉树的深度为 log2n +1
证明：设所有完全二叉树的深度为 k，由完全二叉树的定义可知，它的前 k-1层是深度为 k-1的满二叉树，一共有 2k-1-1个结点。由于完全二叉树深度为 k，故第 k层上还有若干个结点，因此，
该完全二叉树的结点个数 n>2k-1-1。
另一方面，由性质 2可知 n≤2 k-1，即：
2k-1-1< n ≤2 k-1
由此可推出,2k-1 ≤ n < 2 k-1
取对数后有,k-1 ≤ log 2n < k
因为 k为整数，故有 k-1= log2n,由此可得：
k= log2n +1
6.2 二叉树
5、如果对一棵有 n个结点的完全二叉树，则对任一结点有：
（ 1）若 i=1，则 ki是根结点，无双亲；若 i>1,则 ki的双亲编号为 int(i/2)。
（ 2）若 2i≤n,则 ki的左孩子的编号是 2i； 2i>n,则无左孩子。
（ 3）若 2i+1≤n,则 ki右孩子的编号是 2i+1;2i+1>n,则无右孩子。
（ 4）若 i为奇数且不为 1，则 ki的左兄弟的编号是 i-1；否则 ki无左兄弟。
（ 5）若 i为偶数且小于 n，则 ki的右兄弟的编号是 i+1；否则 ki无右兄弟。
6.2 二叉树
二叉树的存储结构
1）顺序存储结构,对完全二叉树而言，既简单又节省存储空间，但对非完全二叉树，必须按完全二叉树的形式来存储树中的结点，这将造成存储空间的浪费。
A
0 B
0 0 0 C
1 2 3 4 5 6 7
A 0 B 0 0 0 C
6.2 二叉树
2）链式存储结构设计不同的结点结构可构成不同的链式存储结构。通常采用二叉链表的形式，即：
lchild data rchild
typedef struct BiTNode
{ TElemType data;
struct BiTNode *lchild,*rchild;
} *BiTree;
6.2 二叉树
二叉链表的生成
Status CreateBiTree(BiTree &T)
{ scanf(&ch);
if (ch==‘’) T=NULL;
else
{ if (!(T=(BiTNode *) malloc (sizeof(BiTNode)))) exit(OVERFLOW);
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}
6.2 二叉树
A
B C
D E F
T
A
B ∧ C
∧ D ∧ ∧ E ∧ ∧ F ∧
6.2 二叉树
二叉树的遍历遍历,是指沿某条搜索路径周游二叉树，对树中每个结点访问一次且仅访问一次。
前序遍历（ DLR）,访问根的操作是在遍历其左、右
(先根 ) 子树之前进行的。
中序遍历 （ LDR）,访问根的操作是在遍历其左、右
(中根 ) 子树之中进行的。
后序遍历（ LRD）,访问根的操作是在遍历其左、右
(后根 ) 子树之后进行的。
6.2 二叉树
A
B C
D E F
前序遍历序列,ABDCEF
中序遍历序列,DBAECF
后序遍历序列,DBEFCA
6.2 二叉树前序遍历递归算法：
Status PreOrder(BiTree T)
{ if (T) { Visit(T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
6.2 二叉树中序遍历递归算法：
Status InOrder(BiTree T)
① { if (T) {
② InOrder(T->lchild);
③ Visit(T->data);
④ InOrder(T->rchild);
}
⑤ }
6.2 二叉树后序遍历递归算法：
Status PostOrder(BiTree T)
{ if (T) { PostOrder(T->lchild);
PostOrder(T->rchild);
Visit(T->data);
}
}
6.2 二叉树
InOrder(&A) InOrder(&B) InOrder(&D) InOrder(NULL)
① ① ① ①
② ②
② ③ (访问 B) ③ ⑤
(访问 D)
③ (访问 A) ④ InOrder(NULL)
⑤ ①
④ ④ InOrder(NULL)
… ⑤ ① ⑤
⑤ ⑤
#
( 中序遍历序列,DBAECF )
6.2 二叉树
中序遍历二叉树的非递归算法：
Status InOrder1(BiTree T,status (* visit)(TelemType e))
{ Initstack(S); Push(S,T);
while (! StackEmpty(S))
{ while (GetTop(S,p) && p) Push(S,p->lchild);
Pop(S,p);
if (! StackEmpty(S))
{ Pop(S,p); if (! Visit(p->data)) return ERROR;
Push(S,p->rchild);
}
}
}
6.2 二叉树
,遍历”是二叉树各种操作的基础。
由上讨论得知：
遍历二叉树是以一定规则将二叉树中的结点排列成一个线性序列，得到二叉树中结点的先序序列或中序序列或后序序列。
这实质上是对一个非线性结构进行线性化。
练习题
已知某二叉树的前序遍历序列为 ABDEGCFHIJ，
中序遍历序列为,DBGEAHFIJC，请写出该二叉树的后序遍历序列？
求某二叉树的叶子数。
参考答案：
A
B C
D E F
G H I
J
后序遍历序列,
DGEBHJIFCA
参考答案：
Status countleaf(BiTree T,int &count)
{ if (T) { if (T->lchild==NULL && T->rchild==NULL)
count++;
countleaf(T->lchild,count);
countleaf(T->rchild,count);
}
}
6.2 二叉树结点的结构,lchild ltag data rtag rchild
其中,ltag= 0 指示结点的左孩子
1 指示结点的前驱
rtag= 0 指示结点的右孩子
1 指示结点的后继
线索链表：以上述结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表。
线索：其中指向结点的前驱和后继的指针，叫做线索。
线索二叉树：加上线索的二叉树称之为线索二叉树。
线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。
6.2 二叉树中序线索二叉树,
A
NULL
NULL B E
C D F
G
H r I
6.2 二叉树
中序遍历建立线索化链表的算法
Status InOrderThreading(BiThrTree &Thrt,BiThrTree T)
{ if (! (Thrt=(BiThrTree) malloc (sizeof(BiThrNode))))
exit(OVERFLOW);
Thrt->Ltag=Link; Thrt->Rtag=Thread;
Thrt->rchild=Thrt;
if (! T) Thrt->lchild=Thrt;
else { Thrt->lchild=T; pre=Thrt;
InThreading(T);
pre=->rchild=Thrt; pre->Rtag=Thread;
Thrt->rchild=pre;
} return OK;
}
6.2 二叉树
Status InThreading(BiThrTree p)
{ if (p) { InThreading(p->lchild);
if (! P->lchild) { p->Ltag=Thread;
p->lchild=pre; }
if (! Pre->rchild) { pre->Rtag=Thread;
pre->rchild=p; }
pre=p;
InThreading(p->rchild);
}
}
6.2 二叉树
线索二叉树的三种常用运算,
查找某结点 P在指定次序下的前驱和后继遍历线索二叉树线索二叉树的插入
6.2 二叉树
查找某结点 P在指定次序下的后继
Statust inordernext(BiThrptr p)
{ if (p->Rtag==1) return (p->rchild);
else { q=p->rchild;
while (q->Ltag==0) q=q->lchild;
return (q);
}
}
6.2 二叉树
查找某结点 P在指定次序下的前驱
Statust inorderpre(BiThrptr p)
{ if (p->Ltag==1) return (p->lchild);
else { q=p->lchild;
while (q->Rtag==0) q=q->rchild;
return (q);
}
}
练习题
画出下列二叉树的前序、中序和后序线索二叉树。
A
B C
D E F
G H
6.3 树和森林
树的存储结构
树和森林与二叉树的转换
树和森林的遍历
6.3 树和森林
树的存储结构双亲表示法孩子表示法孩子兄弟表示法
6.3 树和森林
树和森林与二叉树的转换
A A
B
B C D E C
F G D
E F G H I J H
I
J
6.3 树和森林
A
A E G B E
B C D F H I C F G
D H
I
6.3 树和森林
树和森林的遍历树的先序遍历,先访问树的根结点，然后依次先序遍历根的每棵子树。
树的后序遍历,先依次后序遍历每棵子树，然后访问根结点。
（参见,P137—图 6.16）
注,先序遍历一棵树恰好等价于先序遍历该树对应的二叉树 ;
后序遍历一棵树恰好等价于中序遍历该树对应的二叉树 ;
6.3 树和森林
树和森林的遍历森林的先序遍历,
(1) 先访问森林中第一棵树的根结点 ;
(2) 先序号遍礼第一棵树中根结点的子树森林 ;
(3) 先序遍历除去第一棵树之后剩余的树构成的森林。
森林的中序遍历：
(1) 中序遍历森林中第一棵树的根结点的子树森林 ;
(2) 访问第一棵树的根结点 ;
(3) 中序遍历除去第一棵树之后剩余的树构成的森林。
（参见,P138—图 6.17）
6.4 哈夫曼树及应用
概念路径,从树中一个结点到另一个结点之间的分支构成了这两个结点之间的路径。
路径长度,路径上的分支数目称做路径长度。
树的路径长度,从树根到树中每一结点的路径长度之和。
结点的带权路径长度,从该结点到树根之间的路径长度与结点上权的乘积。
树的带权路径长度,树中所有叶子结点的带权路径长度之和
（ WPL）。
（参见,P144—图 622）
6.4 哈夫曼树及应用
最优二叉树 (哈夫曼树 )
带权路径长度 WPL最小的二叉树，称之为最优二叉树。
（如何构造最优二叉树？）
哈夫曼算法：
（ 1） 根据给定的 n个权值 { w1,w2,…,wn }构成 n棵二叉树的集合
F={T1,T2,…,Tn}，其中每棵二叉树 Ti中只有一个带权为 wi的根结点，
其左右子树均为空。
（ 2） 在 F中选取每棵根结点的权值最小的树作为左右子树构造新的二叉树，
且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
（ 3） 在 F中删除这两棵树，同时将新得到的二叉树加入 F中。
（ 4） 重复（ 2）和（ 3），直到 F含一棵树为止。
(参见,P146—图 624)
6.4 哈夫曼树及应用
哈夫曼编码前缀编码,任意一个字符的编码都不是另一个字符的编码的前缀。
0 1 a的编码,0
a b的编码,10
0 1 c的编码,110
b d的编码,111
0 1
c d
上机题：
以（ P148-例 6-2）为例，根据算法 6.12设计哈夫曼编码。
第 7章 图 （ 6学时）
图的概念
图的存储结构 (邻接矩阵、邻接链表等 )
图的遍历 (DFS和 BFS)
生成树和最小生成树 (Prim算法和 Kruskal算法 )
拓扑排序
关键路径
最短路径 (Dijkstra算法和 Floyd算法 )
7.1 图的概念图是一种复杂的非线性结构
图,由顶点集 V和边集 E组成，记为：
G=（ V,E）
例：
A A A 3 B
5 8 4 9 E
B B C 6 9
C 2 D
C D
(G1) (G2) (G3)
7.1 图的概念
有向图,若图 G中的每条边都是有方向的，则称 G为有向图。
例：图 G1 V(G1)={A,B,C}
E(G1)={<A,B>,<B,A>,<B,C >}
无向图,若图 G中的每条边都没有方向的，则称 G为无向图。
例：图 G2 V(G2)={A,B,C,D}
E(G2)={(A,B),(A,C),(A,D),(B,C),(B,D),(C,D)}
网络,若将图的每条边都赋上一个具有某种有意义的数（权），
则称这种带权的图为网络。
例：图 G3
有向完全图,若有向图 G的顶点数 n和边数 e恰有 e=n(n-1)条边。
无向完全图,若有向图 G的顶点数和边数恰有 e=n(n-1)/2条边。
7.1 图的概念
关联,若 (vi,vj)是一条无向边，则称顶点 vi和 vj互为邻接点，或称
vi和 vj相邻接；并称边 (vi,vj)关联于顶点 vi和 vj，或称边
(vi,vj)与顶点 vi和 vj相关联。
子图,设 G=（ V,E）是一个图，若 V’是 V的子集,E’是 E的子集，
且 E’中的边所关联的顶点均在 V’中，则 G’=（ V’,E’）也是一个图，则称其为 G的子图。
例：
A A
A B C
B C
D
7.1 图的概念
度,无向图中顶点 V的度是关联于该顶点的边的数目，记为 D(V)。
若 G为有向图，则以顶点 V为终点的边的数目称为 V的入度，
记为 ID(V)；把以顶点 V为始点的边的数目称为 V的出度，记为 OD(V)；那么顶点 V的度则定义为该顶点的入度与出度之和。
结论：无论是有向图还是无向图，顶点数 n、边数 e和度数之间有如下关系：
E= (∑D(vi))/2 i,1～ n
例：图 G1：
e=(D(A)+D(B)+D(C))/2=((1+1)+(1+2)+(1))/2=3
图 G2：
e=(D(A)+D(B)+D(C)+D(D))/2=12/2=6
7.1 图的概念
路径,在图 G中，若存在一个顶点序列 vp,vi1,vi2,…,v q，使得
(vp,vi1),(vi1,vi2),…,(v in,vq)均属于 E(G)，则称到顶点 vp到 vq
存在一条路径。
路径长度,该路径上边的数目。
简单路径,若一条路径上除 vp和 vq可以相同外，其余顶点均不相同，则称此路径为一条简单路径。
简单回路,起点和终点相同的简单路径。
7.1 图的概念
连通,在无向图 G中，若从顶点 vi到 vj有路径，则称 vi和 vj是连通的。
连通图,若 V(G)中任意两个不同的顶点 vi和 vj都连通，则称 G为连通图。
连通分量,无向图 G的极大连通子图称为 G的连通分量。
（参见,P159—图 7.3）
强连通图,在有向图中，若对于 V(G)中任意两个不同的顶点 vi和 vj
都存在从 vi到 vj以及 vj到 vi的路径，则称 G是强连通图。
强连通分量,有向图 G的极大连通子图称为 G的强连通分量。
（参见,P159—图 7.4）
7.2 图的存储结构图的常用存储表示方法有：邻接矩阵（数组）、邻接表、邻接多重表和十字链表等。
邻接矩阵表示法邻接矩阵,是表示顶点之间相邻关系的矩阵。
设 G=（ V,E）是具有 n个顶点的图，则 G的邻接矩阵是具有如下性质的 n阶方阵。
A[i][j]= 1 若 (vi,vj)或 < vi,vj >是 E(G)中的边
0 若 (vi,vj )或 < vi,vj >不是 E(G)中的边
(若为网时，则在边存在的位置写上权值 w )
7.2 图的存储结构
v1 v4 0 1 1 1
A1= 1 0 1 1
1 1 0 0
v2 v3 1 1 0 0
v1 v4 0 0 0 1 0
0 0 1 0 0
v5 A2= 1 0 0 0 0
v2 v3 1 1 0 0 0
0 0 1 1 0
7.2 图的存储结构
Status CreateUDN(Mgraph &G)
{ scanf(&G.vexnum,&G.arcnum,&IncInfo);
for(i=0; i<G.vexnum; ++i ) scanf(&G.vexs[i]);
for(i=0; i<G.vexnum; ++i)
for(j=0; j<G.vexnum; ++j) G.arcs[i][j]={INFINITY,NULL}
for(k=0; k<G.arcnum; ++k)
{ scanf(&v1,&v2,&w);
i=LocateVex(G,v1); j=LocateVex(G,v2);
G.arcs[i][j].adj=w; if(IncInfo) Input(*G.arcs[i][j].info);
G.arcs[j][i]=G.arcs[i][j];
} return OK;
}
7.2 图的存储结构
邻接链表表示法边表,对于无向图而言,vi的邻接表中每一个表结点都对应于与 vi
相关联的一条边，因此，称之为边表。
出边表,对于有向图而言,vi的邻接表中每一个表结点都对应于以 vi为始头射出的一条边，因此，称之为出边表。
入边表,对于有向图而言,vi的邻接表中每一个表结点都对应于以 vi为终点射入的一条边，因此，称之为入边表。
（以入边表表示的称之为逆邻接表）
7.2 图的存储结构
邻接链表表示法 （ 顶点表） （ 边表）
v1 v4 1 v1 2 3 4
2 v2 1 3 4
3 v3 1 2
v2 v3 4 v4 1 2
v1 v4 1 v1 4
2 v2 3
v5 3 v3 1
v2 v3 4 v4 1 2
5 v5 3 4
7.2 图的存储结构
逆邻接链表表示法
（ 顶点表） （ 入边表）
v1 v4 1 v1 3 4
2 v2 4
v5 3 v3 2 5
4 v4 1 5
v2 v3 5 v5
7.3 图的遍历
图的遍历,从图的某一顶点出发，沿着某条搜索路径对图中所有顶点仅作一次访问的过程。
深度优先搜索（ Depth_First Search,DFS）遍历,首先访问出发点 vi，并将其标记为已访问过，然后依次从 vi出发搜索 vi的每一个邻接点 vj，若 vj未被访问过，则以 vj为新的出发点继续进行深度优先搜索。它的特点是尽可能先对纵深方向进行搜索，故称之为深度优先搜索。 （它类似于树的先根遍历）
按访问顶点的走向次序所得到的顶点序列，称为该图的深度优先搜索遍历序列，简称为 DFS序列 。
由此，当以邻接表作存储结构时，深度优先搜索遍历的 时间复杂度为 O(n+e)。
（参见,P168-图 7.13（ a）、（ b））
7.3 图的遍历
深度优先搜索遍历算法（邻接表）
Void DFSTraverse(Graph G,status (*visit)(int v))
{ for (v=0; v<G.vexnum; ++v) visited[v]=FALSE;
for (v=0; v<G.vexnum; ++v)
if (! Visited[v]) DFS(G,v);
}
Void DFS(Graph G,int v)
{ visited[v]=TRUE; VisitFunc(v);
for (w=FirstAdjVex(G,v); w; w=NextAdjVex(G,v,w))
if (! Visited[w]) DFS(G,w);
}
7.3 图的遍历
广度优先搜索（ Breadth_First Search,BFS）遍历,首先访问出发点 vi，并将其标记为已访问过，接着依次访问 vi的所有邻接点，
然后再依次访问与其邻接的所有未曾访问过的顶点，依次类推，
直至图中所有和初始出发点 vi有路径相通的顶点都已访问过为止。
它的特点是尽可能先对横向进行搜索，故称之为广度优先搜索。
（它类似于树的按层次遍历）
按访问顶点的走向次序所得到的顶点序列，称为该图的广度优先搜索遍历序列，简称为 BFS序列 。
由此，当以邻接表作存储结构时，广度优先搜索遍历的 时间复杂度为 O(n+e)。
（参见,P168-图 7.13（ a）、（ c））
7.3 图的遍历
Void BFS(Graph G,status (* visit) (int v))
{ for (v=0; v<G.vexnum; ++v) visited[v]=FALSE;
InitQueue(Q);
for (v=0; v<G.vexnum; ++v)
if (! Visited[v])
{ EnQueue(Q,v);
while (! QueueEmpty)
{ DeQueue(Q,u); visited[u]=TRUE; Visit(u);
for (w=FirstAdjVex(G,u); w; w=NextAdjVex(G,u,w))
if (! visited[w]) EnQueue(Q,w ); }
}
}
练习题,
给出图 G的邻接矩阵和邻接表两种存储结构，并分别给出图 G的 DFS序列和 BFS序列。
1 2
3
4 5
（图 G）
上机题：
建立图 G的邻接矩阵和邻接链表，并在此存储结构上进行 DFS遍历和 BFS遍历，输出 DFS序列和 BFS序列。
7.4 生成树和最小生成树
生成树,一个连通图 G的子图，如果是一个包含 G的所有顶点的树
（无回路的连通图），则该子图称为 G的生成树（它是连通图的一个极小连通子图）。
如何求得生成树？
设图 G是一个具有 n个顶点的连通图，则从 G的任一顶点出发，
作一次深度优先搜索或广度优先搜索，就可将 G中所有 n个顶点都访问到，访问中经过 n-1条边，这 n-1条边将 n个顶点连接成 G的极小连通子图，它就是 G的一棵生成树。
通常：由深度优先搜索得到的生成树称为深度优先生成树，简称 DFS
生成树。
由广度优先搜索得到的生成树称为广度优先生成树，简称 BFS
生成树。
7.4 生成树和最小生成树
v1
v2 v3
v4 v5 v6 v7
v8
(图 G)
v1 v1
v2 v3 v2 v3
v4 v5 v6 v7 v4 v5 v6 v7
v8 v8
（ DFS生成树） （ BFS生成树）
7.4 生成树和最小生成树
最小生成树,对于连通网络 G,边是带权的，因而 G的生成树的各边也是带权的,把生成树的各边的权值总和称为生成树的权，则权最小的生成树称为 G的最小生成树。
MST性质,假设 N=（ V,E）是一个连通网,U是顶点集 V的一个非空子集。若（ u,v）是一条具有最小权值的边，其中 u∈U,
v∈V -U，则必存在一棵包含边（ u,v）的最小生成树。
利用 MST性质构造最小生成树的算法：
Prim算法（参见,P174-图 7.16、图 7.17和算法 7.9）
Kruskal算法（参见,P176-图 7.18）
7.4 生成树和最小生成树
Void MiniSpanTree_Prim(MGrph G,VertexType u)
{ k=LocateVex(G,u);
for (j=0; j<G.vexnum; ++j)
if (j !=k) closedge[j]={u,G.arcs[k][j].adj};
closedge[k].lowcost=0;
for (i=1; i<G.vexnum; ++i )
{ k=mininum(closedge);
printf( closedge[k].adjvex,G.vexs[k]);
closedge[k].lowcost=0;
for (j=0; j<G.vexnum; ++j)
if (G.arcs[k][j].adj<closedge[j].lowcost)
closedge[j]={G.vexs[k],G.arcs[k][j].adj};
}
}
练习题
使用 Prim和 Kruskal算法构造图 G的一棵最小生成树。
①
6 5
② 5 1 5 ④
③
3 6 4 2
⑤ 6 ⑥
7.5 拓扑排序
拓扑排序,由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
偏序,若集合 X上的关系 R是自反的、反对称的和传递的，则称 R是集合 X上的偏序关系。
全序,设 R是集合 X上的偏序，如果对每个 x,y∈X,必有 xRy，或 yRx，则称 R是集合 X上的全序关系。
AOV网,用顶点表示活动，用弧表示活动间的优先关系的有向图称为 AOV（ Activity On Vertex
Network） 网,
7.5 拓扑排序
如何进行拓扑排序？
（ 1）在有向图中选一个没有前驱的顶点且输出之。
（ 2）从图中删除该顶点和所有以它为尾的弧。
重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。
（参见,P182-图 7.28）
7.5 拓扑排序
Status Topologicalsort(ALGraph G)
{ FindInDegree(G,indegree);
InitStack(S);
for (i=0; i<G.vexnum; ++i)
if (! Indegree[i]) Push(S,i);
count=0;
while (! StackEmpty(S))
{ Pop(S,i); print(i,G.vextices[i].data); ++coun
for (p=G.vextices[i].firstarc; p; p=p->nextarc)
{ k=p->adjvex; if(! (--indegree[k])) Push(S,k); }
} if(count<G.vexnum) return ERROR;
else return OK;
}
7.6 关键路径
AOE(Activity On Edge network)网：
即边表示活动的网络。 AOE网是一个带权的有向图。
其中：顶点表示事件，边表示活动。
源点,网中只有一个入度为零的顶点。
汇点,网中只有一个出度为零的顶点。
关键路径,从源点到汇点的最长路径。
关键活动,关键路径上的所有活动都是关键活动。
AOE网待研究的问题是：
（ 1）完成整个工程至少需要多少时间？
（ 2）哪些活动是影响工程进度的关键？
7.6 关键路径以 P183-图 7.29为例可见：
（ 1）整个工程需要 18天才能完成。
（ 2）影响工程的关键路径是：
( v1 v2 v5 v8 v9 ),18天
( v1 v2 v5 v7 v9 ),18天
7.6 关键路径
关键活动,把 e(i)=l(i)的活动 ai称为关键活动。
其中,e(i)表示活动 ai的最早开始时间。（例,a6,5）
l(i)表示活动 ai的最迟开始时间。（例,a6,8）
关系式：
e(i)=ve(j)
l(i)=vl(k)-dut(<j,k>)
其中,ve(j)：事件 vj的最早发生时间（是从源点 v1到顶点
vj的最长路径的长度,例,ve(5)=7）。
vl(j)：事件 vj的最迟发生时间（在不推迟整个工程完成的前提下，应等于汇点 vn的最早发生时间 ve(n)减去 vk到 vn的最长路径长度，例,vl(5)=7）。
dut(<j,k>)：表示边 <vj,vk>的权值。
7.6 关键路径
事件 vj的最早发生时间 ve(j)的计算可用下列递推公式：
ve(1)=0
ve(j)=MAX{ ve(i)+dut(<i,j>) }
ve(1)=0
ve(2)= ve(1)+dut(<1,2>)=0+6=6
ve(3)= ve(1)+dut(<1,3>)=0+4=4
ve(4)= ve(1)+dut(<1,4>)=0+5=5
ve(5)= MAX{ ve(2)+dut(<2,5>),ve(3)+dut(<3,5>) }=MAX{6+1,4+1}=7
ve(6)= ve(4)+dut(<4,6>) =5+2=7
ve(7)= ve(5)+dut(<5,7>)=7+9=16
ve(8)= MAX{ve(5)+dut(<5,8>),ve(6)+dut(<6,8>)}=MAX{7+7,7+4}=14
ve(9)= MAX{ve(7)+dut(<7,9>),ve(8)+dut(<8,9>)}=MAX{16+2,14+4}=18
7.6 关键路径
事件 vj的最迟发生时间 vl(j)的计算可用下列递推公式：
vl(n)=ve(n)
vl(j)=MIN{ vl(k)-dut(< j,k>) }
vl(9)=ve(9)=18
vl(8)= vl(9)-dut(<8,9>)=18-4=14
vl(7)= vl(9)-dut(<7,9>)=18-2=16
vl(6)= vl(8)-dut(<6,8>)=14-4=10
vl(5)= MIN{ vl(8)-dut(<5,8>),vl(7)-dut(<5,7>) }=MIN{14-7,16-9}=7
vl(4)= vl(6)-dut(<4,6>) =10-2=8
vl(3)= vl(5)-dut(<3,5>)=7-1=6
vl(2)=vl(5)-dut(<2,5>)=7-1=6
vl(1)= MIN{vl(2)-dut(<1,2>),vl(3)-dut(<1,3>),vl(4)-dut(<1,4>)}
=MIN{6-6,6-4,8-5}=0
7.6 关键路径利用 ve和 vl的值，按公式即可计算出各活动 ai的最早开始时间 e(i)和最迟开始时间 l(i)，结果如下：
a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11
e 0 0 0 6 4 5 7 7 7 16 14
l 0 2 3 6 6 8 7 7 10 16 14
l-e 0 2 3 0 2 3 0 0 3 0 0
（从中可以看出,a1,a4,a7,a8,a10 和 a11是关键活动。）
7.6 关键路径由上述讨论可以得出 求关键活动算法的基本步骤：
（ 1）对 AOE网进行拓扑排序，同时按拓扑排序序列的次序求出各顶点事件的最早发生时间 ve，若网中有回路，则算法终止，否则执行步骤（ 2）。
（ 2）按拓扑序列的逆序求出各顶点事件的最迟发生时间
vl。
（ 3）根据各顶点事件的 ve值 vl值，求出各活动 ai的最早开始时间 e(i)和最迟开始时间 l(i)，若 e(i)=l(i)，
则 ai为关键活动。
7.6 关键路径
Status TopologicalOrder(ALGraph G,Stack &T)
{ FindInDegree(G,indegree);
InitStack(T); count=0; ve[0..G.vexnum-1]=0;
while (! StackEmpty(S))
{ Pop(S,j); Push(T,j); ++count;
for (p=G.vertices[j].firstarc; p; p=p->nextarc)
{ k=p->adjvex; if (--indegree[k]==0) Push(S,k);
if (ve[j]+*(p->info)>ve[k]) ve[k]=ve[j]+*(p->info); }
}
if (count<G.vexnum) return ERROR;
else return OK;
}
7.6 关键路径
Status CriticalPath(ALGraph G)
{ if (! ToplogicalOrder(G,T)) return ERROR
vl[0..G.vexnum]=ve[0..G.vexnum-1];
while (! StackEmpty(T))
for (Pop(T,j),p=G.vextices[j].firstarc; p; p=p->nextarc)
{ k=p->adjvex; dut=*(p->info);
if (vl[k]-dut<vl[j]) vl[j]=vl[k]-dut; }
for ( j=0; j<Gvexnum; ++j )
for ( p=G.vertices[j]; p; p=p->nextarc)
{ k=p->adjvex; dut=*(p->info);
ee=ve[j]; el=vl[k]-dut;
tag= (ee==el)? ‘*’,‘’ ; printf(j,k,dut,ee,el,tag ); }
}
上机题
对图 G所示的 AOE网，求出各项活动的最早开始时间和最迟开始时间，并回答：工程完成的最短时间是什么？哪些活动是关键活动。
v2 3 v4 4 v6
5 5 4
v1 6 3 v7 5 v9 2 v10
6 3 1 4 2
v3 v5 v8
(G)
7.7 最短路径
最短路径（交通咨询系统、网络通信系统）
单源点最短路径,给定带权有向图 G和源点 v，求从 v到
（ Dijkstra算法） G中其余各顶点的最短路径。
多源点最短路径,给定带权有向图 G，求 G中每一对顶
(Floyd算法 ) 点之间的最短路径。
7.7 最短路径
Dijkstra算法基本思想,按路径长度递增序产生诸顶点的最短路径。
具体步骤：
（ 1）用邻接矩阵 arcs来表示带权有向图,arcs[i][j]表示弧 <vi,vj>
上的权值。若 <vi,vj>不存在，则置 arcs[i][j]为 ≦ 。 S为已找到从 v出发的最短路径的终点的集合，它的初始状态为空集。那么，
从 v出发到图上其余各顶点可能的最短路径长度的初值为：
D[i]=arcs[Locate_Vex(G,v)][i] vi∈V
（ 2）选择 vj，使得
D[j]=Min{D[i]|vi∈V -S }
vj就是当前求得的一条从 v出发的最短路径的终点。令：
S=S∪ {j}
7.7 最短路径
（ 3）修改从 v出发到集合 V-S上任一顶点 vk可达的最短路径长度。如果
D[j]+arcs[j][k]<D[k]
则修改 D[k]为
D[k]=D[j]+arcs[j][k]
（ 4）重复 (2),(3)操作共 n-1次，由此求得从 v到图上其余各顶点的最短路径是依路径长度递增的序列。
（参见,P187-图 7.34、图 7.35）
7.7 最短路径
Void ShortestPath_DIJ(Mgraph G,int v0,PathMatrix &p,
shortPathTable &D)
{ for (v=0; v<G.vexnum; ++v)
{ final[v]=FALSE; D[v]=G.arcs[v0][v];
for (w=0; w<G.vexnum; ++w) P[v][w] =FALSE;
if (D[v]<INFINITY) { P[v][v0]=TRUE; P[v][v]=TRUE; }
}
D[v0]=0; final[v0]=TRUE;
for (i=1; i<G.vexnum; ++i )
{ min=INFINITY;
for (w=0; w<G.vexnum; ++w)
if (! final[w])
if (D[w]<min) { v=w; min=D[w];}
7.7 最短路径
final[v]=TRUE;
for (w=0; w<G.vexnum; ++w)
if (! Final[w] && (min+G.arcs[v][w]<D[w]))
{ D[w]=min+G.arcs[v][w];
P[w]=P[v]; P[w][w]=TRUE;
}
}
}
7.7 最短路径
用 Dijkstra算法求出有向网 G的单源点 (① )的最短路径。
①
10 100
② 30 ⑤
50 10 60
③ 20 ④
（ G）
7.7 最短路径源点 中间顶点 终点 路径长度
1 2 10
1 4 30
1 4 3 50
1 4,3 5 60
7.7 最短路径
Floyd算法基本思想,经过 n次试探，以求得顶点 vi到 vj的最短路径。
具体方法,定义一个阶方阵序列
D(-1),D(0),D(1),…,D (k),…,D (n-1)
其中：
D(-1)[i][j]=arcs[i][j]
D(k)[i][j]=Min{D(k-1)[i][j],D(k-1) [i][k]+D(k-1) [k][j]} 0≤k≤n-1
由上述计算公式可见：
D(1)[i][j]是从 vi到 vj的中间顶点的序号不大于 1的最短路径长度；
D(k)[i][j]是从 vi到 vj的中间顶点的序号不大于 k的最短路径长度；
D(n-1)[i][j]就是从 vi到 vj的最短路径长度；
7.7 最短路径
（参见 P191-图 7.36、图 7.37）
Void ShortestPath_Floyd(Mgraph G,PathMatrix &P[],
DistancMatrix &D)
{ for (v=0; v<G.vexnum; ++v)
for (w=0; w<G.vexnum; ++w)
{ D[v][w]=G.arcs[v][w];
for (u=0; u<G.vexnum; ++u) P[v][w][u]=FALSE;
if (D[v][w]<INFINITY)
{ P[v][w][v]=TRUE; P[v][w][w]=TRUE; }
}
7.7 最短路径
for (u=0; u<G.vexnum; ++u)
for (v=0; v<G.vexnum; ++v)
for (w=0; w<G.vexnum; ++w)
if (D[v][u]+D[u][w]<D[v][w])
{ D[v][w]=D[v][u]+D[u][w];
for (i=0; i<G.vexnum; ++i)
P[v][w][i]=P[v][u][i] || P[u][w][i];
}
}
树的定义,树是 n(n≥0)个结点的有限集。
它满足以下两个条件,
（ 1）有且仅有一个特定的称为根的结点。
（ 2）其余的结点可分为 m个互不相交的有限集合 T1,
T2,…,T m,其中，每个集合又都是一棵树（子树）。
树的表示
6.1 树结点的度,一个结点的子树个数称为该结点的度。
树的度,一棵树中结点度的最大值。
叶子（终端结点）,度为 0的结点。
分支结点（非终端结点）,度不为 0的结点。
内部结点,除根结点之外的分支结点。
孩子,树中某个结点的子树的根称为个结点的孩子。
双亲,该结点则为孩子的双亲。
兄弟,同一个双亲的孩子。
路径,若树中存在一个结点序列 k1,k2,…,kj，使得 ki是 ki+1的双亲
(1≤i<j),称该结点序列是从 k1到 kj的一条路径。
祖先,若树中结点 k到 ks存在一条路径，则称 k是 ks的祖先。
子孙,ks是 k的子孙。
6.1 树层次,结点的层次是从根开始算起 (根为 1层 )。
高度,树中结点的最大层次称为树的高度或深度。
有序树,若将树中每个结点的各子树看成是从左到右有秩序的。
无序树,否则称为无序树。
森林,是 m(m≥0)棵互不相交的树的集合。
(树形结构的逻辑特征可用树中结点之间的父子关系来描述 )
6.1 树树的基本操作有下列几种：
（ 1）初始化操作。
（ 2）求根函数。
（ 3）求双亲函数。
（ 4）求孩子结点函数。
（ 5）求右兄弟函数。
（ 6）建树函数。
（ 7）插入子树操作。
（ 8）删除子树操作。
（ 9）遍历操作。
（ 10）清除结构操作。
6.2 二叉树
概念
性质
存储结构
遍历
线索化
6.2 二叉树
概念定义：二叉树是个结点的有限集，它或者是空集，
或者由一个根结点及两棵不相交的分别称作这个根的左子树和右子树的二叉树组成。
二叉树的五种基本形态
6.2 二叉树
二叉树的性质
1、二叉树第 i层上的结点数目最多为 2i-1(i≥0) 。
归纳法证明：
归纳基础,i=1时，有 2i-1=20=1。
归纳假设：假设对所有的 j(1≤j<i) 命题成立，即第 j层上至多有 2j-1个结点，证明 j=i时命题成立。
归纳步骤：根据归纳假设，第 i-1层上至多有 2i-2个结点，由于二叉树的每个结点至多有两个孩子，故第 i层上的结点至多是第 i层上的最大结点数的 2倍，即 j=i时该层上至多有 2*2i-2=2i-1个结点，故命题成立。
6.2 二叉树
2、深度为 k的二叉树至多有 2k-1个结点。
证明：在具有相同深度的二叉树中，仅当每一层都含有最多结点时，
其树中结点数最多。因此，利用性质 1可得，深度为的二叉树中至多含有的结点数为：
20+21+… +2k-1=2k-1
故命题正确。
3、在任意一棵二叉树中，若终端结点的个数为 n0，度为 2
的结点数为 n2，则 n0=n2+1。
证明：因为二叉树中所有结点的度数均不大于 2，所以结点总数应等于 0度结点数,1度结点数和 2度结点数之和，即：
n=n0+n1+n2 ①
6.2 二叉树另一方面,1度结点有一个孩子,2度结点有两个孩子。所以，
二叉树中孩子结点总数是 n1+2n2，二叉树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可以表示为：
n=n1+2n2+1 ②
由式①和式②得到,n0=n2+1
两种特殊形式的二叉树：
满二叉树,一棵深度为 k且有 2k-1个结点的二叉树。
完全二叉树,若一棵二叉树至多只有最下面两层上结点的度数可以小于 2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。
6.2 二叉树
4、具有 n个结点的完全二叉树的深度为 log2n +1
证明：设所有完全二叉树的深度为 k，由完全二叉树的定义可知，它的前 k-1层是深度为 k-1的满二叉树，一共有 2k-1-1个结点。由于完全二叉树深度为 k，故第 k层上还有若干个结点，因此，
该完全二叉树的结点个数 n>2k-1-1。
另一方面，由性质 2可知 n≤2 k-1，即：
2k-1-1< n ≤2 k-1
由此可推出,2k-1 ≤ n < 2 k-1
取对数后有,k-1 ≤ log 2n < k
因为 k为整数，故有 k-1= log2n,由此可得：
k= log2n +1
6.2 二叉树
5、如果对一棵有 n个结点的完全二叉树，则对任一结点有：
（ 1）若 i=1，则 ki是根结点，无双亲；若 i>1,则 ki的双亲编号为 int(i/2)。
（ 2）若 2i≤n,则 ki的左孩子的编号是 2i； 2i>n,则无左孩子。
（ 3）若 2i+1≤n,则 ki右孩子的编号是 2i+1;2i+1>n,则无右孩子。
（ 4）若 i为奇数且不为 1，则 ki的左兄弟的编号是 i-1；否则 ki无左兄弟。
（ 5）若 i为偶数且小于 n，则 ki的右兄弟的编号是 i+1；否则 ki无右兄弟。
6.2 二叉树
二叉树的存储结构
1）顺序存储结构,对完全二叉树而言，既简单又节省存储空间，但对非完全二叉树，必须按完全二叉树的形式来存储树中的结点，这将造成存储空间的浪费。
A
0 B
0 0 0 C
1 2 3 4 5 6 7
A 0 B 0 0 0 C
6.2 二叉树
2）链式存储结构设计不同的结点结构可构成不同的链式存储结构。通常采用二叉链表的形式，即：
lchild data rchild
typedef struct BiTNode
{ TElemType data;
struct BiTNode *lchild,*rchild;
} *BiTree;
6.2 二叉树
二叉链表的生成
Status CreateBiTree(BiTree &T)
{ scanf(&ch);
if (ch==‘’) T=NULL;
else
{ if (!(T=(BiTNode *) malloc (sizeof(BiTNode)))) exit(OVERFLOW);
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}
6.2 二叉树
A
B C
D E F
T
A
B ∧ C
∧ D ∧ ∧ E ∧ ∧ F ∧
6.2 二叉树
二叉树的遍历遍历,是指沿某条搜索路径周游二叉树，对树中每个结点访问一次且仅访问一次。
前序遍历（ DLR）,访问根的操作是在遍历其左、右
(先根 ) 子树之前进行的。
中序遍历 （ LDR）,访问根的操作是在遍历其左、右
(中根 ) 子树之中进行的。
后序遍历（ LRD）,访问根的操作是在遍历其左、右
(后根 ) 子树之后进行的。
6.2 二叉树
A
B C
D E F
前序遍历序列,ABDCEF
中序遍历序列,DBAECF
后序遍历序列,DBEFCA
6.2 二叉树前序遍历递归算法：
Status PreOrder(BiTree T)
{ if (T) { Visit(T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
6.2 二叉树中序遍历递归算法：
Status InOrder(BiTree T)
① { if (T) {
② InOrder(T->lchild);
③ Visit(T->data);
④ InOrder(T->rchild);
}
⑤ }
6.2 二叉树后序遍历递归算法：
Status PostOrder(BiTree T)
{ if (T) { PostOrder(T->lchild);
PostOrder(T->rchild);
Visit(T->data);
}
}
6.2 二叉树
InOrder(&A) InOrder(&B) InOrder(&D) InOrder(NULL)
① ① ① ①
② ②
② ③ (访问 B) ③ ⑤
(访问 D)
③ (访问 A) ④ InOrder(NULL)
⑤ ①
④ ④ InOrder(NULL)
… ⑤ ① ⑤
⑤ ⑤
#
( 中序遍历序列,DBAECF )
6.2 二叉树
中序遍历二叉树的非递归算法：
Status InOrder1(BiTree T,status (* visit)(TelemType e))
{ Initstack(S); Push(S,T);
while (! StackEmpty(S))
{ while (GetTop(S,p) && p) Push(S,p->lchild);
Pop(S,p);
if (! StackEmpty(S))
{ Pop(S,p); if (! Visit(p->data)) return ERROR;
Push(S,p->rchild);
}
}
}
6.2 二叉树
,遍历”是二叉树各种操作的基础。
由上讨论得知：
遍历二叉树是以一定规则将二叉树中的结点排列成一个线性序列，得到二叉树中结点的先序序列或中序序列或后序序列。
这实质上是对一个非线性结构进行线性化。
练习题
已知某二叉树的前序遍历序列为 ABDEGCFHIJ，
中序遍历序列为,DBGEAHFIJC，请写出该二叉树的后序遍历序列？
求某二叉树的叶子数。
参考答案：
A
B C
D E F
G H I
J
后序遍历序列,
DGEBHJIFCA
参考答案：
Status countleaf(BiTree T,int &count)
{ if (T) { if (T->lchild==NULL && T->rchild==NULL)
count++;
countleaf(T->lchild,count);
countleaf(T->rchild,count);
}
}
6.2 二叉树结点的结构,lchild ltag data rtag rchild
其中,ltag= 0 指示结点的左孩子
1 指示结点的前驱
rtag= 0 指示结点的右孩子
1 指示结点的后继
线索链表：以上述结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表。
线索：其中指向结点的前驱和后继的指针，叫做线索。
线索二叉树：加上线索的二叉树称之为线索二叉树。
线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。
6.2 二叉树中序线索二叉树,
A
NULL
NULL B E
C D F
G
H r I
6.2 二叉树
中序遍历建立线索化链表的算法
Status InOrderThreading(BiThrTree &Thrt,BiThrTree T)
{ if (! (Thrt=(BiThrTree) malloc (sizeof(BiThrNode))))
exit(OVERFLOW);
Thrt->Ltag=Link; Thrt->Rtag=Thread;
Thrt->rchild=Thrt;
if (! T) Thrt->lchild=Thrt;
else { Thrt->lchild=T; pre=Thrt;
InThreading(T);
pre=->rchild=Thrt; pre->Rtag=Thread;
Thrt->rchild=pre;
} return OK;
}
6.2 二叉树
Status InThreading(BiThrTree p)
{ if (p) { InThreading(p->lchild);
if (! P->lchild) { p->Ltag=Thread;
p->lchild=pre; }
if (! Pre->rchild) { pre->Rtag=Thread;
pre->rchild=p; }
pre=p;
InThreading(p->rchild);
}
}
6.2 二叉树
线索二叉树的三种常用运算,
查找某结点 P在指定次序下的前驱和后继遍历线索二叉树线索二叉树的插入
6.2 二叉树
查找某结点 P在指定次序下的后继
Statust inordernext(BiThrptr p)
{ if (p->Rtag==1) return (p->rchild);
else { q=p->rchild;
while (q->Ltag==0) q=q->lchild;
return (q);
}
}
6.2 二叉树
查找某结点 P在指定次序下的前驱
Statust inorderpre(BiThrptr p)
{ if (p->Ltag==1) return (p->lchild);
else { q=p->lchild;
while (q->Rtag==0) q=q->rchild;
return (q);
}
}
练习题
画出下列二叉树的前序、中序和后序线索二叉树。
A
B C
D E F
G H
6.3 树和森林
树的存储结构
树和森林与二叉树的转换
树和森林的遍历
6.3 树和森林
树的存储结构双亲表示法孩子表示法孩子兄弟表示法
6.3 树和森林
树和森林与二叉树的转换
A A
B
B C D E C
F G D
E F G H I J H
I
J
6.3 树和森林
A
A E G B E
B C D F H I C F G
D H
I
6.3 树和森林
树和森林的遍历树的先序遍历,先访问树的根结点，然后依次先序遍历根的每棵子树。
树的后序遍历,先依次后序遍历每棵子树，然后访问根结点。
（参见,P137—图 6.16）
注,先序遍历一棵树恰好等价于先序遍历该树对应的二叉树 ;
后序遍历一棵树恰好等价于中序遍历该树对应的二叉树 ;
6.3 树和森林
树和森林的遍历森林的先序遍历,
(1) 先访问森林中第一棵树的根结点 ;
(2) 先序号遍礼第一棵树中根结点的子树森林 ;
(3) 先序遍历除去第一棵树之后剩余的树构成的森林。
森林的中序遍历：
(1) 中序遍历森林中第一棵树的根结点的子树森林 ;
(2) 访问第一棵树的根结点 ;
(3) 中序遍历除去第一棵树之后剩余的树构成的森林。
（参见,P138—图 6.17）
6.4 哈夫曼树及应用
概念路径,从树中一个结点到另一个结点之间的分支构成了这两个结点之间的路径。
路径长度,路径上的分支数目称做路径长度。
树的路径长度,从树根到树中每一结点的路径长度之和。
结点的带权路径长度,从该结点到树根之间的路径长度与结点上权的乘积。
树的带权路径长度,树中所有叶子结点的带权路径长度之和
（ WPL）。
（参见,P144—图 622）
6.4 哈夫曼树及应用
最优二叉树 (哈夫曼树 )
带权路径长度 WPL最小的二叉树，称之为最优二叉树。
（如何构造最优二叉树？）
哈夫曼算法：
（ 1） 根据给定的 n个权值 { w1,w2,…,wn }构成 n棵二叉树的集合
F={T1,T2,…,Tn}，其中每棵二叉树 Ti中只有一个带权为 wi的根结点，
其左右子树均为空。
（ 2） 在 F中选取每棵根结点的权值最小的树作为左右子树构造新的二叉树，
且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
（ 3） 在 F中删除这两棵树，同时将新得到的二叉树加入 F中。
（ 4） 重复（ 2）和（ 3），直到 F含一棵树为止。
(参见,P146—图 624)
6.4 哈夫曼树及应用
哈夫曼编码前缀编码,任意一个字符的编码都不是另一个字符的编码的前缀。
0 1 a的编码,0
a b的编码,10
0 1 c的编码,110
b d的编码,111
0 1
c d
上机题：
以（ P148-例 6-2）为例，根据算法 6.12设计哈夫曼编码。
第 7章 图 （ 6学时）
图的概念
图的存储结构 (邻接矩阵、邻接链表等 )
图的遍历 (DFS和 BFS)
生成树和最小生成树 (Prim算法和 Kruskal算法 )
拓扑排序
关键路径
最短路径 (Dijkstra算法和 Floyd算法 )
7.1 图的概念图是一种复杂的非线性结构
图,由顶点集 V和边集 E组成，记为：
G=（ V,E）
例：
A A A 3 B
5 8 4 9 E
B B C 6 9
C 2 D
C D
(G1) (G2) (G3)
7.1 图的概念
有向图,若图 G中的每条边都是有方向的，则称 G为有向图。
例：图 G1 V(G1)={A,B,C}
E(G1)={<A,B>,<B,A>,<B,C >}
无向图,若图 G中的每条边都没有方向的，则称 G为无向图。
例：图 G2 V(G2)={A,B,C,D}
E(G2)={(A,B),(A,C),(A,D),(B,C),(B,D),(C,D)}
网络,若将图的每条边都赋上一个具有某种有意义的数（权），
则称这种带权的图为网络。
例：图 G3
有向完全图,若有向图 G的顶点数 n和边数 e恰有 e=n(n-1)条边。
无向完全图,若有向图 G的顶点数和边数恰有 e=n(n-1)/2条边。
7.1 图的概念
关联,若 (vi,vj)是一条无向边，则称顶点 vi和 vj互为邻接点，或称
vi和 vj相邻接；并称边 (vi,vj)关联于顶点 vi和 vj，或称边
(vi,vj)与顶点 vi和 vj相关联。
子图,设 G=（ V,E）是一个图，若 V’是 V的子集,E’是 E的子集，
且 E’中的边所关联的顶点均在 V’中，则 G’=（ V’,E’）也是一个图，则称其为 G的子图。
例：
A A
A B C
B C
D
7.1 图的概念
度,无向图中顶点 V的度是关联于该顶点的边的数目，记为 D(V)。
若 G为有向图，则以顶点 V为终点的边的数目称为 V的入度，
记为 ID(V)；把以顶点 V为始点的边的数目称为 V的出度，记为 OD(V)；那么顶点 V的度则定义为该顶点的入度与出度之和。
结论：无论是有向图还是无向图，顶点数 n、边数 e和度数之间有如下关系：
E= (∑D(vi))/2 i,1～ n
例：图 G1：
e=(D(A)+D(B)+D(C))/2=((1+1)+(1+2)+(1))/2=3
图 G2：
e=(D(A)+D(B)+D(C)+D(D))/2=12/2=6
7.1 图的概念
路径,在图 G中，若存在一个顶点序列 vp,vi1,vi2,…,v q，使得
(vp,vi1),(vi1,vi2),…,(v in,vq)均属于 E(G)，则称到顶点 vp到 vq
存在一条路径。
路径长度,该路径上边的数目。
简单路径,若一条路径上除 vp和 vq可以相同外，其余顶点均不相同，则称此路径为一条简单路径。
简单回路,起点和终点相同的简单路径。
7.1 图的概念
连通,在无向图 G中，若从顶点 vi到 vj有路径，则称 vi和 vj是连通的。
连通图,若 V(G)中任意两个不同的顶点 vi和 vj都连通，则称 G为连通图。
连通分量,无向图 G的极大连通子图称为 G的连通分量。
（参见,P159—图 7.3）
强连通图,在有向图中，若对于 V(G)中任意两个不同的顶点 vi和 vj
都存在从 vi到 vj以及 vj到 vi的路径，则称 G是强连通图。
强连通分量,有向图 G的极大连通子图称为 G的强连通分量。
（参见,P159—图 7.4）
7.2 图的存储结构图的常用存储表示方法有：邻接矩阵（数组）、邻接表、邻接多重表和十字链表等。
邻接矩阵表示法邻接矩阵,是表示顶点之间相邻关系的矩阵。
设 G=（ V,E）是具有 n个顶点的图，则 G的邻接矩阵是具有如下性质的 n阶方阵。
A[i][j]= 1 若 (vi,vj)或 < vi,vj >是 E(G)中的边
0 若 (vi,vj )或 < vi,vj >不是 E(G)中的边
(若为网时，则在边存在的位置写上权值 w )
7.2 图的存储结构
v1 v4 0 1 1 1
A1= 1 0 1 1
1 1 0 0
v2 v3 1 1 0 0
v1 v4 0 0 0 1 0
0 0 1 0 0
v5 A2= 1 0 0 0 0
v2 v3 1 1 0 0 0
0 0 1 1 0
7.2 图的存储结构
Status CreateUDN(Mgraph &G)
{ scanf(&G.vexnum,&G.arcnum,&IncInfo);
for(i=0; i<G.vexnum; ++i ) scanf(&G.vexs[i]);
for(i=0; i<G.vexnum; ++i)
for(j=0; j<G.vexnum; ++j) G.arcs[i][j]={INFINITY,NULL}
for(k=0; k<G.arcnum; ++k)
{ scanf(&v1,&v2,&w);
i=LocateVex(G,v1); j=LocateVex(G,v2);
G.arcs[i][j].adj=w; if(IncInfo) Input(*G.arcs[i][j].info);
G.arcs[j][i]=G.arcs[i][j];
} return OK;
}
7.2 图的存储结构
邻接链表表示法边表,对于无向图而言,vi的邻接表中每一个表结点都对应于与 vi
相关联的一条边，因此，称之为边表。
出边表,对于有向图而言,vi的邻接表中每一个表结点都对应于以 vi为始头射出的一条边，因此，称之为出边表。
入边表,对于有向图而言,vi的邻接表中每一个表结点都对应于以 vi为终点射入的一条边，因此，称之为入边表。
（以入边表表示的称之为逆邻接表）
7.2 图的存储结构
邻接链表表示法 （ 顶点表） （ 边表）
v1 v4 1 v1 2 3 4
2 v2 1 3 4
3 v3 1 2
v2 v3 4 v4 1 2
v1 v4 1 v1 4
2 v2 3
v5 3 v3 1
v2 v3 4 v4 1 2
5 v5 3 4
7.2 图的存储结构
逆邻接链表表示法
（ 顶点表） （ 入边表）
v1 v4 1 v1 3 4
2 v2 4
v5 3 v3 2 5
4 v4 1 5
v2 v3 5 v5
7.3 图的遍历
图的遍历,从图的某一顶点出发，沿着某条搜索路径对图中所有顶点仅作一次访问的过程。
深度优先搜索（ Depth_First Search,DFS）遍历,首先访问出发点 vi，并将其标记为已访问过，然后依次从 vi出发搜索 vi的每一个邻接点 vj，若 vj未被访问过，则以 vj为新的出发点继续进行深度优先搜索。它的特点是尽可能先对纵深方向进行搜索，故称之为深度优先搜索。 （它类似于树的先根遍历）
按访问顶点的走向次序所得到的顶点序列，称为该图的深度优先搜索遍历序列，简称为 DFS序列 。
由此，当以邻接表作存储结构时，深度优先搜索遍历的 时间复杂度为 O(n+e)。
（参见,P168-图 7.13（ a）、（ b））
7.3 图的遍历
深度优先搜索遍历算法（邻接表）
Void DFSTraverse(Graph G,status (*visit)(int v))
{ for (v=0; v<G.vexnum; ++v) visited[v]=FALSE;
for (v=0; v<G.vexnum; ++v)
if (! Visited[v]) DFS(G,v);
}
Void DFS(Graph G,int v)
{ visited[v]=TRUE; VisitFunc(v);
for (w=FirstAdjVex(G,v); w; w=NextAdjVex(G,v,w))
if (! Visited[w]) DFS(G,w);
}
7.3 图的遍历
广度优先搜索（ Breadth_First Search,BFS）遍历,首先访问出发点 vi，并将其标记为已访问过，接着依次访问 vi的所有邻接点，
然后再依次访问与其邻接的所有未曾访问过的顶点，依次类推，
直至图中所有和初始出发点 vi有路径相通的顶点都已访问过为止。
它的特点是尽可能先对横向进行搜索，故称之为广度优先搜索。
（它类似于树的按层次遍历）
按访问顶点的走向次序所得到的顶点序列，称为该图的广度优先搜索遍历序列，简称为 BFS序列 。
由此，当以邻接表作存储结构时，广度优先搜索遍历的 时间复杂度为 O(n+e)。
（参见,P168-图 7.13（ a）、（ c））
7.3 图的遍历
Void BFS(Graph G,status (* visit) (int v))
{ for (v=0; v<G.vexnum; ++v) visited[v]=FALSE;
InitQueue(Q);
for (v=0; v<G.vexnum; ++v)
if (! Visited[v])
{ EnQueue(Q,v);
while (! QueueEmpty)
{ DeQueue(Q,u); visited[u]=TRUE; Visit(u);
for (w=FirstAdjVex(G,u); w; w=NextAdjVex(G,u,w))
if (! visited[w]) EnQueue(Q,w ); }
}
}
练习题,
给出图 G的邻接矩阵和邻接表两种存储结构，并分别给出图 G的 DFS序列和 BFS序列。
1 2
3
4 5
（图 G）
上机题：
建立图 G的邻接矩阵和邻接链表，并在此存储结构上进行 DFS遍历和 BFS遍历，输出 DFS序列和 BFS序列。
7.4 生成树和最小生成树
生成树,一个连通图 G的子图，如果是一个包含 G的所有顶点的树
（无回路的连通图），则该子图称为 G的生成树（它是连通图的一个极小连通子图）。
如何求得生成树？
设图 G是一个具有 n个顶点的连通图，则从 G的任一顶点出发，
作一次深度优先搜索或广度优先搜索，就可将 G中所有 n个顶点都访问到，访问中经过 n-1条边，这 n-1条边将 n个顶点连接成 G的极小连通子图，它就是 G的一棵生成树。
通常：由深度优先搜索得到的生成树称为深度优先生成树，简称 DFS
生成树。
由广度优先搜索得到的生成树称为广度优先生成树，简称 BFS
生成树。
7.4 生成树和最小生成树
v1
v2 v3
v4 v5 v6 v7
v8
(图 G)
v1 v1
v2 v3 v2 v3
v4 v5 v6 v7 v4 v5 v6 v7
v8 v8
（ DFS生成树） （ BFS生成树）
7.4 生成树和最小生成树
最小生成树,对于连通网络 G,边是带权的，因而 G的生成树的各边也是带权的,把生成树的各边的权值总和称为生成树的权，则权最小的生成树称为 G的最小生成树。
MST性质,假设 N=（ V,E）是一个连通网,U是顶点集 V的一个非空子集。若（ u,v）是一条具有最小权值的边，其中 u∈U,
v∈V -U，则必存在一棵包含边（ u,v）的最小生成树。
利用 MST性质构造最小生成树的算法：
Prim算法（参见,P174-图 7.16、图 7.17和算法 7.9）
Kruskal算法（参见,P176-图 7.18）
7.4 生成树和最小生成树
Void MiniSpanTree_Prim(MGrph G,VertexType u)
{ k=LocateVex(G,u);
for (j=0; j<G.vexnum; ++j)
if (j !=k) closedge[j]={u,G.arcs[k][j].adj};
closedge[k].lowcost=0;
for (i=1; i<G.vexnum; ++i )
{ k=mininum(closedge);
printf( closedge[k].adjvex,G.vexs[k]);
closedge[k].lowcost=0;
for (j=0; j<G.vexnum; ++j)
if (G.arcs[k][j].adj<closedge[j].lowcost)
closedge[j]={G.vexs[k],G.arcs[k][j].adj};
}
}
练习题
使用 Prim和 Kruskal算法构造图 G的一棵最小生成树。
①
6 5
② 5 1 5 ④
③
3 6 4 2
⑤ 6 ⑥
7.5 拓扑排序
拓扑排序,由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
偏序,若集合 X上的关系 R是自反的、反对称的和传递的，则称 R是集合 X上的偏序关系。
全序,设 R是集合 X上的偏序，如果对每个 x,y∈X,必有 xRy，或 yRx，则称 R是集合 X上的全序关系。
AOV网,用顶点表示活动，用弧表示活动间的优先关系的有向图称为 AOV（ Activity On Vertex
Network） 网,
7.5 拓扑排序
如何进行拓扑排序？
（ 1）在有向图中选一个没有前驱的顶点且输出之。
（ 2）从图中删除该顶点和所有以它为尾的弧。
重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。
（参见,P182-图 7.28）
7.5 拓扑排序
Status Topologicalsort(ALGraph G)
{ FindInDegree(G,indegree);
InitStack(S);
for (i=0; i<G.vexnum; ++i)
if (! Indegree[i]) Push(S,i);
count=0;
while (! StackEmpty(S))
{ Pop(S,i); print(i,G.vextices[i].data); ++coun
for (p=G.vextices[i].firstarc; p; p=p->nextarc)
{ k=p->adjvex; if(! (--indegree[k])) Push(S,k); }
} if(count<G.vexnum) return ERROR;
else return OK;
}
7.6 关键路径
AOE(Activity On Edge network)网：
即边表示活动的网络。 AOE网是一个带权的有向图。
其中：顶点表示事件，边表示活动。
源点,网中只有一个入度为零的顶点。
汇点,网中只有一个出度为零的顶点。
关键路径,从源点到汇点的最长路径。
关键活动,关键路径上的所有活动都是关键活动。
AOE网待研究的问题是：
（ 1）完成整个工程至少需要多少时间？
（ 2）哪些活动是影响工程进度的关键？
7.6 关键路径以 P183-图 7.29为例可见：
（ 1）整个工程需要 18天才能完成。
（ 2）影响工程的关键路径是：
( v1 v2 v5 v8 v9 ),18天
( v1 v2 v5 v7 v9 ),18天
7.6 关键路径
关键活动,把 e(i)=l(i)的活动 ai称为关键活动。
其中,e(i)表示活动 ai的最早开始时间。（例,a6,5）
l(i)表示活动 ai的最迟开始时间。（例,a6,8）
关系式：
e(i)=ve(j)
l(i)=vl(k)-dut(<j,k>)
其中,ve(j)：事件 vj的最早发生时间（是从源点 v1到顶点
vj的最长路径的长度,例,ve(5)=7）。
vl(j)：事件 vj的最迟发生时间（在不推迟整个工程完成的前提下，应等于汇点 vn的最早发生时间 ve(n)减去 vk到 vn的最长路径长度，例,vl(5)=7）。
dut(<j,k>)：表示边 <vj,vk>的权值。
7.6 关键路径
事件 vj的最早发生时间 ve(j)的计算可用下列递推公式：
ve(1)=0
ve(j)=MAX{ ve(i)+dut(<i,j>) }
ve(1)=0
ve(2)= ve(1)+dut(<1,2>)=0+6=6
ve(3)= ve(1)+dut(<1,3>)=0+4=4
ve(4)= ve(1)+dut(<1,4>)=0+5=5
ve(5)= MAX{ ve(2)+dut(<2,5>),ve(3)+dut(<3,5>) }=MAX{6+1,4+1}=7
ve(6)= ve(4)+dut(<4,6>) =5+2=7
ve(7)= ve(5)+dut(<5,7>)=7+9=16
ve(8)= MAX{ve(5)+dut(<5,8>),ve(6)+dut(<6,8>)}=MAX{7+7,7+4}=14
ve(9)= MAX{ve(7)+dut(<7,9>),ve(8)+dut(<8,9>)}=MAX{16+2,14+4}=18
7.6 关键路径
事件 vj的最迟发生时间 vl(j)的计算可用下列递推公式：
vl(n)=ve(n)
vl(j)=MIN{ vl(k)-dut(< j,k>) }
vl(9)=ve(9)=18
vl(8)= vl(9)-dut(<8,9>)=18-4=14
vl(7)= vl(9)-dut(<7,9>)=18-2=16
vl(6)= vl(8)-dut(<6,8>)=14-4=10
vl(5)= MIN{ vl(8)-dut(<5,8>),vl(7)-dut(<5,7>) }=MIN{14-7,16-9}=7
vl(4)= vl(6)-dut(<4,6>) =10-2=8
vl(3)= vl(5)-dut(<3,5>)=7-1=6
vl(2)=vl(5)-dut(<2,5>)=7-1=6
vl(1)= MIN{vl(2)-dut(<1,2>),vl(3)-dut(<1,3>),vl(4)-dut(<1,4>)}
=MIN{6-6,6-4,8-5}=0
7.6 关键路径利用 ve和 vl的值，按公式即可计算出各活动 ai的最早开始时间 e(i)和最迟开始时间 l(i)，结果如下：
a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11
e 0 0 0 6 4 5 7 7 7 16 14
l 0 2 3 6 6 8 7 7 10 16 14
l-e 0 2 3 0 2 3 0 0 3 0 0
（从中可以看出,a1,a4,a7,a8,a10 和 a11是关键活动。）
7.6 关键路径由上述讨论可以得出 求关键活动算法的基本步骤：
（ 1）对 AOE网进行拓扑排序，同时按拓扑排序序列的次序求出各顶点事件的最早发生时间 ve，若网中有回路，则算法终止，否则执行步骤（ 2）。
（ 2）按拓扑序列的逆序求出各顶点事件的最迟发生时间
vl。
（ 3）根据各顶点事件的 ve值 vl值，求出各活动 ai的最早开始时间 e(i)和最迟开始时间 l(i)，若 e(i)=l(i)，
则 ai为关键活动。
7.6 关键路径
Status TopologicalOrder(ALGraph G,Stack &T)
{ FindInDegree(G,indegree);
InitStack(T); count=0; ve[0..G.vexnum-1]=0;
while (! StackEmpty(S))
{ Pop(S,j); Push(T,j); ++count;
for (p=G.vertices[j].firstarc; p; p=p->nextarc)
{ k=p->adjvex; if (--indegree[k]==0) Push(S,k);
if (ve[j]+*(p->info)>ve[k]) ve[k]=ve[j]+*(p->info); }
}
if (count<G.vexnum) return ERROR;
else return OK;
}
7.6 关键路径
Status CriticalPath(ALGraph G)
{ if (! ToplogicalOrder(G,T)) return ERROR
vl[0..G.vexnum]=ve[0..G.vexnum-1];
while (! StackEmpty(T))
for (Pop(T,j),p=G.vextices[j].firstarc; p; p=p->nextarc)
{ k=p->adjvex; dut=*(p->info);
if (vl[k]-dut<vl[j]) vl[j]=vl[k]-dut; }
for ( j=0; j<Gvexnum; ++j )
for ( p=G.vertices[j]; p; p=p->nextarc)
{ k=p->adjvex; dut=*(p->info);
ee=ve[j]; el=vl[k]-dut;
tag= (ee==el)? ‘*’,‘’ ; printf(j,k,dut,ee,el,tag ); }
}
上机题
对图 G所示的 AOE网，求出各项活动的最早开始时间和最迟开始时间，并回答：工程完成的最短时间是什么？哪些活动是关键活动。
v2 3 v4 4 v6
5 5 4
v1 6 3 v7 5 v9 2 v10
6 3 1 4 2
v3 v5 v8
(G)
7.7 最短路径
最短路径（交通咨询系统、网络通信系统）
单源点最短路径,给定带权有向图 G和源点 v，求从 v到
（ Dijkstra算法） G中其余各顶点的最短路径。
多源点最短路径,给定带权有向图 G，求 G中每一对顶
(Floyd算法 ) 点之间的最短路径。
7.7 最短路径
Dijkstra算法基本思想,按路径长度递增序产生诸顶点的最短路径。
具体步骤：
（ 1）用邻接矩阵 arcs来表示带权有向图,arcs[i][j]表示弧 <vi,vj>
上的权值。若 <vi,vj>不存在，则置 arcs[i][j]为 ≦ 。 S为已找到从 v出发的最短路径的终点的集合，它的初始状态为空集。那么，
从 v出发到图上其余各顶点可能的最短路径长度的初值为：
D[i]=arcs[Locate_Vex(G,v)][i] vi∈V
（ 2）选择 vj，使得
D[j]=Min{D[i]|vi∈V -S }
vj就是当前求得的一条从 v出发的最短路径的终点。令：
S=S∪ {j}
7.7 最短路径
（ 3）修改从 v出发到集合 V-S上任一顶点 vk可达的最短路径长度。如果
D[j]+arcs[j][k]<D[k]
则修改 D[k]为
D[k]=D[j]+arcs[j][k]
（ 4）重复 (2),(3)操作共 n-1次，由此求得从 v到图上其余各顶点的最短路径是依路径长度递增的序列。
（参见,P187-图 7.34、图 7.35）
7.7 最短路径
Void ShortestPath_DIJ(Mgraph G,int v0,PathMatrix &p,
shortPathTable &D)
{ for (v=0; v<G.vexnum; ++v)
{ final[v]=FALSE; D[v]=G.arcs[v0][v];
for (w=0; w<G.vexnum; ++w) P[v][w] =FALSE;
if (D[v]<INFINITY) { P[v][v0]=TRUE; P[v][v]=TRUE; }
}
D[v0]=0; final[v0]=TRUE;
for (i=1; i<G.vexnum; ++i )
{ min=INFINITY;
for (w=0; w<G.vexnum; ++w)
if (! final[w])
if (D[w]<min) { v=w; min=D[w];}
7.7 最短路径
final[v]=TRUE;
for (w=0; w<G.vexnum; ++w)
if (! Final[w] && (min+G.arcs[v][w]<D[w]))
{ D[w]=min+G.arcs[v][w];
P[w]=P[v]; P[w][w]=TRUE;
}
}
}
7.7 最短路径
用 Dijkstra算法求出有向网 G的单源点 (① )的最短路径。
①
10 100
② 30 ⑤
50 10 60
③ 20 ④
（ G）
7.7 最短路径源点 中间顶点 终点 路径长度
1 2 10
1 4 30
1 4 3 50
1 4,3 5 60
7.7 最短路径
Floyd算法基本思想,经过 n次试探，以求得顶点 vi到 vj的最短路径。
具体方法,定义一个阶方阵序列
D(-1),D(0),D(1),…,D (k),…,D (n-1)
其中：
D(-1)[i][j]=arcs[i][j]
D(k)[i][j]=Min{D(k-1)[i][j],D(k-1) [i][k]+D(k-1) [k][j]} 0≤k≤n-1
由上述计算公式可见：
D(1)[i][j]是从 vi到 vj的中间顶点的序号不大于 1的最短路径长度；
D(k)[i][j]是从 vi到 vj的中间顶点的序号不大于 k的最短路径长度；
D(n-1)[i][j]就是从 vi到 vj的最短路径长度；
7.7 最短路径
（参见 P191-图 7.36、图 7.37）
Void ShortestPath_Floyd(Mgraph G,PathMatrix &P[],
DistancMatrix &D)
{ for (v=0; v<G.vexnum; ++v)
for (w=0; w<G.vexnum; ++w)
{ D[v][w]=G.arcs[v][w];
for (u=0; u<G.vexnum; ++u) P[v][w][u]=FALSE;
if (D[v][w]<INFINITY)
{ P[v][w][v]=TRUE; P[v][w][w]=TRUE; }
}
7.7 最短路径
for (u=0; u<G.vexnum; ++u)
for (v=0; v<G.vexnum; ++v)
for (w=0; w<G.vexnum; ++w)
if (D[v][u]+D[u][w]<D[v][w])
{ D[v][w]=D[v][u]+D[u][w];
for (i=0; i<G.vexnum; ++i)
P[v][w][i]=P[v][u][i] || P[u][w][i];
}
}
