数据结构(2).ppt

《数据结构(2).ppt》由会员分享，可在线阅读，更多相关《数据结构(2).ppt（93页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据结构数据结构数据结构的概念学号姓名性别 民族 语文数学英语总分101张华男汉91126120102郝博男汉113130117103王静女回9711492104孟晓立女苗11610885105宋子荣男汉10112296106陈威男汉10599113表：学生档案表：学生档案数据结构的概念数据（data）：凡是能输入到计算机的描述客观事物的符号数据元素（data element）：也叫结点（node）或记录（record），是数据的基本单位。如：表中的一行就是一个数据元素。数据项（data item）：是数据不可分割的最小单位。如：“学号”、”数学“等。数据对象（data object）：指性质

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

3、数据元素之间存在多对多的任意关系。数据的存储结构顺序存储（数组）顺序存储（数组）表中一行（即一个学生信息）抽象成一个结点ai，ai与a(i+1)在存储上是相邻的。设a1的起始地址为S，每个元素占M个存储单元（字节），则第i个元素的起始存储位置为loc(ai)=loc(a1)+(i-1)m存储地址内存数据元素位置编号Sa11S+ma22S+2ma33S+(n-1)mann数据的存储结构链式存储（指针）链式存储（指针）存储地址数据域指针域201a1601216a2462462a3nil601a4807807a5216头指针201头指针Ha1a4a5a2a3nil栈先进后出表（FILO）或下推表假设

4、栈的最大长度为m，所有结点都具有同一类型stype，则定义栈如下：Const m=栈的最大长度;Type stack=array1.m of stype;栈类型Var s:stack;栈 t:integer;栈顶指针 xx:stype;栈的基本运算：入栈 push出栈 pop读取栈顶元素 top入栈 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;st:=x;end

5、;End;出栈 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:=st;t:=t-1;end;End;Procedure pop(var s:stack;var t:integer);Begin if t=0 then writeln(empty!)else begin xx:=st;t:=t-1;end;end;读取栈顶元素 top(s,t)函数top(s,t)读栈顶元素。Function to

6、p(s:stack;t:integer;):stype;Begin if t=0 then writeln(empty!)else top:=st;End;栈的应用计算表达式的值非递归的回溯法计算表达式的值输入一个表达式，该表达式含+、-、*、/、(、)和操作数，所含字符数不超过255，以结束，输出该表达式的值。分析：字符串输入，不能进行数值计算，所以，需要将输入的中缀表达式转换成后缀表达式。输入字符串：e 后缀表达式：a 存放运算符的栈：s当ei为：u数字：ei压入a；u（：ei压入s；u）：将s中栈顶至（间的所有运算符出栈进入a，丢弃（；u+、-：将s中栈顶至（间的所有运算符出栈进入a，e

7、i进入s；u*、/：将s中栈顶至（前的第一个+或-前的所有运算符出栈进入a，ei压入s；u例e：5*8+3*(5*2/3 4)+7u则a：5 8*3 5 2*3/4-*+7+计算表达式的值队列先进先出表（FIFO）插入的一端称为队尾r，删除的一端称为队首frfbc删除一个元素abc一个队列bcd插入一个元素rfrf定义队列：Const m=队列元素的上限;Type equeue=array1.m of qtype;Var q:equeue;r,f:integer;初始：f=r=0队满：r=m队空：f=r队列的主要运算：入队（ADD）出队（DEL）入队ADD（q,x,r）过程ADD（q,x,r）

8、在队列q的尾端插入元素xProcedure ADD(var q:equeue;x:qtype;var r:integer;);Begin if r=m then writeln(full!)else begin r:=r+1;qr:=x;end;End;出队 DEL（q,y,f）过程DEL（q,y,f）取出q队列的队首元素yProcedure DEL(var q:equeue;var y:qtype;var f:integer;);Begin if f=r then writeln(empty)else begin f:=f+1;y:=qf;end;End;假溢出随着队列一端插入，一端删除，队

