数据结构 芦溪中学 胡小妹.

Presentation on theme: "数据结构 芦溪中学 胡小妹."— Presentation transcript:

1 数据结构 芦溪中学 胡小妹

2 数据结构的概念 学号 姓名 性别 民族 语文 数学 英语 总分 101 张华 男 汉 91 126 120 102 郝博 113 130
表：学生档案 学号 姓名 性别 民族 语文 数学 英语 总分 101 张华 男 汉 91 126 120 102 郝博 113 130 117 103 王静 女 回 97 114 92 104 孟晓立 苗 116 108 85 105 宋子荣 122 96 106 陈威 99

3 数据结构的概念 数据（data）：凡是能输入到计算机的描述客观事物的符号
数据元素（data element）：也叫结点（node）或记录（record），是数据的基本单位。如：表中的一行就是一个数据元素。 数据项（data item）：是数据不可分割的最小单位。如：“学号”、”数学“等。 数据对象（data object）：指性质相同的数据元素的集合。如：所有的男生就构成一个数据对象。 数据结构（data structure）：数据之间的关系。包括数据的逻辑结构和数据的存储结构（物理结构）。

4 数据的逻辑结构 计算机所处理的数据一般都存在某种内在的、特殊的关系，这种数据本身以及它们内在的相互之间的逻辑关系，叫做数据的逻辑结构。
用一个二元组 B=(D,S) 表示。 D表示结点构成的集合 S表示D中结点之间关系的集合 包括初等类型和组合类型 整型 实型 布尔型 字符型 指针型 集合结构：数据元素之间除了同属于一个集合的关系外，无任何其它关系。 线性结构：数据元素之间存在一对一的线性关系。 树型结构：数据元素之间存在一对多的层次关系。 图结构：数据元素之间存在多对多的任意关系。

5 数据的存储结构 顺序存储（数组） 表中一行（即一个学生信息）抽象成一个结点ai，ai与a(i+1)在存储上是相邻的。
设a1的起始地址为S，每个元素占M个存储单元（字节），则第i个元素的起始存储位置为 loc(ai)=loc(a1)+(i-1)m 存储地址 内存 数据元素位置编号 S a1 1 S+m a2 2 S+2m a3 3 S+(n-1)m an n

6 数据的存储结构 链式存储（指针） 头指针 201 存储地址 数据域 指针域 201 a1 601 216 a2 462 a3 nil a4
807 a5 头指针H a1 a4 a5 a2 a3 nil

7 栈 先进后出表（FILO）或下推表 假设栈的最大长度为m，所有结点都具有同一类型stype，则定义栈如下： Const m=栈的最大长度;
Type stack=array[1..m] of stype; {栈类型} Var s:stack; {栈} t:integer; {栈顶指针} xx:stype; 栈的基本运算： 入栈 push 出栈 pop 读取栈顶元素 top

8 入栈 push(s,x,t) 过程push(s,x,t)往栈S中压入一个值为X的结点。
Procedure push(var s:stack; x:stype; var t:integer;); Begin if t=m then writeln(‘full!’) else begin t:=t+1; s[t]:=x; end; End;

9 出栈 pop(s,t) 函数pop(s,t)从栈s中弹出一个结点。
Function pop(var s:stack; var t:integer;):stype; Begin if t=0 then writeln(‘empty!’) else begin pop:=s[t]; t:=t-1; end; End; Procedure pop(var s:stack; var t:integer); Begin if t=0 then writeln(‘empty!’) else begin xx:=s[t];

10 读取栈顶元素 top(s,t) 函数top(s,t)读栈顶元素。
Function top(s:stack; t:integer;):stype; Begin if t=0 then writeln(‘empty!) else top:=s[t]; End;

11 栈的应用 计算表达式的值 非递归的回溯法

12 计算表达式的值 输入一个表达式，该表达式含+、-、*、/、(、)和操作数，所含字符数不超过255，以@结束，输出该表达式的值。
分析：字符串输入，不能进行数值计算，所以，需要将输入的中缀表达式转换成后缀表达式。 输入字符串：e 后缀表达式：a 存放运算符的栈：s

13 计算表达式的值 当e[i]为： 数字： e[i]压入a； （： e[i]压入s； ）： 将s中栈顶至（间的所有运算符出栈进入a，丢弃（；
+、-： 将s中栈顶至（间的所有运算符出栈进入a， e[i]进入s； *、/： 将s中栈顶至（前的第一个+或-前的所有运算符出栈进入a，e[i]压入s； 例e：5 * * ( 5 * 2 / 3 – 4 ) + 7 则a：5 8 * * 3 / 4 - * + 7 +

14 队列 a b c b c b c d 一个队列 f r 删除一个元素 f r 插入一个元素 f r 先进先出表（FIFO）

