在一个图中，每条边或弧可以拥有一个与之相关的数值，我们将它称为权。这些权可以具有一定的含义，比如，表示一个顶点到达另一个顶点的距离、所花费的时间、线路的造价等等。这种带权的图通常被称作网。

图或网的生成树不是唯一的，从不同的顶点出发可以生成不同的生成树，但n个结点的生成树一定有n-1条边

下面我们计算一下上面两棵生成树的权值之和。第一棵生成树的权值总和是：16+11+5+6+18=56；第二棵生成树的权值是：16+19+33+18+6=92。通常我们将权值总和最小的生成树称为最小生成树。

构造最小生成树的方法：最初生成树为空，即没有一个结点和一条边，首先选择一个顶点作为生成树的根，然后每次从不在生成树中的边中选择一条权值尽可能小的边，为了保证加入到生成树中的边不会造成回路，与该边邻接的两个顶点必须一个已经在生成树中，一个则不在生成树中，若网中有n个顶点（这里考虑的网是一个连通无向图），则按这种条件选择n-1边就可以得到这个网的最小生成树了。详细的过程可以描述为：设置2个集合，U集合中的元素是在生成树中的结点，V-U集合中的元素是不在生成树中的顶点。首先选择一个作为生成树根结点的顶点，并将它放入U集合，然后在那些一端顶点在U集合中，而另一端顶点在V-U集合中的边中找一条权最小的边，并把这条边和那个不在U集合中的顶点加入到生成树中，即输出这条边，然后将其顶点添加到U集合中，重复这个操作n-1次。

下面我们考虑一下如何实现这个操作过程的算法。

分析 ：（1）它主要有两项操作：按条件选择一条边和将顶点加入到U集合中；（2）网中的每个顶点不是在U集合中，就是在V-U集合中。为了提高算法的时间、空间效率，我们将为这个算法设计一个辅助数组closedge，用来记录从集合U到集合V-U具有最小权值的边。对每个属于V-U集合的顶点，在辅助数组中存在一个相应的分量closedge[i-1]，它包括两个域，一个域用来表示在该顶点与V-U集合中某些顶点构成的边中权最小的那条边的权值，若该顶点进入U集合，则值为0；另一个域表示这条最小权值的边对应的在V-U集合中的顶点下标。其类型定义如下所示： #defineMAX_NUM10struct{intadjvex;floatlowcist;}closedge[MAX_NUM];整个算法的执行过程可以描述为： {初始化closedge数组的内容；选择某个顶点k作为生成树的根结点，并将它加入到U集合中；重复下列操作n-1次：l选择一条满足条件的边；l输出这条边的两个端点；l修改V-U集合中的顶点信息，即与U集合中构成最小权值的边。}假设该网以邻接矩阵的形式给出，则完整的算法为： voidMini_SpanTree(GraphG,intk,intn){//G是网的邻接矩阵，k是生成树根结点的序号，n是网的顶点数目for(j=0;j<n;j++)if(j!=k)closedge[j]={k,G[k][j]};closedge[k]lowcost=0;for(i=1;i<n;i++){k=minmun(closedge);printf(k,closedge[k]adjvex);closedge[k]lowcost=0;//将顶点加入U集合中for(j=0;j<n;j++)if(closedge&&G[k][j]<closedge[j]lowcost)closedge[j]={k,G[k][j]};}}

不总是一样的，克鲁斯卡尔算法是精确算法，即每次都能求得最优解，但对于规模较大的最小生成树问题，求解速度较慢。而普里姆算法是近似求解算法，虽然对于大多数最小生成树问题都能求得最优解，但相当一部分求得的是近似最优解。这是我个人见解。

避圈法，从网络图中任意节点开始寻找与该节点关联的权数最小的边，使之与已选边不构成为圈，直到选够n-1条边为止。避圈法则采取先将图中的点都取出来，然后，逐渐向上面添边，并保证后添入的边不与以前添上的边构成圈就可以了，这个过程直到将边集中能加入的边（加入后不够成圈）都加完为止。