9、列在数组中不断向队尾方向移动，而在队首产生一片不以利用的空闲存储区，最后会导致当r=m时，不能再加入元素，形成假溢出。m321m321m321m321初始 加入3个元素 删除3个元素 加入m-3个元素，队满f=r=0 f=0 r=3 f=r=3 r=m f=3rfrfrfrf循环队列AmAm-1Am+1123m-1mrfl初始：f=r=ml入队：r:=r+1;r:=r mod m+1 if r=m+1 then r:=1;l出队：f:=f+1;f:=f mod m+1 if f=m+1 then f:=1;l队空：f=r;l队满：f=r mod m+1;树l树的递归定义：有且仅有一个结点没有前

10、驱（父结点），该结点为树的根除根外，其余所有结点有且仅有一个前驱除根外，每一个结点都通过唯一的路径连到根上rabcefghijk第一层第二层第三层第四层根结点分支结点叶结点树结点的度=该结点的子树树目树的度=max(所有结点的度)树的深度（高度）=树中最大的层次森林：若干棵互不相交的树的集合有序树和无序树树的表示方法自然界的树形表示法：用结点和边表示树括号表示法：先将根结点放入一对（）中，然后把它的子树按由左而右的顺序放入（）中，而对子树也采用同样方法处理：同层子树放入它们根结点后面的（）中，同层子树之间用逗号隔开：(r(a(e,f(j),b(g),c(h(k),i)树的存储结构静态记录数组静

11、态记录数组 所有结点存储在一个数组中，数组元素为记录类型，包括数据域和长度为n（n为树的度）的数组，分别存储该结点的每一个儿子的下标。Const n=树的度；max=结点数的上限；Type node=record data:datatype;ch:array1.nof integer;end;treetype=array1.max of node;Var tree:treetype;动态多重链表动态多重链表 每个结点由数据域和n（n为树的度）个指针域共n+1个域组成。const n=树的度;Type treetype=node;node=record data:datatype;next:ar

12、ray1.n of treetype;end;var root:treetype;树的存储结构二叉树l二叉树的递归定义l二叉树是以结点为元素的有限集，它或者为空，或者满足以下条件：有一个特定的结点称为根；余下的结点分为互不相交的子集L和R，其中R是根的左子树，L是根的右子树，L和R又是一棵二叉树。l二叉树和树是两个不同的概念：树的每个结点可以有任意多个后继，而二叉树中每个结点的后继不能超过2；树的子树可以不分次序（有序树除外），而二叉树的子树有左右之分。二叉树的形态二叉树的五种基本形态a 空二叉树 b 只有一个结点的二叉树 c 只有左子树的二叉树d 只有右子树的二叉树 e 左、右子树均有的二叉

13、树二叉树的两个特殊形态l满二叉树：一棵深度为K且有2K-1个结点的二叉树称为满二叉树l完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树。二叉树的存储结构顺序存储结构顺序存储结构Const m=树中结点数上限;Type node=record data:datatype;prt,lch,rch:0.m;end;Treetype=array1.mof node;Var tree:treetype;链式存储结构链式存储结构Type bitrpetr=node;node=record data:datatype

14、;lch,rch:bitrpetr;end;Var bt:bitreptr;二叉树的存储结构二叉树的遍历前序：abdheicfjkgl中序：dhbeiajkfclg后序：hdiebkjflgcaabcdehifgjlk前序遍历中序遍历后序遍历普通有序树的遍历普通树转换成二叉树长子变左儿子兄弟变右儿子raxwbfcstudeijhmonraxwbfcstudeijhmonraxwbfcstudeijhmon森林的遍历森林转换成二叉树rabcsdtefgrabcsdtefgrabctefgsd由中序和后序确定前序中序和后序确定前序中序：s=s1sksn后序：s=s1sn显然，sn为根，在前序中直接

15、输出，设在中序中与sn相同的字符为sk若k1，则左子树存在，s1sk-1为左子树的中序遍历，s1sk-1为左子树的后序遍历若k1 then solve1(copy(s1,1,k-1),copy(s2,1,k-1);if k1 then solve2(copy(s1,1,k1),copy(s2,2,k);if klength(s1)then solve2(copy(s1,k+1,length(s1)-k),copy(s2,k+1,length(s2)-k);end;End;由中序和前序确定后序二叉树的应用二叉排序树最优二叉树二叉排序树二叉排序树是具有以下性质的非空二叉树：若根的左子树不空，则左子

16、树的所有结点值均小于根结点值；若根的右子树不空，则右子树的所有结点值均不小于根结点值；根结点的左、右子树也分别为二叉排序树。例：输入序列a1,a2an（1=n=1000），将a按照递增顺序排列后输出。构造二叉排序树的方法：令a1为二叉树的根；若a2a1，则令a2为a1左子树的根结点，否则令a2为a1右子树的根结点；对a3，a4an递归重复。构造二叉排序树例：a序列为：35 40 30 90 82 32 33 373540309082323337中序遍历：30 32 33 35 37 40 82 90构造二叉排序树procedure createtree;begin fillchar(b,siz

17、eof(b),0);b1.data:=a1;for i:=2 to n do begin bi.data:=ai;p:=1;while true do if aibp.data then if bp.l0 then p:=bp.l else begin bp.l:=i;break;end else if bp.r0 then p:=bp.r else begin bp.r:=i;break;end;end;end;稳定的构造二叉排序树主程序Begin readln(n);for i:=1 to n do read(ai);writeln;createtree;inorder(1);End.最优

18、二叉树最优二叉树（哈夫曼树、最优搜索树）最优二叉树（哈夫曼树、最优搜索树）例：计算最优的判定过程全校学生的成绩由百分制转换成五等分制，在五个等级上分布不均匀，颁布规律如下：百分制分数范围 059 6069 7079 8089 90100 分布情况%5 15 40 30 10现有10000个数据，以下两种判定转化过程：60不及格 70及格 80中 90良 优8070 90treep.data)then begin i:=p;m1:=treep.data;end;min:=i;end;Begin fillchar(tree,sizeof(tree),0);for i:=1 to n do read

19、(treei.data);for k:=n+1 to m do begin i:=min(k-1);treei.prt:=k;treek.lch:=i;j:=min(k-1);treej.prt:=k;treek.rch:=j;treek.data:=treei.data+treej.data;end;bt:=m;End;求最优判断Procedure ht(t:integer);通过前序遍历计算每个叶子的路径长度Begin if t=m then treet.lth:=0 else treet.lth:=treetreet.prt.lth+1 if treet.lth0 then begin

20、ht(treet.lch);ht(treet.rch);end;End;BEGIN readln(n);for i:=1 to 5 do readln(wi);hufm(w,tree,bt);ht(bt);writlen(m*treebt.data);for i:=1 to 5 do write(n*treei.lth*treei.data:0:0);END.图图是较线性表和树更为复杂的一种数据结构，在这种数据结构中，数据结点间的联系是任意的，因此它可以更广泛地表示数据元素之间的关系。线性表和树是图的特例。图的基本概念图的定义如果数据元素集合D中的各元素之间存在任意的前驱中后继关系R，则此数据

21、结构G=（D，R）称为图。如果将数据元素抽象成顶点，元素之间的前驱或后继关系用边表示，则图亦可以表示为G=（V，E），其中V是顶点的有限（非空）集合，E是边的集合，如果元素Vi是元素Vj的前驱，则用(Vi,Vj)表示它们之间的边。v1v3v5v2v4v1v2v3v4无向图和有向图无向图无向图在图G=（V，E）中，如果对于任意的Vi,VjV，当(Vi,Vj)E时，必有(Vj,Vi)E，则称此图为无向图（如：图2）。在一个具有n个顶点的无向图中，边的最大数目为n(n-1)/2，此时的图称为无向完全图（如：图3）。在无向图中，与一个顶点相连的边数为该顶点的度。v1v3v5v2v4图2v1v3v5v2

22、v4图3无向图和有向图有向图有向图在图G=（V，E）中，如果对于任意的Vi,VjV，当(Vi,Vj)E时，(Vj,Vi)E未必成立，则称此图为有向图（如：图4）。顶点的出度：该顶点后继的个数顶点的入度：该顶点前驱的个数顶点的度=出度+入度图的度=MAX（所有结点的度）v1v2v3v4图4路径和连通集在图G=（V，E）中，如果对于顶点Vi,Vj，存在满足下述条件的结点序列X1,X2Xk(k1)l X1=Vi,Xk=Vjl (Xi,Xi+1)E i=1,2,k-1则称结点序列X1=Vi,X2,Xk=Vj为顶点Vi到顶点Vj的一条路径，而路径上的边的数目k-1称为该路径的长度，并称顶点集合X1,.,

23、Xk为连通集。简单路径和回路如果一条路径上的顶点除起点X1和终点Xk可以相同外，其他顶点均不相同，则称此路径为一条简单路径。u如：图2中1 2 4 5是一条简单路径，而1 2 4 3 1 5不是。X1=Xk的简单路径称为回路（也称为环）。u如：图4中1 4 2 1为一条回路。v1v3v5v2v4图2v1v2v3v4图4有根图在一个图中，若存在一个顶点w，它与其他顶点都是连通的，则称此图为有根图，顶点w即为它的根。图5为有根图，1 2 3 4都可以作为根；图6为有根图，1或2为它的根。123图61243图5连通图和最大连通子图对于无向图而言，若其中任两个顶点之间是连通的，则称该图为连通图。一个无

24、向图的连通分支定义为此图的最大连通子图。图2是连通的，它的最大连通子图即为本身。v1v3v5v2v4图2强连通图和强连通分支对于有向图的任意两个顶点Vi、Vj间(ViVj)，都有一条从Vi到Vj的有向路径，同时还有一条从Vj到Vi的有向路径，则称该有向图是强连通图。有向图中强连通的最大子图称为该图的强连通分支。图6不是强连通的，它含有两个强连通分支，如图7。123图7123图6零图和平凡图在一个图中不与任何顶点相邻接的顶点称为孤立顶点。u如：图7中的3仅由孤立顶点组成的图称为零图。仅由一个孤立顶点组成的图称为平凡图。123图7图的存储结构相邻矩阵表示法，若G=（V，E）是一个具有N个顶点的图，

25、则G的相邻矩阵是如下定义的二维数组A，其规模为N*N1(或权)(Vi,Vj)E0(或)(Vi,Vj)EAI,j=0 3 5 8 03 0 6 4 115 6 0 2 08 4 2 0 100 11 0 10 0A1=0 1 0 0 01 0 0 0 10 1 0 1 01 0 0 0 00 0 0 1 0A2=v1v2v3v4v53542101168图8v1v2v5v4v3图9相邻矩阵的特点Type maxn=顶点数的上限;Var a:array1.n,1.n of integer;f:array1.maxn of boolen;无向图的相邻矩阵是对称的，而有向图不是。占用的存储单元数只与顶点

26、数有关而与边数无关。相邻矩阵方便度数的计算。容易计算路径的存在性。在无权有向图或无向图中，判定Vi,Vj两个顶点之间否存在长度为m的路径，只要考虑am=a*a*a*a(m个a矩阵相乘后的乘积矩阵)中(i,j)的元素值是否为0就行了。图的邻接表示法l用邻接表法表示图需要保存一个顺序存储的顶点表和n个边表（每个边表为一个单链表，存储与一个顶点相连的所有边的信息）。l顶点表的每个表目对应于图的一个顶点，包括顶点信息，即：与该顶点相连的边数m；访问标志visited边表的首指针firstarc。图中每个顶点都有一个边表，基中每一个顶点对应于与该顶点相关联的一条边，包括：与此边相关联的另一个顶点序号v；

27、若为带权图的话，该边的权值w；指向边表的下一个顶点的后继指针nextarc.图的邻接表示法Const max=图的顶点数的上限;Type arcptr=arcnode;边表的指针类型 arcnode=record 边表的顶点类型 v:integer;关联该边的另一顶点序号 nestar:arcptr;边表的后继指针 w:real;边的权值 end;vexnode=record 顶点表的表目类型 m:integer;与该顶点相连的边数 visited:boolean;访问标志 firstarc:arcptr;边表的首指针 end;adjlist=array1.max of vexnode;邻接表

28、类型Var dig:adjlist;邻接表 n,e:integer;顶点数和边数图的邻接表示法v1v2v5v4v31257643图10mvisitedfrstarc11false22false32false41false51falsevwnestarc22nil544713nil46nil11nil25nilvwnestarc图的邻接表示法读n,e;For i:=1 to n do begin with digi do begin m:=0;firstarc:=nil;visited:=false;end;end;For i:=1 to e do begin 读第i条边关联的顶点序号j，k和该

29、边的权Wjk;digj.m:=digj.m+1;new(q);with q do begin v:=k;w:=wj,k;nestarc:=digj.firstarc;end;digj.firstarc:=q;end;图的遍历深度优先搜索dfs广度优先搜索bfs深度优先搜索dfsl从某个顶点V0出发，访问此顶点。然后依次从V0的未被访问的邻接点出发深度优先遍历图，直至图中所有和V0有路径相连的顶点都被访问到。若此时图中尚有顶点未被访问，则另选一个未曾访问的顶点作为起始点，重复上述过程，直到图中所有顶点都被访问为止。l从V1出发，dfs图8的结果是：V1 V2 V3 V4 V5 l从V3出发，df

30、s图10的结果是：V3 V2 V1 V5 V4l从V1出发，dfs图10的结果是：V1 V2 V5 V4 V3v1v2v5v4v31257643图10v1v2v3v4v53542101168图8深度优先搜索dfs相邻矩阵：Procedure dfs(i:integer);Begin 访问处理结点i;fi:=true;for j:=1 to n do if(not fj)and(ai,j=1)then dfs(j);End;Procedure traver1;Begin fillchar(f,sizeof(f),0);for i:=1 to n do 深度优先搜索每一个未访问的顶点 if not

31、 fi then dfs(i);End;调用一次dfs(i)，可按深度优先搜索的顺序访问处理顶点i所在的连通分支（强连通分支）广度优先搜索bfsl假设从图中某顶点V0出发，在访问了V0之后依次访问V0的各个未曾访问的邻接点，然后分别从这些邻接点出发按广度优先搜索的顺序遍历图，直至图中所有可被访问的顶点都被访问过。l从V1出发，bfs图8：V1 V2 V3 V4 V5v1v2v3v4v53542101168图8广度优先搜索bfs队列f r队列v1fr队列f r队列v2v3v4fr队列v3v4fr队列v3v4v5fr队列v3v4v5frv1v1 v2 v3v1 v2 v3 v4 v5v1v2v3v

32、4v53542101168图8广度优先搜索bfsProcedure bfs(i:integer);Begin 访问处理结点i;fi:=true;r:=r+1;qr:=i;结点i进入队列q while rfront do begin front:=front+1;从队列中移出队首元素 for j:=1 to n do if(not fj)and(aqfront,j=1)then begin 访问顶点j;fj:=true;r:=r+1;qr:=j;结点j进入队列q end;end;End;广度优先搜索bfsProcedure traver2;Begin fillchar(f,sizeof(f),0

33、);for i:=1 to n do if(not fj)then bfs(i);End;图的生成树l若图是连通的无向图或强连通的有向图，则从其中任一个顶点出发，调用一次dfs或bfs后便可以系统地访问图中所有顶点；l若图是有根的有向图，则从根出发通过调用一次dfs或bfs后亦可以系统地访问图中所有顶点；l在这种情况下，图中的所有顶点加上遍历过程中经过的边所构成子图称作图的生成树。v1v2v3v4v53542101168图8v1v2v5v4v3图9v1v2v3v4v5图8的广度优先搜索树v3v2v4v1v5图9的深度优先搜索树图的最小生成树现有一张城市地图，图中的顶点为城市，无向边代表两个城市

34、间的连通关系，边上的权为公路造价。在分析了这张地图后可以发现，任一对城市都是连通的。现在的问题是，要用公路把所有的城市都联系起来，如何设计可使工程总造价最少。输入：un（城市数，1=n=20)ue(有向边数，1=e=210)u以下e行，每行为边(I,j)和该边的距离Wij(1=i=n,1=j=n)输出：un-1行，每行为两个城市的序号，表明这两个城市间建一条公共汽车线路。图的最小生成树在一张有权连通图中，如何寻找一棵各边权的总和为最小的生成树，就是本章节所要讨论的问题。计算最小生成树的思维方向：计算最小生成树的思维方向：为了保证边权总和最小，必须保证、添加(u,v)不能够形成回路；、在保证的前

35、提下添加权尽可能小的这样的边称之为安全边。计算最小生成树的步骤：计算最小生成树的步骤：有两种算法可计算图的最小生成树uKruskal算法uPrim算法Kruskal算法对给定图的所有边从小到大排序，依次试探将边和它的端点加入生成树，如果加入的边不产生环，则继续将边和它的端点加入，否则，将它删去，直到生成树中含有n-1条边。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;边集，其

36、中第i条边为(ei.x,ei.y)，该边的权为ei.c n,m,ans:longint;顶点数为n，边数为m f:Array 1.maxn of longint;并查集，其中fi为顶点i所在并查集的代表顶点，即子树根Kruskal算法通过函数top(i)计算顶点i所在子树的根Function top(i:longint):longint;计算和返回顶点i所在并查集的代表顶点Begin if ifi Then fitop(fi);若i非所在并查集的代表顶点，则沿fi递归 topfi;返回顶点i所在并查集的代表顶点End;Kruskal算法通过过程Union(i,j,c)合并顶点i和顶点j所在的两

37、棵树现有边权为c的边（i，j）。若该边的两个端点分属于两棵树，顶点i和顶点j所在子树的根分别为x和y，则(i,j)加入最小生成树，合并两棵树（即顶点i和顶点j所在的并查集）。Procedure Union(i,j,c:longint);合并i和j所在集合Var x,y:longint;Begin xtop(i);ytop(j);分别取出顶点i和顶点j所在子树的根 if xy Then Begin inc(ans,c);fyx;End;若i和j分属于两棵子树，则该边权计入最小生成树的权和，两棵子树合并End;Kruskal算法BEGIN 按照边权值（c域值）递增的顺序排序边集e；For i1 t

38、o n do fii;建立由n棵树组成的森林，每棵树包含图的一个顶点 ans0;最小生成树的权和初始化为0 For i1 to m do union(ei.x,ei.y,ei.c);枚举每条边，将两个端点分属两棵树的边加入最小生成树 writeln(ans);END.Prim算法任取一个顶点加入生成树，然后对那些一个端点在生成树中，另一个端点不在生成树中的边进行排序，取权值最小的边，将它和另外一个端点加进生成树中。重复上述步骤直到所有顶点都进入了生成树为止。Prim算法 di顶点i与生成树相连的最短边长；bai顶点i在生成树的标志；wi,j（i,j）的边长。若图中不存在边（i,j），则wi,j

39、=min所有未在生成树的顶点的最小距离值Prim算法fillchar(ba，sizeof(ba)，0)；所有顶点未在生成树for i：=2 to n do di：=；所有顶点的距离值初始化d1：=0；ans：=0；顶点1的距离值和生成树的权和初始化for i：=1 to n do 依次范围每个顶点 Begin min：=；在所有未在生成树、且距离值最小（min）的顶点k for j：=1 to n do if(not baj)and(djmin)then begin k：=j；min：=dj；end；if min=then begin ans：=-1；break；end；若这样的顶点不存在，则

40、无解退出 ans：=ans+min；bak：=true；最小距离值min计入生成树的权和,顶点k进入生成树 for j：=1 to n do 调整与k相连的各顶点的距离值 begin min：=wk，j；if mindj then dj：=min；end；for End；forwriteln(ans：0：3)；输出最小生成树的权和Kruskal与Prim的比较共同点：贪心，选择边权最小的安全边；不同点：Kruskal算法在森林中的两 棵树之间 添安全边；Prim算法在单棵树上添安全边。单源最短路径现有一张县城地图，图中的顶点为城镇，无向边代表两个城镇间的连通关系，边上的权为公路造价，县城所在的

41、城镇为V0。由于该县经济比较落后，因此公路建设只能从县城开始规划。规划的要求是所有可到达县城的城镇必须建设一条通往县城的汽车线路，该线路的工程总造价必须最少。输入：n（城镇数，1=n=20）县城所在的城镇序号V0 e（有向边数，1=evm的距离值+Wmi），则要修改vi的距离（vi的距离值vm的距离值+Wmi）。修改后再选距离值最小的一个结点加入到第一组中，。如此进行下去，直至第一组囊括图的所有结点或再无可加入第一组的结点存在。显然，这种从第二组的结点中选距离值最小的结点扩展是一种贪心策略。051058147713 9 98圆内的数字为距离值。绿色的结点为第一组的结点，灰色的结点为第二组的结点

42、单源最短路径（Dijkstra算法）用一维数组来实现优先队列。设 n图的结点数；adj有向图的相邻矩阵。其中 dist最短路径集合。其中 distipre在v0至vi的最短路径上，vi的前趋结点序号；distilengthv0至vi的最短路径长度，即vi的距离值；(1in)Const n=图的结点数；Type path=record 路径集合的结点类型 length：real；距离值 pre：0n；前趋结点序号 end；var adj：array1n，1n of real 相邻矩阵 dist：array1n of path；路径集合Dijkstra算法fillchar(adj，sizeof(a

43、dj)，0)；建立相邻矩阵adjfor i1 to n do for j1 to n do if（i，j）E then adji，jwij else adji，j；for i1 to n do 路径集合初始化 begin distilengthadjv0，i；if distilength then distiprev0 else distipre0；end；foradjv0，v01；源结点v0进入第一组 Dijkstra算法repeat min；u0；for i1 to n do 从第二组中找距离值最小的结点u if(adji，i=0)and(distilengthmin)then begin

44、 ui；mindistilength；end；then if u0 第二组中存在一个距离值最小的结点 then begin adju，u1；结点u进入第一组 for i1 to n do 修正第二组中u可达的结点距离值 if(adji，i=0)and(distilengthdistulength+adju，i)then begin distilengthdistulength+adju，i；distipreu；end；then end；thenuntil u=0；Dijkstra算法算法结束时，沿着结点vi的pre指针回溯，便可确定v0至vi的最短路径：procedure print(i：integer)；Begin if i=v0 then 输出结点v0 else begin print(distipre)；输出结点i和v0至vi的最短路径长度distilength；end；else End；print显然递归调用print1，printn后，可得知v0至所有结点的最短路径。v0v1v2v3v443629464