15 Pascal语言 C语言定义队列 定义队列： 定义队列： Const m=队列元素的上限; Const int MAXN=50;
Type equeue=array[1..m] of int; Var q:equeue; r,f:integer; 初始：f=r=0 队满：r=m 队空：f=r 队列的主要运算： 入队（ADD） 出队（DEL） 定义队列： Const int MAXN=50; int queue[MAXN]; int r,f:integer; 初始：f=r=-1 队满：r=maxn-1 队空：f=r 队列的主要运算： 入队（ADD） 出队（DEL）

16 Pascal C入队add 过程ADD（x,r）在队列q的尾端插入元素x 过程ADD（x,r）在队列q的尾端插入元素x
Procedure ADD(x:qtype; var r:integer;); Begin if r=m then writeln(‘full!’) else begin r:=r+1; q[r]:=x; end; End; 过程ADD（x,r）在队列q的尾端插入元素x void ADD( int x; int r); { if (r==m) printf(“队列已经满了！”)； else begin r:=r+1; q[r]:=x; }

17 Pascal C语言出队 DEL（y,f） 过程DEL（y,f）取出q队列的队首元素y 过程DEL（y,f）取出q队列的队首元素y
Procedure DEL(var y:qtype; var f:integer;); Begin if f=r then writeln(‘empty’) else begin f:=f+1; y:=q[f]; end; End; 过程DEL（y,f）取出q队列的队首元素y void DEL( int y; int f); { if (f==r) printf(“队列已经为空”)； else { f:=f+1;y=q[f];} }

18 假溢出 随着队列一端插入，一端删除，队列在数组中不断向队尾方向移动，而在队首产生一片不以利用的空闲存储区，最后会导致当r=m时，不能再加入元素，形成假溢出。 m 3 2 1 m 3 2 1 m 3 2 1 r m 3 2 1 r f r f f f r 初始 加入3个元素 删除3个元素 加入m-3个元素，队满 f=r= f=0 r= f=r= r=m f=3

19 循环队列 f r 初始：f=r=m 入队：r:=r+1; r:=r mod m +1 A[m] if r=m+1 then r:=1;
出队：f:=f+1; f:=f mod m +1 if f=m+1 then f:=1; 队空：f=r; 队满：f=r mod m+1; m A[m] A[m-1] A[m+1] m-1 f 3 2 r 1

20 卡片游戏 桌上有一叠牌，从第一张牌（即位于顶面的牌）开始从上往下依次编号为1~n。当至少还剩两张牌时进行以下操作：把第一张牌扔掉，然后把新的第一张放到整叠牌的最后，输入n,输出每次扔掉的牌，以及最后剩下的牌。 样例输入：7 样例输出：

21 铁轨 某城市有一个火车站，铁轨铺设如图6-1所示。有n节车厢从A方向驶入车站，按进站顺序编号为1~n。你的任务是让它们按照某种特定的顺序进入B方向的铁轨并驶出车站。为了重组车厢，你可以借助中转站C。这是一个可以停放任意多节车厢的车站，但由于末端封顶，驶入C的车厢必须按照相反的顺序驶出C。对于每个车厢，一旦从A移入C，就不能再回到A了；一旦从C移入B,就不能回到C了。换句话说，在任意时刻，只有两种选择：A->C和C->B。

22 树 树的递归定义： 有且仅有一个结点没有前驱（父结点），该结点为树的根 除根外，其余所有结点有且仅有一个前驱
除根外，每一个结点都通过唯一的路径连到根上 根结点 第一层 r a b c e f g h i j k 分支结点 第二层 第三层 叶结点 第四层

23 树 结点的度=该结点的子树树目 树的度=max(所有结点的度) 树的深度（高度）=树中最大的层次 森林：若干棵互不相交的树的集合
有序树和无序树

24 树的表示方法 自然界的树形表示法：用结点和边表示树
括号表示法：先将根结点放入一对（）中，然后把它的子树按由左而右的顺序放入（）中，而对子树也采用同样方法处理：同层子树放入它们根结点后面的（）中，同层子树之间用逗号隔开： (r(a(e,f(j)),b(g),c(h(k),i)))

25 树的存储结构 静态记录数组 所有结点存储在一个数组中，数组元素为记录类型，包括数据域和长度为n（n为树的度）的数组，分别存储该结点的每一个儿子的下标。 Const n=树的度； max=结点数的上限； Type node=record data:datatype; ch:array[1..n]of integer; end; treetype=array[1..max] of node; Var tree:treetype; define n=树的度； define max=结点数的上限； struct node { int data; int d[n]; } struct node a[max];