破圈法，在网络图中寻找一个圈。若不存在圈，则已经得到最短树或网络不存在最短树；去掉该圈中权数最大的边；反复重复前两步，直到最小树。

破圈法为“见圈破圈”，即如果看到图中有一个圈，就将这个圈的边去掉一条，直至图中再无一圈为止。

扩展资料

无圈且连通的无向图称为树。树一般记为T。作为树定义还可以有以下几种表述：T连通且无圈或回路；T无圈且有n-1条边（如果有n个结点）；T连通有n-1条边；T无回路，但不相邻的两个结点之间联以一边，恰得一个圈。

T连通，但去掉T的任意一条边，T 就不连通了；（亦即在点集合相同的图中，树是含边数最少的连通图）。T的任意两个结点之间恰有一条初等链。

-最小树形图问题

-破圈法

首先看一下深度优先和广度优先怎么遍历：

深度优先遍历从某个顶点出发，首先访问这个顶点，然后找出刚访问这个结点的第一个未被访问的邻结点，然后再以此邻结点为顶点，继续找它的下一个新的顶点进行访问，重复此步骤，直到所有结点都被访问完为止。

广度优先遍历从某个顶点出发，首先访问这个顶点，然后找出这个结点的所有未被访问的邻接点，访问完后再访问这些结点中第一个邻接点的所有结点，重复此方法，直到所有结点都被访问完为止。

在看题目，其要求按顺时针方向：

深度优先序列：v1 v2 v3 v5 v4

广度优先序列：v1 v2 v4 v3 v5

最小生成树，有两种方法，prim和kruskal算法。

这题最小生成树如下：

[(v4,v5),(v1,v4),(v2,v4),(v5,v3)],其中（v4,v5）表示v4和v5点之间连线。如下图类似（这里简单表示一下）。

v1 v2 v3

\ / /

v4----v5

图的最小生成树与最短路径的算法

一、图的生成树与最小生成树

在一个连通图G中，如果取它的全部顶点和一部分边构成一个子图G’，即：

若边集E（G’）中的边既将图中的所有顶点连通又不形成回路，则称子图G’是原图G的一棵生成树。

最小生成树：给图中每个边赋一权值，所有生成树中所选择边的权值之和最小的生成树，称之为最小代价生成树，即是最小生成树。

1、普里姆算法

11算法描述

假设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就是最后得到的最小生成树。 12关键问题

普里姆算法的关键之处是：每次如何从生成树T中到T外的所有边中，找出一条最短边。例如，在第k次前，生成树T中已有k个顶点和（k-1）条边，此时T中到T外的所有边数为k（n-k），当然它包括两顶点间没有直接边相连，其权值被看作为“无穷大”的边在内，从如此多的边中查找最短边，其时间复杂性为O（k（n-k）），显然是很费时的。是否有一种好的方法能够降低查找最短边的时间复杂性呢？ 13 解决方法

方法是：假定在进行第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）。

14 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 painterEvery 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 pictureEddy 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

10 10

20 20

20 40

Sample Output：

341

2、克鲁斯卡尔算法

21 算法描述

假设G＝（V，E）是一个具有n个顶点的连通网，T＝（U，TE）是G的最小生成树，U的初值等于V，即包含有G中的全部顶点，TE的初值为空。此算法的基本思想是，将图G中的边按权值从小到大的顺序依次选取，若选取的边使生成树T不形成回路，则把它并入TE中，保留作为T的一条边，若选取的边使生成树T形成回路，则将其舍弃，如此进行下去，直到TE中包含有n-1条边为止。此时的T即为最小生成树。

22 关键问题

克鲁斯卡尔算法的关键之处是：如何判断欲加入的一条边是否与生成树中已选取的边形成回路。这可将各顶点划分为所属集合的方法来解决，每个集合中的顶点表示一个无回路的连通分量。算法开始时，由于生成树的顶点集等于图G的顶点集，边集为空，所以n个顶点分属于n个集合。每个集合中只有一个顶点，表明顶点之问互不连通。

23 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;

24 注意：

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、从一顶点到其余各顶点的最短路径

11 描述

