sh实现最小生成树和最短路径的算法
\u6700\u77ed\u8def\u5f84\u548c\u6700\u5c0f\u751f\u6210\u6811\u5206\u522b\u5bf9\u5e94\u4ec0\u4e48\u7b97\u6cd5\uff0c\u4e24\u8005\u533a\u522b\u662f\u4ec0\u4e48\uff1f\u6700\u5c0f\u751f\u6210\u6811\u5c31\u662f\u6c42\u7684\u6700\u77ed\u8def\u5f84\uff1f\uff1f\u6700\u77ed\u8def\u5f84\u548c\u6700\u5c0f\u751f\u6210\u6811\u662f\u4e0d\u540c\u7684\u6982\u5ff5\u3002
\u6700\u77ed\u8def\u5f84\u662f\u5bf9\u4e8e\u4e00\u4e2a\u56fe\u7684\u4e24\u4e2a\u7ed3\u70b9\u800c\u8a00\u7684\u3002\u5728\u4e00\u4e2a\u56fe\u4e2d\uff0c\u7ed3\u70b9A\u901a\u8fc7\u67d0\u4e9b\u7ed3\u70b9\u548c\u8fb9\u53ef\u4ee5\u8d70\u5230\u7ed3\u70b9B\uff0c\u90a3\u8fd9\u4e9b\u7ed3\u70b9\u548c\u8fb9\u5c31\u7ec4\u6210\u4e00\u6761A\u5230B\u7684\u8def\u5f84\uff0cA\u5230B\u7684\u6700\u77ed\u8def\u5f84\u5c31\u662fA\u5230B\u7684\u6240\u6709\u8def\u5f84\u4e2d\u8fb9\u6743\u503c\u603b\u548c\u6700\u5c0f\u7684\u90a3\u4e00\u6761\uff08\u6216\u591a\u6761\uff09\u3002
\u6700\u5c0f\u751f\u6210\u6811\u662f\u5bf9\u4e8e\u4e00\u4e2a\u56fe\u672c\u8eab\u800c\u8a00\u7684\u3002\u5bf9\u4e8e\u4e00\u4e2a\u6709n\u4e2a\u7ed3\u70b9\u7684\u65e0\u5411\u8fde\u901a\u56fe\uff08\u8fb9\u6ca1\u6709\u65b9\u5411\uff0c\u4efb\u610f\u4e24\u70b9\u4e4b\u95f4\u90fd\u5b58\u5728\u8def\u5f84\u53ef\u4ee5\u5230\u8fbe\uff09\uff0c\u5fc5\u7136\u53ef\u4ee5\u53bb\u6389\u67d0\u4e9b\u8fb9\uff0c\u4f7f\u5f97\u6700\u7ec8\u5269\u4e0bn-1\u6761\u8fb9\uff0c\u5e76\u4e14n\u4e2a\u7ed3\u70b9\u4ecd\u7136\u662f\u8fde\u901a\u7684\uff0c\u8fd9n\u4e2a\u7ed3\u70b9\u548cn-1\u6761\u8fb9\u7ec4\u6210\u4e86\u539f\u56fe\u7684\u4e00\u4e2a\u751f\u6210\u6811\uff0c\u800c\u6700\u5c0f\u751f\u6210\u6811\u5c31\u662f\u6240\u6709\u53ef\u80fd\u7684\u751f\u6210\u6811\u4e2dn-1\u6761\u8fb9\u7684\u6743\u503c\u603b\u548c\u6700\u5c0f\u7684\u90a3\u4e00\u4e2a\uff08\u6216\u591a\u4e2a\uff09\u3002
\u6700\u77ed\u8def\u5f84\u5e38\u7528\u7b97\u6cd5\u6709\uff1afloyd\uff0cdijkstra\uff0cSPFA\uff0cA*\u7b49
\u6700\u5c0f\u751f\u6210\u6811\u5e38\u7528\u7b97\u6cd5\u6709\uff1aprim\uff0ckruskal
graphminspantree, \u6700\u5c0f\u751f\u6210\u6811
graphshortestpath, \u4e00\u6761\u6700\u77ed\u8def\u5f84
graphallshortestpaths, \u6240\u6709\u6700\u77ed\u8def\u5f84
一、图的生成树与最小生成树
在一个连通图G中，如果取它的全部顶点和一部分边构成一个子图G’，即：
若边集E（G’）中的边既将图中的所有顶点连通又不形成回路，则称子图G’是原图G的一棵生成树。
最小生成树：给图中每个边赋一权值，所有生成树中所选择边的权值之和最小的生成树，称之为最小代价生成树，即是最小生成树。
1、普里姆算法
1.1算法描述
假设G=（V, E）是一个具有n个顶点的连通网，T=（U, TE）是G的最小生成树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空集。算法开始时，首先从V中任取一个顶点（假定取v1），将它并入U中，此时U={v1}，然后只要U是V的真子集（即），就从那些其一个端点已在T中，另一个端点仍在T外的所有边中，找一条最短（即权值最小）边，假定为（vi, vj），其中，并把该边（vi, vj）和顶点vj分别并入T的边集TE和顶点集U，如此进行下去，每次往生成树里并入一个顶点和一条边，直到（n-1）次后就把所有n个顶点都并入到生成树T的顶点集中，此时U＝V，TE中含有（n-1）条边，T就是最后得到的最小生成树。 1.2关键问题
普里姆算法的关键之处是：每次如何从生成树T中到T外的所有边中，找出一条最短边。例如，在第k次前，生成树T中已有k个顶点和（k-1）条边，此时T中到T外的所有边数为k（n-k），当然它包括两顶点间没有直接边相连，其权值被看作为“无穷大”的边在内，从如此多的边中查找最短边，其时间复杂性为O（k（n-k）），显然是很费时的。是否有一种好的方法能够降低查找最短边的时间复杂性呢？ 1.3 解决方法
方法是：假定在进行第k次前已经保留着从T中到T外每一顶点（共（n-k）个顶点）的各一条最短边，进行第k次时，首先从这（n-k）条最短边中，找出一条最最短的边（它就是从T中到T外的所有边中的最短边），假设为（vi, vj），此步需进行（n-k）次比较；然后把边（vi, vj）和顶点vj分别并入T中的边集TE和顶点集U中，此时T外只有n-（k+1）个顶点，对于其中的每个顶点vt，若（vj, vt）边上的权值小于已保留的从原T中到vt的最短边的权值，则用（v, vt）修改之，使从T中到T外顶点vt的最短边为（vj, vt），否则原有最短边保持不变，这样，就把第k次后从T中到T外每一顶点vt的各一条最短边都保留下来了。为进行第（k+1）次运算做好了准备，此步需进行（n-k-1）次比较。所以，利用此方法求第k次的最短边共需比较2（n-k）-1次，即时间复杂性为O（n-k）。
1.4 prim算法：
设一个辅助数组closedge，以记录从U到V—U具有最小代价的边。数组中的每个元素closedge[v]是记录类型，包含两个域： closedge[v].lowcast=Min{cost(u,v)|u∈U}; closedge[v].vex存储该边依附的在U中的顶点。
proc mintree_prim(gn:adjmatrix;u0:integer);
begin
for v:=1 to n do
if v<>u0 then
with closedage[v] do [vex:=u0; lowcast:=gn[u0,v];]
closedge[u0].lowcast:=0;{并入U集合}
for i:=1 to n-1 do
begin
v:=min(closedge);{寻找代价最小的边}
write(closedge[v].vex,v); closedge[v].lowcast:=0;{并入U集合}
for k:=1 to n do
if gn[v,k]<closedge[k].lowcast then
begin closedge[k].lowcast:=gn[v,k]; closedge[k].vex:=v; end;
end;
end; 练习1：prim算法实现
【问题描述】从文件中读入连通带权图的信息，按prim算法求出该图的最小生成树，以V1作为初始结点。
【输入文件】第一行两个整数m和n，分别表示图的结点数和图中的边数。以下n行表示n条边：每一行三个数x、y和k，k表示x与y之间边的权值。
【输出文件】共m行，第一行：最小生成树的权；以下m-1行表示选取的边，边的第1个结点小于第2个结点，并按结点由小到大输出。
【示例】输入：5 7 输出：45
1 2 17 1 4
2 3 30 1 5
1 4 5 2 4
2 4 10 3 5
3 4 24
3 5 7
1 5 23
练习2： Eddy painting
Eddy begins to like painting pictures recently ,he is sure of himself to become a painter.Every day Eddy draws pictures in his small room, and he usually puts out his newest pictures to let his friends appreciate. but the result it can be imagined, the friends are not interested in his picture.Eddy feels very puzze,in order to change all friends 's view to his technical of painting pictures ,so Eddy creates a problem for the his friends of you.
Problem descriptions as follows: Given you some coordinates pionts on a drawing paper, every point links with the ink with the straight line, causes all points finally to link in the same place. How many distants does your duty discover the shortest length which the ink draws?
Input：
The first line contains 0 < n <= 100, the number of point. For each point, a line follows; each following line contains two real numbers indicating the (x,y) coordinates of the point.
Input contains multiple test cases. Process to the end of file.
Output：
Your program prints a single real number to two decimal places: the minimum total length of ink lines that can connect all the points.
Sample Input：
3
1.0 1.0
2.0 2.0
2.0 4.0
Sample Output：
3.41
2、克鲁斯卡尔算法
2.1 算法描述
假设G＝（V，E）是一个具有n个顶点的连通网，T＝（U，TE）是G的最小生成树，U的初值等于V，即包含有G中的全部顶点，TE的初值为空。此算法的基本思想是，将图G中的边按权值从小到大的顺序依次选取，若选取的边使生成树T不形成回路，则把它并入TE中，保留作为T的一条边，若选取的边使生成树T形成回路，则将其舍弃，如此进行下去，直到TE中包含有n-1条边为止。此时的T即为最小生成树。
2.2 关键问题
克鲁斯卡尔算法的关键之处是：如何判断欲加入的一条边是否与生成树中已选取的边形成回路。这可将各顶点划分为所属集合的方法来解决，每个集合中的顶点表示一个无回路的连通分量。算法开始时，由于生成树的顶点集等于图G的顶点集，边集为空，所以n个顶点分属于n个集合。每个集合中只有一个顶点，表明顶点之问互不连通。
2.3 Kruskal算法：
proc mintree_krusk(gn:adjmatrix);
begin
for i:=1 to n do
un[i]:=i;
for i:=1 to n-1 do
begin
minedge(a,b);
write(a,b,gn[a,b]);
k:=un[b];
for i:=1 to n do {两个连通分量合并}
if un[i]=k then un[i]:=un[a];
end;
end;
2.4 注意：
proc minedge(var a:integer;var b:integer);用于在剩下的边中选取不再同一连通分量上的最小代价的边，边的结点分别为a和b。
为了实现该过程，可以将图中的边生成一边结点（包含两个顶点和代价）数组，由小到大排序，然后通过排序后的数组进行处理；
un数组：用来记载随着边的加入，各顶点属于哪个连通分量。
练习3：Kruskal算法实现
【问题描述】从文件中读入连通带权图的信息，按Kruskal算法求出该图的最小生成树，以V1作为初始结点。
【输入文件】第一行两个整数m和n，分别表示图的结点数和图中的边数。以下n行表示n条边：每一行三个数x、y和k，k表示x与y之间边的权值。
【输出文件】共m行，第一行：最小生成树的权；以下m-1行表示选取的边，按选取边的权值由小到大输出。
【示例】输入：5 7 输出：45
1 2 17 1 4
2 3 30 3 5
1 4 5 2 4
2 4 10 1 5
3 4 24
3 5 7
1 5 23
练习4：判断最小生成树是否唯一
Given a connected undirected graph, tell if its minimum spanning tree is unique.
Definition 1 (Spanning Tree): Consider a connected, undirected graph G = (V, E). A spanning tree of G is a subgraph of G, say T = (V', E'), with the following properties:
1. V' = V.
2. T is connected and acyclic.
Definition 2 (Minimum Spanning Tree): Consider an edge-weighted, connected, undirected graph G = (V, E). The minimum spanning tree T = (V, E') of G is the spanning tree that has the smallest total cost. The total cost of T means the sum of the weights on all the edges in E'.
Input
The first line contains a single integer t (1 <= t <= 20), the number of test cases. Each case represents a graph. It begins with a line containing two integers n and m (1 <= n <= 100), the number of nodes and edges. Each of the following m lines contains a triple (xi, yi, wi), indicating that xi and yi are connected by an edge with weight = wi. For any two nodes, there is at most one edge connecting them.
Output
For each input, if the MST is unique, print the total cost of it, or otherwise print the string 'Not Unique!'.
Sample Input
2
3 3
1 2 1
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2
Sample Output
3
Not Unique!
二、最短路径
【问题描述】由于从一顶点到另一顶点可能存在着多条路径。每条路径上所经过的边数可能不同，即路径长度不同，我们把路径长度最短（即经过的边数最少）的那条路径叫做最短路径，其路径长度叫做最短路径长度或最短距离。求图中一顶点vi到其余各顶点的最短路径和最短距离比较容易，只要从该顶点vi，出发对图进行一次广度优先搜索遍历，在遍历时记下每个结点的层次即可。
若图是带权图（假定权值非负）从源点vi到终点vj的每条路径上的权（它等于该路径上所经边上的权值之和，称为该路径的带权路径长度）可能不同，我们把权值最小的那条路径也称做最短路径，其权值也称作最短路径长度或最短距离。
实际上，这两类最短路径问题可合并为一类，这只要把第一类的每条边的权都设为1就归属于第二类了，所以在以后的讨论中，若不特别指明，均是指第二类的最短路径问题。
求图的最短路径问题包括两个子问题：一是求图中一顶点到其余各顶点的最短路径，二是求图中每对顶点之间的最短路径。下面分别进行讨论。
始点 终点 最短路径 路径长度
v0 v1 No path
v2 (v0,v2) 10
v3 (v0,v4,v3) 50
v4 (v0,v4) 30
v5 (v0,v4,v3,v5) 60
始点 终点 最短路径 路径长度
v1 V2 (v1,v2) 10
V3 (v1,v2,v3) 27
V4 (v1,v5,v4) 20
v5 (v1,v5) 7
1、从一顶点到其余各顶点的最短路径
1.1 描述
迪杰斯特拉（Dijkstra）于1959年提出了解决此问题的一般算法，具体做法是按照从源点到其余每一顶点的最短路径长度的升序依次求出从源点到各顶点的最短路径及长度，每次求出从源点vi到一个终点vj的最短路径及长度后，都要以vj作为新考虑的中间点，用vi到vj的最短路径和最短路径长度对vi到其它尚未求出最短路径的那些终点的当前路径及长度作必要的修改，使之成为当前新的最短路径和最短路径长度，当进行n-2次后算法结束。
1.2 Dijkstra算法:
首先，引进一个辅助向量dist，dist[i]表示当前所找到的从始点V到每个终点Vi的最短路径长度。其初态为：若<v,vi>存在，则dist[i]为其上的权值，否则为最大值（计算机能表示）。
算法:(1)用邻接矩阵cost表示带权有向图。S表示已找到的从v出发的最短路径的终点的集合，初态为空。dist向量的初值为：dist[v,i]=cost[v,i];
(2)选择vj，使得：dist[j]=Min{dist[i]|vi∈V-S}；vj就是当前求得从v出发的最短路径的终点。
S=S+{j};
(3)修改从v出发到集合V-S上任意顶点vk可达的最短路径长度。
if dist[j]+cost[j,k]<dist[k] then dist[k]:=dist[j]+cost[j,k];
(4)重复(2)(3)共n-1次。
代码：proc short_dij;
begin
for i:=1 to n do
begin
dist[i]:=cost[v0,i];
if dist[i]<max then path[i]:=v0 else path[i]:=-1; end;
flag[I]:=true;
for k:=1 to n-1 do
begin
wm:=max; j:=v0;
for i:=1 to n do
if not(flag[i]) and (dist[i]<wm) then begin j:=i; m:=dist[i]; end;
flag[j]:=true; for i:=1 to n do if not(flag[i]) and (dist[j]+cost[j,i]<dist[i]) then
begin dist[i]:=dist[j]+cost[j,i]; path[i]:=j; end;
end;
end; 其中：cost：邻接矩阵；
path[i]：存储从v0到顶点i的最短路径；是以集合作为数组元素；
dist[i]：存储相应路径长度；
flag[i]：表示已处理的顶点。
练习5：Dijkstra算法练习
【问题描述】从文件中读入带权图的信息，按Dijkstra算法根据给定源点求出从源点法到该图中其余顶点的最短路径。
【输入文件】第一行：一个整数L：L=0表示无向图，L=1表示有向图；第二行三个整数m、n和k，分别表示图的结点数、图中的边数以及源点。以下n行表示n条边：每一行三个数x、y和z，z表示x与y之间边的权值。
【输出文件】共m-1行，每一行的数据包括：顶点： 最短路径：路径，如果不存在路径，数据为：顶点：No path。
【示例】输入：1 输出：2：No path
6 8 1 3：10：1 3
1 3 10 4：50：1 5 4
1 5 30 5：30：1 5
1 6 100 6：60：1 5 4 6
2 3 5
3 4 50
4 6 10
5 4 20
5 6 60
练习6：路由选择问题
【问题描述】
X城有一个含有N个节点的通信网络，在通信中，我们往往关心信息从一个节点I传输到节点J的最短路径。遗憾的是，由于种种原因，线路中总有一些节点会出故障，因此在传输中要避开故障节点。
任务一：在己知故障节点的情况下，求避开这些故障节点，从节点I到节点J的最短路径S0。
任务二：在不考虑故障节点的情况下，求从节点I到节点J的最短路径S1、第二最短路径S2。
【输入文件】
第1行： N I J (节点个数 起始节点 目标节点)
第2—N+1行： Sk1 Sk2…SkN (节点K到节点J的距离为SkJ K=1，2，……，N)
最后一行： P T1 T2……Tp (故障节点的个数及编号)
【输出文件】
S0 S1 S2 (S1<=S2 从节点I到节点J至少有两条不同路径)
【输入输出样例】
route.in
5 1 5
0 10 5 0 0
10 0 0 6 20
5 0 0 30 35
0 6 30 0 6
0 20 35 6 0
1 2
route.out
40 22 30
2、每对顶点之间的最短路径
求图中每对顶点之间的最短路径是指把图中任意两个顶点vi和vj（i≠j）之间的最短路径都计算出来。解决此问题有两种方法：一是分别以图中的每个顶点为源点共调用n次迪杰斯特拉算法，此方法的时间复杂性为O（n3）；二是采用下面介绍的弗洛伊德（Floyed）算法，此算法的时间复杂性仍为O（n3），但比较简单。 弗洛伊德算法实际上是一个动态规划的算法。从图的邻接矩阵开始，按照顶点v1，v2，…，vn的次序，分别以每个顶点vk（1≤k≤n）作为新考虑的中间点，在第k-1次运算Ak-1 （A（0）为原图的邻接矩阵G） 的基础上，求出每对顶点vi到vj的最短路径长度计算公式为：
Floyd算法：
proc shortpath_floyd;
begin
for i:=1 to n do for j:=1 to n do
begin
length[i,j]:=cost[i,j];
if length[i,j]<max then path[i,j]:=[i]+[j];
end;
for k:=1 to n do for i:=1 to n do for j:=1 to n do
if length[i,k]+length[k,j]<length[i,j] then
begin
length[i,j]:=length[i,k]+length[k,j];
path[i,j]:=path[i,k]+path[k,j];
end;
end;
其中：cost为邻接矩阵；
path[i,j]：表示顶点i到j的最短路径；
length[i,j]：
练习7：Floyd算法练习
【问题描述】从文件中读入带权图的信息，按Dijkstra算法根据给定源点求出从源点到该图中其余顶点的最短路径。
【输入文件】第一行：一个整数L：L=0表示无向图，L=1表示有向图；第二行三个整数m、n，分别表示图的结点数和图中的边数。以下n行表示n条边：每一行三个数x、y和z，z表示x与y之间边的权值。第n+2行：整数R，以下R行每行一个整数表示顶点标号作为源点。
【输出文件】共R行，每一行的数据表示源点到其余顶点的距离，按顶点编号由小大输出，如果没有路径，输出-1。
【示例】输入：1 输出：-1 10 50 30 60
6 8 -1 –1 –1 20 30
1 3 10
1 5 30
1 6 100
2 3 5
3 4 50
4 6 10
5 4 20
5 6 60
2
1
5
绛旓細鎵句竴鏉鏈鐭(鍗虫潈鍊鏈灏)杈,鍋囧畾涓(vi, vj),鍏朵腑,骞舵妸璇ヨ竟(vi, vj)鍜岄《鐐箆j鍒嗗埆骞跺叆T鐨勮竟闆員E鍜岄《鐐归泦U,濡傛杩涜涓嬪幓,姣忔寰鐢熸垚鏍閲屽苟鍏ヤ竴涓《鐐瑰拰涓鏉¤竟,鐩村埌(n-1)娆″悗灏辨妸鎵鏈塶涓《鐐归兘骞跺叆鍒扮敓鎴愭爲T鐨勯《鐐归泦涓,姝ゆ椂U
绛旓細浠ユ暟鎹粨鏋勪负渚嬶紝鏈灏忕敓鎴愭爲鍜屾渶鐭矾寰勭殑鍖哄埆鏄渶灏忕敓鎴愭爲鑳藉淇濊瘉鏁翠釜鎷撴墤鍥剧殑鎵鏈夎矾寰勪箣鍜屾渶灏忥紝浣嗕笉鑳戒繚璇佷换鎰忎袱鐐逛箣闂存槸鏈鐭矾寰勩傛渶鐭矾寰勬槸浠庝竴鐐瑰嚭鍙戯紝鍒拌揪鐩殑鍦扮殑璺緞鏈灏忋傛暟鎹粨鏋勶紙datastructure锛夋槸璁＄畻鏈哄瓨鍌ㄣ佺粍缁囨暟鎹殑鏂瑰紡锛屾寚鐩镐簰涔嬮棿瀛樺湪涓绉嶆垨澶氱鐗瑰畾鍏崇郴鐨勬暟鎹厓绱犵殑闆嗗悎锛屽線寰鍚岄珮...
绛旓細鏈鐭矾寰勫拰鏈灏忕敓鎴愭爲鏄笉鍚岀殑姒傚康銆傛渶鐭矾寰勬槸瀵逛簬涓涓浘鐨勪袱涓粨鐐硅岃█鐨勩傚湪涓涓浘涓紝缁撶偣A閫氳繃鏌愪簺缁撶偣鍜岃竟鍙互璧板埌缁撶偣B锛岄偅杩欎簺缁撶偣鍜岃竟灏辩粍鎴愪竴鏉鍒癇鐨勮矾寰勶紝A鍒癇鐨勬渶鐭矾寰勫氨鏄疉鍒癇鐨勬墍鏈夎矾寰勪腑杈规潈鍊兼诲拰鏈灏忕殑閭ｄ竴鏉★紙鎴栧鏉★級銆傛渶灏忕敓鎴愭爲鏄浜庝竴涓浘鏈韩鑰岃█鐨勩傚浜庝竴涓湁n...
绛旓細鏈灏忕敓鎴愭爲鏄敤鍜屾渶灏戠殑杈归泦灏嗕竴涓浘杩炴垚浠绘剰2鐐瑰彲杈撅紝骞朵笖杩欎釜杈归泦鐨勬婚暱搴︽渶灏忋鏈鐭矾寰鏄竴涓浘涓2涓偣鐨勬渶鐭窛绂汇傚畬鍏ㄤ笉鏄竴涓蹇点傞偅涔熶笉涓鏍峰晩锛屼竴鐐瑰埌鍏朵綑鍚勭偣鐨勮矾寰勫拰鏈灏忥紝灏辨槸涓鐐瑰埌鍏跺畠鐐圭殑鏈鐭矾寰勫拰銆傚樊鐨勫お杩滀簡銆傛瘮濡傝繖鏍蜂竴涓浘(杈规潈宸叉爣鍑)4 v--v 5 \ / 3 v 2 ...
绛旓細鏈鐭矾寰 姣忎袱涓偣i,j涔嬮棿杩炰竴鏉 i鍒癹璺濈闀跨殑杈广 鍋氫竴娆鏈灏忕敓鎴愭爲锛坧rim鎴栬匥ruskal锛夈 甯屾湜鑳藉府鍒颁綘銆傛庝箞姹傛渶鐭矾寰 鏈鐭矾寰勯棶棰樻槸鍥捐鐮旂┒涓殑涓涓粡鍏告紨绠楁硶闂锛 鏃ㄥ湪瀵绘壘鍥撅紙鐢辩粨鐐瑰拰璺緞缁勬垚鐨勶級涓袱缁撶偣涔嬮棿鐨勬渶鐭矾寰勩 婕旂畻娉曞叿浣撶殑褰㈠紡鍖呮嫭锛 1. 纭畾璧风偣鐨勬渶鐭矾寰...
绛旓細涓 鍖哄埆 鏈灏忕敓鎴愭爲鑳藉淇濊瘉鏁翠釜鎷撴墤鍥剧殑鎵鏈夎矾寰勪箣鍜屾渶灏忥紝浣嗕笉鑳戒繚璇佷换鎰忎袱鐐逛箣闂存槸鏈鐭矾寰銆傛渶鐭矾寰勬槸浠庝竴鐐瑰嚭鍙戯紝鍒拌揪鐩殑鍦扮殑璺緞鏈灏忋備簩 瀹炵幇鏂规硶 1. 鏈灏忕敓鎴愭爲 鏈灏忕敓鎴愭爲鏈変袱绉嶇畻娉曟潵寰楀埌锛歅rims绠楁硶鍜孠ruskal绠楁硶銆侹ruskal绠楁硶锛氭牴鎹竟鐨勫姞鏉冨间互閫掑鐨勬柟寮忥紝涓娆℃壘鍑哄姞鏉冨兼渶浣庣殑杈规潵...
绛旓細include <stdio.h> define INFINITY 10000 define TRUE 1 define FALSE 0 define VERTEX_NUM 6 typedef struct Graph { char vexs[VERTEX_NUM]; /*椤剁偣*/ int arcs[VERTEX_NUM][VERTEX_NUM]; /*閭绘帴鐭╅樀*/ int vexnum; /*椤剁偣鏁*/ int arcnum; /*寮ф暟*/ }Graph;
绛旓細鏈鐭矾寰勫拰鏈灏忕敓鎴愭爲鏄笉鍚岀殑姒傚康.鏈鐭矾寰勬槸瀵逛簬涓涓浘鐨勪袱涓粨鐐硅岃█鐨.鍦ㄤ竴涓浘涓,缁撶偣A閫氳繃鏌愪簺缁撶偣鍜岃竟鍙互璧板埌缁撶偣B,閭ｈ繖浜涚粨鐐瑰拰杈瑰氨缁勬垚涓鏉鍒癇鐨勮矾寰,A鍒癇鐨勬渶鐭矾寰勫氨鏄疉鍒癇鐨勬墍鏈夎矾寰勪腑杈规潈鍊兼诲拰鏈灏忕殑閭ｄ竴鏉★紙鎴栧鏉★級.鏈灏忕敓鎴愭爲鏄浜庝竴涓浘鏈韩鑰岃█鐨.瀵逛簬涓涓湁n涓...
绛旓細PRIM(绠鍗曠増) 鏈灏忕敓鎴愭爲绠楁硶 (Minimum Spanning Tree)杈撳叆锛氬浘g锛 // 鏈夊悜鍥炬垨鑰呮棤鍚戝浘 杈撳嚭锛(1)鏈灏忕敓鎴愭爲闀縮um锛(2)鏈灏忕敓鎴愭爲prev銆傜粨鏋: 鍥緂鐢ㄩ偦鎺ョ煩闃佃〃绀猴紝鏈鐭杈归暱dist鐢ㄦ暟缁勮〃绀恒傜畻娉曪細Prim绠楁硶 澶嶆潅搴︼細O(|V|^2)/ include <iostream> include <vector> include <list> incl...
绛旓細绗4绔犺浆鍚戝浘鐨勭畻娉曪紝浠庡浘鐨勬蹇靛嚭鍙戯紝娣卞叆鎺㈣浜嗗浘鐨勬悳绱㈤棶棰樸佹嫇鎵戞帓搴忋佸己杩為氬垎閲忋鏈灏忕敓鎴愭爲鍜屾渶鐭矾寰绠楁硶绛夈傝繕娑夊強浜嗘鎷夊洖璺拰涓浗閭掑憳闂锛屼互鍙婄綉缁滄祦鍙婂叾搴旂敤鐨勮璁猴紝鏈鍚庢彁渚涗簡涔犻鍜屽弬鑰冭祫婧愩傜5绔犳繁鍏ュ埌NP瀹屽叏鎬х悊璁猴紝浠嬬粛浜嗗浘鐏垫満銆佸垽瀹氶棶棰樺拰P銆丯P绫婚棶棰橈紝鎺㈣浜哊P瀹屽叏闂鍜孨P鍥伴毦...