26 二叉树 二叉树的递归定义 二叉树是以结点为元素的有限集，它或者为空，或者满足以下条件： 有一个特定的结点称为根；
余下的结点分为互不相交的子集L和R，其中R是根的右子树，L是根的左子树，L和R又是一棵二叉树。 二叉树和树是两个不同的概念： 树的每个结点可以有任意多个后继，而二叉树中每个结点的后继不能超过2； 树的子树可以不分次序（有序树除外），而二叉树的子树有左右之分。

27 二叉树的形态 二叉树的五种基本形态 a 空二叉树 b 只有一个结点的二叉树 c 只有左子树的二叉树
d 只有右子树的二叉树 e 左、右子树均有的二叉树

28 二叉树的两个特殊形态 满二叉树：一棵深度为K且有2K-1个结点的二叉树称为满二叉树
完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树。

29 二叉树的存储结构 顺序存储结构 顺序存储结构 Const m=树中结点数上限; define m=树中结点数上限;
Type node=record data:datatype; prt,lch,rch:0..m; end; Treetype=array[1.m]of node; Var tree:treetype; 顺序存储结构 define m=树中结点数上限; struct node{ int data; int p[3]; } struct node a[m];

30 二叉树的遍历 前序：abdheicfjkgl 中序：dhbeiajkfclg 后序：hdiebkjflgca a b c d e h i f

31 前序遍历 二叉链表 二叉树的顺序存储结构 Procedure preorder(bt:bitreptr);
Begin if bt<>nil then begin 访问处理bt^.data; preorder(bt^.lch); preorder(bt^.rch); end; End; 二叉树的顺序存储结构 Procedure preorder(i:integer;); Begin if i<>0 then begin 访问处理tree[i].data; preorder(tree[i].lch); preorder(tree[i].rch); end; End;

32 中序遍历 二叉链表 Procedure inorder(bt:bitreptr); Begin if bt<>nil then
inorder(bt^.lch); 访问处理bt^.data; inorder(bt^.rch); end; End; 二叉树的顺序存储结构 Procedure inorder(i:integer;); Begin if i<>0 then begin inorder(tree[i].lch); 访问处理tree[i].data; inorder(tree[i].rch); end; End;

33 后序遍历 二叉链表 Procedure postorder(bt:bitreptr);
Begin if bt<>nil then begin postorder(bt^.lch); postorder(bt^.rch); 访问处理bt^.data; end; End; 二叉树的顺序存储结构 Procedure inorder(i:integer;); Begin if i<>0 then begin inorder(tree[i].lch); inorder(tree[i].rch); 访问处理tree[i].data; end; End;

34 普通有序树的遍历 普通树转换成二叉树 长子变左儿子 兄弟变右儿子 r a x w b f c s t u d e i j h m o n r

35 森林的遍历 森林转换成二叉树 r a b c s d t e f g r a b c t e f g s d r a b c s d t e

36 由中序和后序确定前序 中序和后序确定前序 中序：s’=s1’……sk’……sn’ 后序：s’’=s1’’…………sn’’
显然， sn’’为根，在前序中直接输出，设在中序中与sn’’相同的字符为sk’ 若k>1，则左子树存在， s1’……sk-1’为左子树的中序遍历，s1’’……sk-1’’为左子树的后序遍历 若k<n，则右子树存在， sk+1’……sn’为右子树的中序遍历，sk’’……sn-1’’为右子树的后序遍历

37 由中序和后序确定前序 Procedure solve1(s1,s2:string); Var k:integer;
Begin if length(s2)=1 then write(s2) {递归出口} else begin k:=pos(s2[length(s2)],s1); write(s1[k]); if k>1 then solve1(copy(s1,1,k-1),copy(s2,1,k-1)); if k<length(s1) then solve1(copy(s1,k+1,length(s1)-k),copy(s2,k,length(s2)-k)); end; End;

38 由中序和前序确定后序 Procedure solve2(s1,s2:string); Var k:integer;
Begin if length(s2)=1 then write(s2) else begin k:=pos(s2[1],s1); if k>1 then solve2(copy(s1,1,k1),copy(s2,2,k)); if k<length(s1) then solve2(copy(s1,k+1,length(s1)-k), copy(s2,k+1,length(s2)-k)); end; End;

39 二叉树的应用 二叉排序树 最优二叉树

40 二叉排序树 二叉排序树是具有以下性质的非空二叉树： 若根的左子树不空，则左子树的所有结点值均小于根结点值；
若根的右子树不空，则右子树的所有结点值均不小于根结点值； 根结点的左、右子树也分别为二叉排序树。 例：输入序列a1,a2……an（1<=n<=1000），将a按照递增顺序排列后输出。 构造二叉排序树的方法： 令a1为二叉树的根； 若a2<a1，则令a2为a1左子树的根结点，否则令a2为a1右子树的根结点； 对a3，a4……an递归重复②。