迪杰斯特拉（Dijkstra）于1959年提出了解决此问题的一般算法，具体做法是按照从源点到其余每一顶点的最短路径长度的升序依次求出从源点到各顶点的最短路径及长度，每次求出从源点vi到一个终点vj的最短路径及长度后，都要以vj作为新考虑的中间点，用vi到vj的最短路径和最短路径长度对vi到其它尚未求出最短路径的那些终点的当前路径及长度作必要的修改，使之成为当前新的最短路径和最短路径长度，当进行n-2次后算法结束。

12 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至少有两条不同路径)

输入输出样例

routein

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

routeout

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

问题一：什么是最小生成树[详细]？？ 令到图中所有节点都连通的最小代价。就是最小生成树简单点说有几个城市你要设计一个路线 这个路线能走完所有的这几个城市 而且路程最短 这个路线就是最小生成树的含义

问题二：最小生成树求出来之后怎么求树的代价呢？ 各个节点的权乘以它的深度在相加。权就是节点上的数字

问题三：图G 的一棵最小代价生成树的代价未必小于G 的其他任何一棵生成树的代价，这个是否正确，为什么 最小代价生成树的代价就是最小的，值只不过对于这个找穿小代价生成树的问题是个NPC的，所以用近似算法得到的最小代价生成树不是最优的

问题四：什么是最小生成树？ 最小生成树

1、 最小生成树

对于连通的带权图(连通网)G，其生成树也是带权的。生成树T各边的权值总和称为该树的权，记作：

这里:

TE表示T的边集

w(u，v)表示边(u，v)的权。

权最小的生成树称为G的最小生成树(Minimum SpannirngTree)。最小生成树可简记为MST。

2、生成树和最小生成树的应用

生成树和最小生成树有许多重要的应用。

例网络G表示n各城市之间的通信线路网线路（其中顶点表示城市，边表示两个城市之间的通信线路，边上的权值表示线路的长度或造价。可通过求该网络的最小生成树达到求解通信线路或总代价最小的最佳方案。

3、最小生成树性质（MST性质）

（1）MST性质

最小生成树性质：设G=(V，E)是一个连通网络，U是顶点集V的一个真子集。若(u，v)是G中所有的一个端点在U(u∈U)里、另一个端点不在U(即v∈V-U)里的边中，具有最小权值的一条边，则一定存在G的一棵最小生成树包括此边(u，v)。

问题五：最小生成树是否唯一求解答 摘要：最小生成树是图论的经典问题，求最小生成树以及求最小生成树的权值和得到了足够关注，而很少人去研究。对于给定的图而言，因为最小生成树的权值和是确定的，所以最小生成树不唯一当且仅当最小生成树的形状不唯一。本文提出判断的三种方法并且对它们给予分析和评价。关键词：最小生成树；唯一；prim算法；kruskal算法；次小生成树中图分类号：TP3016 文献标识码：A文章编号：1007-9599 (2011)06-0000-02Minimum Spanning Tree If the Unique Wu Yuliang,Kong Fanlong(Central China Normal University,Wuhan430079,China)Abstract:Minimum spanning tree is a classic problem of graph theory,find the minimum spanning tree minimum spanning tree,and find the weight and get enough attention,and few people to study the minimum spanning tree is uniqueFor a given graph is concerned,because the weights and the minimum spanning tree is determined,so the minimum spanning tree is not unique and only if the shape of the minimum spanning tree is not uniqueDetermine whether the proposed minimum spanning tree,and the only three ways to give their ysis and evaluationKeywords:Minimum spanning tree;Unique;Prim algorithm;Kruskal algorithm;Small spanning tree一、三种方法判断最小生成树(MST)是否唯一（一）借助prim算法提出的方法prim算法的基本思想是：首先选取图中的任意一个顶点v作为树的根加入生成树的 Q中，之后不断往生成树中( Q中)添加顶点w，顶点w满足与 Q中的某个顶点之间有边，且该边上的权值是此时所有连接 Q中的结点与不在 Q中的结点的边中权值最小的，如此加入n-1个结点后，就形成了MST。（剩余3202字）