《数据结构算法集锦》由会员分享，可在线阅读，更多相关《数据结构算法集锦（12页珍藏版）》请在金锄头文库上搜索。
1、一、数论算法 1求两数的最大公约数 function gcd(a,b:integer):integer;begin if b=0 then gcd:=a else gcd:=gcd (b,a mod b);end ; 2求两数的最小公倍数 function lcm(a,b:integer):integer;beginif a0 do inc(lcm,a); end;3素数的求法A.小范围内判断一个数是否为质数： function prime (n: integer): Boolean;var I: integer; begin for I:=2 to trunc(sqrt(n) do if n
2、 mod I=0 then begin prime:=false; exit; end;prime:=true; end;B判断longint范围内的数是否为素数(包含求50000以 内的素数表)：procedure getprime; var i,j:longint;p:array1.50000 of boolean; beginfillchar(p,sizeof(p),true); p1:=false;i:=2; while i50000 do beginif pi then begin j:=i*2; while j=x then breakelse if x mod pri=0 the
3、n exit; prime:=true;end;prime 二、图论算法 1最小生成树A.Prim 算法： procedure prim(v0:integer);var lowcost,closest:array1.maxn of integer;i,j,k,min:integer;beginfor i:=1 to n do beginlowcosti:=costv0,i; closesti:=v0;end;for i:=1 to n-1 do 寻找离生成树最近的未加入顶点kbeginmin:=maxlongint;for j:=1 to n doif (lowcostjmin) and (l
4、owcostj0) then begin min:=lowcostj; k:=j; end;lowcostk:=0; 将顶点k加入生成树生成树中增加一条新的边k到closestk修正各点的lowcost和closest值for j:=1 to n doif costk,jlwocostj then beginlowcostj:=costk,j;closestj:=k;end;end;end;primB.KruskaI算法：(贪心) 按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成 树。function find(v:integer):integer; 返回顶点v所在的集合var i
5、:integer;begini:=1;while (i=n) and (not v in vseti) do inc(i);if i0 dobegin i:=find(eq.v1);j:=find(eq.v2); if ij then begin inc(tot,eq.len);vseti:=vseti+vsetj;vsetj:=; dec(p);end;inc(q);end;writeln(tot);end;2. 最短路径A.标号法求解单源点最短路径：Var a:array1.maxn,1.maxn of integer;b:array1.maxn of integer; bi指顶点倒源点的
6、最短路径mark:array1.maxn of boolean;procedure bhf;var best,best_j:integer; beginfillchar(mark,sizeof(mark),false);mark1:=true; b1:=0; 1 为源点 repeatbest:=0; for i:=1 to n doIf marki then 对每一个已计算出最短路 径的点 for j:=1 to n doif (not markj) and (ai,j0) then if (best=0) or (bi+ai,j0 then beginbbest_j:=best；markbe
7、st_j:=true; end;until best=0; end;bhfB. Floyed算法求解所有顶点对之间的最短路径： procedure floyed;begin for I:=1 to n do for j:=1 to n doif aI,j0 then pI,j:=I else pI,j:=0;pl,j表示倒j的最短路径上j的前驱结点 for k:=1 to n do 枚举中间结点 for i:=1 to n dofor j:=1 to n do if ai,k+aj,kai,j then beginai,j:=ai,k+ak,j;pl,j:=pk,j; end;end;C. D
8、ijkstra 算法：Var a:array1.maxn,1.maxn of integer;b,pre:array1.maxn of integer; prei 指最短路径 上I的前驱结点 mark:array1.maxn of boolean;procedure dijkstra(v0:integer);beginfillchar(mark,sizeof(mark),false); for i:=1 to n dobegin di:=av0,i; if di0 then prei:=v0 else prei:=0;end; markv0:=true;repeat 每循环1次加入1个离1 集
9、合最近的结点并调 整其他结点的参数 min:=maxint; u:=0; u记录离1集合最近的结点 for i:=1 to n doif (not marki) and (dimin) then begin u:=i; min:=di; end;if u0 thenbeginmarku:=true;for i:=1 to n doif (not marki) and (au,i+dudi) thenbegindi:=au,i+du;prei:=u;end;end;until u=0;end;3. 计算图的传递闭包Procedure Longlink;Var T:array1.maxn,1.ma
10、xn of boolean;BeginFillchar(t,sizeof(t),false);For k:=1 to n doFor I:=1 to n doFor j:=1 to n do TI,j:=tI,j or (tI,k and tk,j);End;4无向图的连通分量A深度优先procedure dfs ( now,color: integer);beginfor i:=1 to n doif anow,i and ci=0 then 对结点 I 染色begin ci:=color; dfs(I,color); end;end;B 宽度优先(种子染色法)5关键路径几个定义：顶点1为源
11、点，n为汇点。a. 顶点事件最早发生时间Vej,Ve j = max Ve j + wI,j ,其中 Ve (1) = 0;b. 顶点事件最晚发生时间Vlj,Vl j = min Vlj- wI,j ，其中 Vl(n) = Ve(n);c. 边活动最早开始时间Eel,若边I由j,k表示，则EeI = Vej;d. 边活动最晚开始时间ElI,若边I由j,k表示，贝旧I = Vlk-wj,k; 若Eej = Elj，则活动j为关键活动，由关键活动组成的路径为关键路 径。求解方法：a. 从源点起topsort,判断是否有回路并计算Ve;b. 从汇点起topsort,求Vl;c. 算Ee 和El;6拓
12、扑排序 找入度为0的点，删去与其相连的所有边，不断重复这一过程。例：寻找一数列，其中任意连续p项之和为正，任意q项之和为负，若 不存在则输出NO.7.回路问题Euler 回路(DFS)定义：经过图的每条边仅一次的回路。(充要条件：图连通且无奇点)Hamilton 回路定义：经过图的每个顶点仅一次的回路。一笔画 充要条件：图连通且奇点个数为0个或2个。8判断图中是否有负权回路Bellman-ford算法xI,yI,tI分别表示第I条边的起点，终点和权。共n个结点和m条边。procedure bellman-fordbeginfor I:=0 to n-1 do dI:=+infinitive;d0:=0;for I:=1 to n-1 dofor j:=1 to m do 枚举每一条边if dxj+tjdyj then dyj:=dxj+tj;for I:=1 to m doif dxj+tjdyj then return falseelse return true;end;9第n最短路径问题*第