41 构造二叉排序树 例：a序列为： 35 30 40 32 37 90 33 82 中序遍历：

42 构造二叉排序树 procedure createtree; begin fillchar(b,sizeof(b),0);
b[1].data:=a[1]; for i:=2 to n do begin b[i].data:=a[i]; p:=1; while true do if a[i]<b[p].data then if b[p].l<>0 then p:=b[p].l else begin b[p].l:=i; break; end else if b[p].r<>0 then p:=b[p].r else begin b[p].r:=i; break; end; end; end; 稳定的

43 构造二叉排序树 主程序 Begin readln(n); for i:=1 to n do read(a[i]); writeln;
createtree; inorder(1); End.

44 最优二叉树 最优二叉树（哈夫曼树、最优搜索树） 例：计算最优的判定过程
全校学生的成绩由百分制转换成五等分制，在五个等级上分布不均匀，颁布规律如下： 百分制分数范围 0~ ~ ~ ~ ~100 分布情况% 现有10000个数据，以下两种判定转化过程： <60 不及格 <70 及格 <80 中 <90 良 优 <80 < <90 < 中 良 优 不及格 及格 K1=10000*(1*5%+2*15%+3*40%+4*(30%+10%))=31500 K2=10000*(2*(40%+30%+10%)+3*(5%+15%))=22000

45 最优二叉树 结点的路径长度：从根到每个结点的路径长度 叶结点的权值：叶结点被赋予的实数值
设Wk为第k个结点的权值，Pk为第k个叶结点的带权路径长度。 L=W1*P1+W2*P2……Wn*Pn 则使L最小的树称为最优二叉树。

46 构造最优二叉树 构造方法： 将给定的N个结点构成N棵二叉树的集合F，其中每棵二叉树Ti中只有一个权值为Wi的根结点Ki，其左右、子树均为空；
在F中删除这两棵二叉树，同时将新得到的二叉树加入F中； 重复②③，直到在F中只含有一棵二叉树为止。 24 24 A B C D E 7 5 2 4 6 A E 7 6 13 B 5 11 11 13 C D 2 4 6 6 A B E 7 5 A E 7 6 11

47 最优二叉树 最优二叉树中非叶子结点的度均为2 如果叶结点数为N，则总结点数为2*N-1 Const n=叶结点的上限; m=2*n-1;
Type node=record data:integer; prt,lch,rch,lth:0..m; end; wtype=array[1..n] of integer; treetype=array[1..m] of node; {tree[1..n]为叶子结点， tree[n+1..2*n-2]为分支结点，tree[2*n-1]为根} Var tree:treetype;

48 构造最优二叉树 Procedure hufm(w:wtype;var tree; var bt:integer);
function min(h:integer):integer; begin m1:=maxint; for p:=1 to h do if (tree[p].prt=0) and (m1>tree[p].data) then begin i:=p; m1:= tree[p].data; end; min:=i; end; Begin fillchar(tree,sizeof(tree),0); for i:=1 to n do read(tree[i].data); for k:=n+1 to m do begin i:=min(k-1); tree[i].prt:=k; tree[k].lch:=i; j:=min(k-1); tree[j].prt:=k; tree[k].rch:=j; tree[k].data:=tree[i].data+tree[j].data; bt:=m; End;

49 求最优判断 Procedure ht(t:integer); {通过前序遍历计算每个叶子的路径长度}
Begin if t=m then tree[t].lth:=0 else tree[t].lth:=tree[tree[t].prt].lth+1 if tree[t].lth<>0 then begin ht(tree[t].lch); ht(tree[t].rch); end; End; BEGIN readln(n); for i:=1 to 5 do readln(w[i]); hufm(w,tree,bt); ht(bt); writlen(m*tree[bt].data); for i:=1 to 5 do write(n*tree[i].lth*tree[i].data:0:0); END.

50 图 图是较线性表和树更为复杂的一种数据结构，在这种数据结构中，数据结点间的联系是任意的，因此它可以更广泛地表示数据元素之间的关系。
线性表和树是图的特例。

51 图的基本概念 图的定义 如果数据元素集合D中的各元素之间存在任意的前驱中后继关系R，则此数据结构G=（D，R）称为图。
如果将数据元素抽象成顶点，元素之间的前驱或后继关系用边表示，则图亦可以表示为G=（V，E），其中V是顶点的有限（非空）集合，E是边的集合，如果元素Vi是元素Vj的前驱，则用(Vi, Vj)表示它们之间的边。 v1 v1 v2 v3 v2 v4 v4 v5 v3

