2023年图论算法有哪些[图论算法(经典)].docx
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《2023年图论算法有哪些[图论算法(经典)].docx》由会员分享,可在线阅读,更多相关《2023年图论算法有哪些[图论算法(经典)].docx(44页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、2023年图论算法有哪些图论算法(经典) 图论算法 最小生成树算法(Prim算法) 单源最短路径算法(Dijkstra算法) 随意结点最短路径算法(Floyd算法) 求有向带权图的全部环 Bellman-Ford 算法 计算图的连通性 计算最佳连通分支 计算拓扑序列 图论算法习题 网络建设问题 最短变换问题 挖地雷 乌托邦城市 乌托邦交通中心 某高校打算在校内网中构建校内网络,已知在校内网中选好了N (N 【输入】network.in 输入文件的第一行为一个正整数N(1N100)。 接下来N 行,每行2个数U,V ,表示坐标。 【输出】network.out 输出最短路径距离(保留两位小数)
2、【样例数据】 【输入】 5 0 0 0 1 0 -1 1 0 -1 0 【输出】 4.00 思路分析:此题可以应用PRIM 算法解决,关键是依据输入文件算出图的邻接矩阵,然后可以干脆应用PRIM 算法。 program network; const vmax=100; var w:array1.vmax,1.vmaxof real; x,y:array1.vmax of real; i,j,k,v,e:integer; sum:real; procedure prim(v0:integer); var flag:array1.vmax of boolean; min:real; prevk,n
3、extk:integer; begin fillchar(flag,sizeof(flag),false); flagv0:=true; for i:=1 to v-1 do begin min:=1e38; for k:=1 to v do if flagk then for j:=1 to v do if (not flagj) and (wk,j0) then begin min:=wk,j; nextk:=j; prevk:=k; end; if min1e10 then begin flagnextk:=true; writeln(prevk, ,nextk, ,min:0:2);
4、此部分输出每个结点对的距离,因题目不要求所以不输出。 sum:=sum+min; end; end; end;prim begin assign(input,network.in); reset(input); assign(output,network.out); rewrite(output); fillchar(w,sizeof(w),0); readln(v); for i:=1 to v do readln(xi,yi); for i:=1 to v do 计算图的邻接矩阵 begin for j:=i+1 to v do begin wi,j:=sqrt(sqr(xi-xj)+sq
5、r(yi-yj); wj,i:=wi,j; end; end; sum:=0; prim(1); writeln(sum:0:2); close(input); close(output); end. 无向图的生成树就是从图的边集中选择一些边,使得这些边构成一个连通无环图,也就是树。假如给每一条边加一个权,全部生成树中权和最小的生成树称为最小生成树。 【Prim 算法思想】 随意时刻的中间结果都是一棵树,每次花费最小的代价,用一条边把不在树中的结点加进来。 【最小生成树算法实例】 现有一张城市地图,图中的顶点为城市,无向边代表两个城市间的连通关系,边上的权代表马路造价。在分析了这张图后发觉,任
6、一对城市都是连通的。现在要求用马路把全部城市联系起来,如何设计可使得工程的总造价最少? 【输入】 第一行两个数v(v 【输出】 v-1行,每行为两个城市的序号,表明这两个城市间建一条马路,再加该马路的造价。 【输入样例】 6 10 1 2 10 1 5 19 1 6 21 2 3 5 2 4 6 2 6 11 3 4 6 4 5 18 4 6 14 5 6 33 【输出样例】 1 2 10 2 3 5 2 4 6 2 6 11 4 5 18 原 图 最小生成树 program prim_example; Const vmax=200 var w:array1.vmax,1.vmaxof int
7、eger; i,j,k,v,e:integer; procedure prim(v0:integer); v0是起先结点 var flag:array1.vmax of boolean; min,prevk,nextk:integer; begin fillchar(flag,sizeof(flag),false); flagv0:=true; 先选出v0 for i:=1 to v-1 do 一共找寻v-1条边 begin min:=maxint; for k:=1 to v do if flagk then 找已在集合中的顶点 for j:=1 to v do 求满意条件的边的最小值 if
8、 (not(flagj) and (wk,j0) then begin min:=wk,j; 登记最小值 nextk:=j; prevk:=k; end; if minmaxint then begin flagnextk:=true; 最小值对应顶点进入集合 writeln(prevk, ,nextk, ,min); end; end;for end;prim begin assign(input,prim.in); reset(input); assign(output,prim.out); rewrite(output); fillchar(w,sizeof(w),0); readln(
9、v,e); for k:=1 to e do begin read(i,j); readln(wi,j); wj,i:=wi,j; end; prim(1); close(input); close(output); end. 设图G=(V,E)是一个有向图, 它的每一条边(U,V)都有一个非负权W(U,V),在G 中指定一个结点V0,要求从V0到G 的每一个结点Vj 的最短路径找出来(或指出不存在)。 由于源结点V0是给定的,所谓称为单源最短路径。 【Dijkstra 算法思想】 把全部结点分为两组。 第一组:包含已确定最短路径的结点。 其次组:包含尚未确定最短路径的结点。 按最短路径长度递
10、增的依次把其次组的结点加到第一组中去,直到V0可达的全部结点都包含于第一组中。在这个过程中,总保持从V0到第一组各结点的最短路径长度都不大于从V0到其次组任何结点的路径长度。 【单源最短路径算法实例】 现有一张县城的城镇地图,图中的顶点为城镇,无向边代表两个城镇间的连通关系,边上的权为马路造价,县城所在的城镇为v0。由于该县经济比较落后,因此马路建设只能从县城起先规划。规划的要求是全部可到达县城的城镇必需建设一条通往县城的汽车线路,该线路的工程总造价必需最少。 【输入】 第一行一个整数v ,代表城镇数,县城编号为1。 其次行是一个整数e ,表示有向边数。 以下e 行,每行为两个城镇编号和它们之
11、间的马路造价。 【输出】 v-1行,每行为两个城市的序号,表明这两个城市间建一条马路。 【输入样例】 6 10 1 2 10 1 5 19 1 6 21 2 3 5 2 4 6 2 6 11 3 4 6 4 5 18 4 6 14 5 6 33 【输出样例】 1 2 2 3 2 4 1 5 1 6 原 图 从第1点动身的最短路径 program dijkstra_example; const vmax=100; type path=record 此记录类型用于记录每一个结点与v0的距离和其父结点 length:integer; pre:0.vmax; end; var w:array1.vma
12、x,1.vmax of integer; dist:array1.vmax of path; v,e,u,i,j,x,y:integer; procedure init; begin assign(input,dijkstra.in); reset(input); assign(output,dijkstra.out); rewrite(output); readln(v); readln(e); for i:=1 to v do for j:=1 to v do if ij then wi,j:=30000 30000只是一个较大的数的意思,实际应用于应当依据题目中给出的取值范围给予一个充分
13、大的数 else wi,j:=0; for i:=1 to e do begin read(x,y); readln(wx,y); wy,x:=wx,y; end; end; procedure dijkstra(v0:integer); var min:integer; begin wv0,v0:=1; v0首先进入第一组 for i:=1 to v do begin disti.length:=wv0,i; 计算每个结点的距离值 if disti.length30000 then disti.pre:=v0 如和v0干脆有路,则置前驱结点为v0 else disti.pre:=0; end
14、; repeat min:=30000; u:=0; for i:=1 to v do 找最短距离 if (wi,i=0) and (disti.length then begin u:=i; min:=disti.length; end; if u0 then begin wu,u:=1; for i:=1 to v do 重新计算其他结点的距离值 if (wi,i=0) and (disti.length>distu.length+wu,i) then begin disti.length:=distu.length+wu,i; disti.pre:=u; end; end; unt
15、il u=0; end; begin init; v0:=1; dijkstra(v0); for i:=1 to v do begin if (iv0) and (disti.length30000) then write(disti.pre, ,i); end; close(input); close(output); end. 设图G=(V,E)是一个有向图, 对于每对结点(U,V),找出从U 到V 的最短路径。 【Floyd 算法思想】 利用一个三重循环产生一个存储每个结点最短距离的矩阵. 【Floyd 算法实例】 现有一张城市地图,图中的顶点为城市,无向边代表两个城市间的连通关系,边
16、上的权代表城市之间的距离。求每个城市的最短距离 【输入】 第一行两个数v,e ,分别代表城市数和边数 以下e 行,每行为两个顶点和它们之间的边权。 【输出】 全部可能连接的城市的最短距离。 【输入样例】 6 10 1 2 10 1 5 19 1 6 21 2 3 5 2 4 6 2 6 11 3 4 6 4 5 18 4 6 14 5 6 33 【输出样例】 1 2 10 1 3 15 1 4 16 1 5 19 1 6 21 2 3 5 2 4 6 2 5 24 2 6 11 3 4 6 3 5 24 3 6 16 4 5 18 4 6 14 5 6 32 program floyd_exa
17、mple; const maxn=10; var n,s,t,i,j:integer; dist:array1.maxn,1.maxn of real; prev:array1.maxn,1.maxn of 0.maxn; procedure init; var m,i,u,v:integer; begin assign(input,floyd.in); reset(input); assign(output,floyd.out); rewrite(output); readln(n,m); fillchar(prev,sizeof(prev),0); for u:=1 to n do for
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 图论算法经典 2023 年图论 算法 哪些 经典
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内