52 无向图和有向图 无向图 在图G=（V，E）中，如果对于任意的Vi,Vj∈V，当(Vi,Vj) ∈ E时，必有(Vj,Vi) ∈ E，则称此图为无向图（如：图2）。 在一个具有n个顶点的无向图中，边的最大数目为n(n-1)/2，此时的图称为无向完全图（如：图3）。 在无向图中，与一个顶点相连的边数为该顶点的度。 v1 v3 v5 v2 v4 图2 v1 v3 v5 v2 v4 图3

53 无向图和有向图 有向图 在图G=（V，E）中，如果对于任意的Vi,Vj∈V，当(Vi,Vj) ∈ E时， (Vj,Vi) ∈ E未必成立，则称此图为有向图（如：图4）。 顶点的出度：该顶点后继的个数 顶点的入度：该顶点前驱的个数 顶点的度=出度+入度 图的度=MAX（所有结点的度） v1 v2 v3 v4 图4

54 路径和连通集 在图G=（V，E）中，如果对于顶点Vi,Vj，存在满足下述条件的结点序列X1,X2……Xk(k>1)
X1=Vi,Xk=Vj (Xi,Xi+1) ∈E i=1,2,……,k-1 则称结点序列X1=Vi,X2,……,Xk=Vj为顶点Vi到顶点Vj的一条路径，而路径上的边的数目k-1称为该路径的长度，并称顶点集合{X1,…..,Xk}为连通集。

55 简单路径和回路 如果一条路径上的顶点除起点X1和终点Xk可以相同外，其他顶点均不相同，则称此路径为一条简单路径。
如：图2中 是一条简单路径，而 不是。 X1= Xk的简单路径称为回路（也称为环）。 如：图4中 为一条回路。 v1 v3 v5 v2 v4 图2 v1 v2 v3 v4 图4

56 有根图 在一个图中，若存在一个顶点w，它与其他顶点都是连通的，则称此图为有根图，顶点w即为它的根。
图5为有根图， 都可以作为根； 图6为有根图，1或2为它的根。 1 2 3 图6 1 2 4 3 图5

57 连通图和最大连通子图 对于无向图而言，若其中任两个顶点之间是连通的，则称该图为连通图。 一个无向图的连通分支定义为此图的最大连通子图。
图2是连通的，它的最大连通子图即为本身。 v1 v3 v5 v2 v4 图2

58 强连通图和强连通分支 对于有向图的任意两个顶点Vi、Vj间(Vi<>Vj )，都有一条从Vi到Vj的有向路径，同时还有一条从Vj到Vi的有向路径，则称该有向图是强连通图。 有向图中强连通的最大子图称为该图的强连通分支。 图6不是强连通的，它含有两个强连通分支，如图7。 1 2 3 图6 1 2 3 图7

59 零图和平凡图 在一个图中不与任何顶点相邻接的顶点称为孤立顶点。 如：图7中的3 仅由孤立顶点组成的图称为零图。
仅由一个孤立顶点组成的图称为平凡图。 1 2 3 图7

60 图的存储结构 相邻矩阵表示法， 若G=（V，E）是一个具有N个顶点的图，则G的相邻矩阵是如下定义的二维数组A，其规模为N*N
1(或权) (Vi,Vj) ∈E 0(或±∞) (Vi,Vj) ∈E A[I,j]= v1 v2 v3 v4 v5 3 5 4 2 10 11 6 8 图8 v1 v2 v5 v4 v3 图9 A1= A2=

61 相邻矩阵的特点 Type maxn=顶点数的上限; Var a:array[1..n,1..n] of integer;
f:array[1..maxn] of boolen; 无向图的相邻矩阵是对称的，而有向图不是。占用的存储单元数只与顶点数有关而与边数无关。 相邻矩阵方便度数的计算。 容易计算路径的存在性。 在无权有向图或无向图中，判定Vi,Vj两个顶点之间否存在长度为m的路径，只要考虑am=a*a*a*……*a(m个a矩阵相乘后的乘积矩阵)中(i,j)的元素值是否为0就行了。

62 图的邻接表示法 用邻接表法表示图需要保存一个顺序存储的顶点表和n个边表（每个边表为一个单链表，存储与一个顶点相连的所有边的信息）。
顶点表的每个表目对应于图的一个顶点，包括 顶点信息，即： 与该顶点相连的边数m； 访问标志visited 边表的首指针firstarc。图中每个顶点都有一个边表，基中每一个顶点对应于与该顶点相关联的一条边，包括： 与此边相关联的另一个顶点序号v； 若为带权图的话，该边的权值w； 指向边表的下一个顶点的后继指针nextarc.

63 图的邻接表示法 Const max=图的顶点数的上限; Type arcptr=^arcnode; {边表的指针类型}
arcnode=record {边表的顶点类型} v:integer; {关联该边的另一顶点序号} nestar:arcptr; {边表的后继指针} w:real; {边的权值} end; vexnode=record {顶点表的表目类型} m:integer; {与该顶点相连的边数} visited:boolean; {访问标志} firstarc:arcptr; {边表的首指针} adjlist=array[1..max] of vexnode; {邻接表类型} Var dig:adjlist; {邻接表} n,e:integer; {顶点数和边数}

64 图的邻接表示法 v1 v2 v5 v4 v3 1 2 5 7 6 4 3 图10 m visited frstarc 1 false 2 3
w nestarc 2 nil 5 4 7 1 3 6 v w nestarc 1 nil 2 5

65 图的邻接表示法 读n,e; For i:=1 to n do begin with dig[i] do begin m:=0;
firstarc:=nil; visited:=false; end; For i:=1 to e do begin 读第i条边关联的顶点序号j，k和该边的权Wjk; dig[j].m:=dig[j].m+1; new(q); with q^ do begin v:=k; w:=w[j,k]; nestarc:=dig[j].firstarc; end; dig[j].firstarc:=q;

66 图的遍历 深度优先搜索dfs 广度优先搜索bfs

67 深度优先搜索dfs 从某个顶点V0出发，访问此顶点。然后依次从V0的未被访问的邻接点出发深度优先遍历图，直至图中所有和V0有路径相连的顶点都被访问到。若此时图中尚有顶点未被访问，则另选一个未曾访问的顶点作为起始点，重复上述过程，直到图中所有顶点都被访问为止。 从V1出发，dfs图8的结果是：V1 V2 V3 V4 V5 从V3出发，dfs图10的结果是：V3 V2 V1 V5 V4 从V1出发，dfs图10的结果是：V1 V2 V5 V4 V3 v1 v2 v5 v4 v3 1 2 5 7 6 4 3 图10 v1 v2 v3 v4 v5 3 5 4 2 10 11 6 8 图8

68 深度优先搜索dfs 相邻矩阵： Procedure dfs(i:integer); Begin 访问处理结点i; f[i]:=true;
for j:=1 to n do if (not f[j]) and (a[i,j]=1) then dfs(j); End; Procedure traver1; Begin fillchar(f,sizeof(f),0); for i:=1 to n do {深度优先搜索每一个未访问的顶点} if not f[i] then dfs(i); 调用一次dfs(i)，可按深度优先搜索的顺序访问处理顶点i所在的连通分支（强连通分支）

69 广度优先搜索bfs 假设从图中某顶点V0出发，在访问了V0之后依次访问V0的各个未曾访问的邻接点，然后分别从这些邻接点出发按广度优先搜索的顺序遍历图，直至图中所有可被访问的顶点都被访问过。 从V1出发，bfs图8：V1 V2 V3 V4 V5 v1 v2 v3 v4 v5 3 5 4 2 10 11 6 8 图8

70 广度优先搜索bfs v1 v1 v2 v3 v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 3 5 4 2 10 11 6 8
队列 f r v1 v2 v3 v4 v5 3 5 4 2 10 11 6 8 图8 队列 v1 f r v1 队列 f r 队列 v2 v3 v4 f r v1 v2 v3 队列 v3 v4 f r 队列 v3 v4 v5 f r v1 v2 v3 v4 v5 队列 v3 v4 v5 f r

71 广度优先搜索bfs Procedure bfs(i:integer); Begin 访问处理结点i; f[i]:=true;
r:=r+1; q[r]:=i; {结点i进入队列q} while r<>front do begin front:=front+1; {从队列中移出队首元素} for j:=1 to n do if (not f[j]) and (a[q[front],j]=1) then begin 访问顶点j; f[j]:=true; r:=r+1; q[r]:=j; {结点j进入队列q} end; End;

72 广度优先搜索bfs Procedure traver2; Begin fillchar(f,sizeof(f),0);
for i:=1 to n do if (not f[j]) then bfs(i); End;

73 图的生成树 若图是连通的无向图或强连通的有向图，则从其中任一个顶点出发，调用一次dfs或bfs后便可以系统地访问图中所有顶点；
在这种情况下，图中的所有顶点加上遍历过程中经过的边所构成子图称作图的生成树。 v1 v2 v3 v4 v5 3 5 4 2 10 11 6 8 图8 v1 v2 v3 v4 v5 图8的广度优先搜索树 v1 v2 v5 v4 v3 图9 v3 v2 v4 v1 v5 图9的深度优先搜索树

74 图的最小生成树 现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为公路造价。在分析了这张地图后可以发现，任一对城市都是连通的。现在的问题是，要用公路把所有的城市都联系起来，如何设计可使工程总造价最少。 输入： n（城市数，1<=n<=20) e(有向边数，1<=e<=210) 以下e行，每行为边(I,j)和该边的距离Wij(1<=i<=n, 1<=j<=n) 输出： n-1行，每行为两个城市的序号，表明这两个城市间建一条公共汽车线路。

75 图的最小生成树 在一张有权连通图中，如何寻找一棵各边权的总和为最小的生成树，就是本章节所要讨论的问题。
计算最小生成树的思维方向：为了保证边权总和最小，必须保证 ①、添加(u,v)不能够形成回路； ②、在保证１的前提下添加权尽可能小的 这样的边称之为安全边。 计算最小生成树的步骤：有两种算法可计算图的最小生成树 Kruskal算法 Prim算法

76 Kruskal算法 对给定图的所有边从小到大排序，依次试探将边和它的端点加入生成树，如果加入的边不产生环，则继续将边和它的端点加入，否则，将它删去，直到生成树中含有n-1条边。

77 Kruskal算法 Const maxn=210; maxe=maxn*maxn; {顶点数和边数的上限} Type
edgetype=Record {边的类型} x,y,c:longint; {边权为c的边（x，y）} End; Var e:Array [1..maxe] of edgetype; {边集，其中第i条边为(e[i].x,e[i].y)，该边的权为e[i].c} n,m,ans:longint; {顶点数为n，边数为m} f:Array [1..maxn] of longint; {并查集，其中f[i]为顶点i所在并查集的代表顶点，即子树根}

78 Kruskal算法 通过函数top(i)计算顶点i所在子树的根
Function top(i:longint):longint; {计算和返回顶点i所在并查集的代表顶点} Begin if i<>f[i] Then f[i]←top(f[i]); {若i非所在并查集的代表顶点，则沿f[i]递归} top←f[i]; {返回顶点i所在并查集的代表顶点} End;

79 Kruskal算法 通过过程Union(i,j,c)合并顶点i和顶点j所在的两棵树
现有边权为c的边（i，j）。若该边的两个端点分属于两棵树，顶点i和顶点j所在子树的根分别为x和y，则(i,j) 加入最小生成树，合并两棵树（即顶点i和顶点j所在的并查集）。 Procedure Union(i,j,c:longint); {合并i和j所在集合} Var x,y:longint; Begin x←top(i); y←top(j); {分别取出顶点i和顶点j所在子树的根} if x<>y Then Begin inc(ans,c); f[y]←x; End; {若i和j分属于两棵子树，则该边权计入最小生成树的权和，两棵子树合并} End;

80 Kruskal算法 BEGIN 按照边权值（c域值）递增的顺序排序边集e； For i←1 to n do
f[i]←i; {建立由n棵树组成的森林，每棵树包含图的一个顶点} ans←0; { 最小生成树的权和初始化为0} For i←1 to m do union(e[i].x,e[i].y,e[i].c); {枚举每条边，将两个端点分属两棵树的边加入最小生成树} writeln(ans); END.

81 Prim算法 任取一个顶点加入生成树，然后对那些一个端点在生成树中，另一个端点不在生成树中的边进行排序，取权值最小的边，将它和另外一个端点加进生成树中。重复上述步骤直到所有顶点都进入了生成树为止。

82 Prim算法 d[i]—顶点i与生成树相连的最短边长； ba[i]—顶点i在生成树的标志；
w[i,j]—（i,j）的边长。若图中不存在边（i,j），则w[i,j]=∞ min—所有未在生成树的顶点的最小距离值

83 Prim算法 fillchar(ba，sizeof(ba)，0)； {所有顶点未在生成树}
for i：=2 to n do d[i]：=∞； {所有顶点的距离值初始化} d[1]：=0 ；ans：=0； {顶点1的距离值和生成树的权和初始化} for i：=1 to n do {依次范围每个顶点} Begin min：=∞； {在所有未在生成树、且距离值最小（min）的顶点k} for j：=1 to n do if (not ba[j]) and (d[j]<min) then begin k：=j；min：=d[j]；end； if min=∞ then begin ans：=-1；break；end；{若这样的顶点不存在，则无解退出} ans：=ans+min；ba[k]：=true；{最小距离值min计入生成树的权和,顶点k进入生成树} for j：=1 to n do {调整与k相连的各顶点的距离值} begin min：=w[k，j]；if min<d[j] then d[j]：=min； end；{for} End；{for} writeln(ans：0：3)； {输出最小生成树的权和}

84 Kruskal与Prim的比较 共同点：贪心，选择边权最小的安全边；

85 单源最短路径 现有一张县城地图，图中的顶点为城镇，无向边代表两个城镇间的连通关系，边上的权为公路造价，县城所在的城镇为V0。由于该县经济比较落后，因此公路建设只能从县城开始规划。规划的要求是所有可到达县城的城镇必须建设一条通往县城的汽车线路，该线路的工程总造价必须最少。 输入：n（城镇数，1<=n<=20） 县城所在的城镇序号V0 e（有向边数，1<=e<=210） 以下e行，每行为3个整数，两个城镇的序号和它们间的公路造价。 输出：k行，每行为一条通往县城的汽车线路的总造价和该条线路途径的 城镇序号。

86 单源最短路径（ Dijkstra算法） 单源最短路径：设=(V,E)是一个有向图，它的每一条边(u,v) ∈E都有一个权W(u,v)，在G中指定一个顶点V0，要求把从V0到G的每一个顶点Vj(Vj ∈E)的最短有向路找出来（或者指出不存在从V0到Vj的有向路，即V0到Vj不可达）。这个问题即为单源最短路径。 Dijkstra算法： 把图中所有结点分为两组，每一个结点对应一个距离值： 第一组：包括已确定最短路径的结点，结点对应的距离值是由 v0到此结点的最短路径长度； 第二组：包括尚未确定最短路径的结点，结点对应的距离值是v0经由第一组结点（中间结点）至此结点的最短路径长度； 我们按最短路径长度递增的顺序把第二组的结点加到第一组中去，直至v0可达的所有结点都包含于第一组。在这个过程中，总保持从v0到第一组各结点的最短路径长度都不大于从v0至第二组任何结点的路径长度。

87 单源最短路径（ Dijkstra算法） 初始时v0进入第一组，v0的距离值为0；第二组包含其它所有结点，这些结点对应的距离值这样确定（设vi为第二组中的结点） 然后每次从第二组的结点中选一个其距离值为最小的结点vm加到第一组中。每往第一组加入一个结点vm，就要对第二组的各结点的距离值作一次修正（设vi为第二组的结点, （vm，vi）为图中的边）： 若加进vm做中间结点使得v0至vi的路径长度更短（即vi的距离值>vm的距离值+Wmi），则要修改vi的距离（vi的距离值←vm的距离值+Wmi）。修改后再选距离值最小的一个结点加入到第一组中，…。如此进行下去，直至第一组囊括图的所有结点或再无可加入第一组的结点存在。显然，这种从第二组的结点中选距离值最小的结点扩展是一种贪心策略。

88 圆内的数字为距离值。绿色的结点为第一组的结点，灰色的结点为第二组的结点
单源最短路径（ Dijkstra算法） 圆内的数字为距离值。绿色的结点为第一组的结点，灰色的结点为第二组的结点 9 14 ∞ 13 9 8 10 8 5 5 7 7 ∞

89 用一维数组来实现优先队列。设 n—图的结点数； adj—有向图的相邻矩阵。其中 dist—最短路径集合。其中 dist[i]．pre—在v0至vi的最短路径上，vi的前趋结点序号； dist[i]．length—v0至vi的最短路径长度，即vi的距离值；(1≤i≤n) Const n=图的结点数； Type path=record {路径集合的结点类型} length：real； {距离值} pre：0‥n； {前趋结点序号} end； var adj：array[1‥n，1‥n] of real {相邻矩阵} dist：array[1‥n] of path； {路径集合}

90 Dijkstra算法 fillchar(adj，sizeof(adj)，0)；{建立相邻矩阵adj} for i←1 to n do
for j←1 to n do if（i，j）∈E then adj[i，j]←wij else adj[i，j]←∞； for i←1 to n do {路径集合初始化} begin dist[i]．length←adj[v0，i]； if dist[i]．length<>∞ then dist[i]．pre←v0 else dist[i]．pre←0； end；{for} adj[v0，v0]←1；{源结点v0进入第一组}　　

91 Dijkstra算法 repeat min←∞；u←0； for i←1 to n do {从第二组中找距离值最小的结点u}
if (adj[i，i]=0)and(dist[i]．length<min) then begin u←i；min←dist[i]．length；end；{then} if u<> {第二组中存在一个距离值最小的结点} then begin adj[u，u]←1； {结点u进入第一组} for i←1 to n do {修正第二组中u可达的结点距离值} if(adj[i，i]=0)and(dist[i]．length>dist[u]．length+adj[u，i]) dist[i]．length←dist[u]．length+adj[u，i]； dist[i]．pre←u； end；{then} until u=0； 　　　　　　

92 Dijkstra算法 算法结束时，沿着结点vi的pre指针回溯，便可确定v0至vi的最短路径：
procedure print(i：integer)； Begin if i=v0 then 输出结点v0 else begin print(dist[i]．pre)； 输出结点i和v0至vi的最短路径长度dist[i]．length； end；{else} End；{print} 显然递归调用print[1]，…，print[n]后，可得知v0至所有结点的最短路径。

93 v0 v1 v2 v3 v4 4 3 6 29