pirm算法最小生成树题目是N台电脑,求每个相连,输入矩阵啊a【i】【j】表示i和j连接所需费用我是用个递增序列,求每增加个点后待连接的最小边.#include#includeint r=0队列右端点,l=1左端点,dui[10001]
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/02 03:36:33
![pirm算法最小生成树题目是N台电脑,求每个相连,输入矩阵啊a【i】【j】表示i和j连接所需费用我是用个递增序列,求每增加个点后待连接的最小边.#include#includeint r=0队列右端点,l=1左端点,dui[10001]](/uploads/image/z/11456315-35-5.jpg?t=pirm%E7%AE%97%E6%B3%95%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91%E9%A2%98%E7%9B%AE%E6%98%AFN%E5%8F%B0%E7%94%B5%E8%84%91%2C%E6%B1%82%E6%AF%8F%E4%B8%AA%E7%9B%B8%E8%BF%9E%2C%E8%BE%93%E5%85%A5%E7%9F%A9%E9%98%B5%E5%95%8Aa%E3%80%90i%E3%80%91%E3%80%90j%E3%80%91%E8%A1%A8%E7%A4%BAi%E5%92%8Cj%E8%BF%9E%E6%8E%A5%E6%89%80%E9%9C%80%E8%B4%B9%E7%94%A8%E6%88%91%E6%98%AF%E7%94%A8%E4%B8%AA%E9%80%92%E5%A2%9E%E5%BA%8F%E5%88%97%2C%E6%B1%82%E6%AF%8F%E5%A2%9E%E5%8A%A0%E4%B8%AA%E7%82%B9%E5%90%8E%E5%BE%85%E8%BF%9E%E6%8E%A5%E7%9A%84%E6%9C%80%E5%B0%8F%E8%BE%B9.%23include%23includeint+r%3D0%E9%98%9F%E5%88%97%E5%8F%B3%E7%AB%AF%E7%82%B9%2Cl%3D1%E5%B7%A6%E7%AB%AF%E7%82%B9%2Cdui%5B10001%5D)
pirm算法最小生成树题目是N台电脑,求每个相连,输入矩阵啊a【i】【j】表示i和j连接所需费用我是用个递增序列,求每增加个点后待连接的最小边.#include#includeint r=0队列右端点,l=1左端点,dui[10001]
pirm算法最小生成树
题目是N台电脑,求每个相连,输入矩阵啊a【i】【j】表示i和j连接所需费用
我是用个递增序列,求每增加个点后待连接的最小边.
#include
#include
int r=0队列右端点,l=1左端点,dui[10001]队列,pos[10001]队列里对应的实际电脑编号,i,j,n,a[101][101],q[101]判断着个点是否已经被连过,ans=0答案;
void cha(int x,int y)将新边插入到队列里,维护单调
{
int i;
for(i=r;i>=l-1;i--)
{
if(i==l-1){dui[i+1]=x;pos[i+1]=y;break;}
if(dui[i]>x){dui[i+1]=dui[i];pos[i+1]=pos[i];}
else {dui[i+1]=x;pos[i+1]=y;break;}
}
}
int pai(int x){
int j;
for(j=1;j
pirm算法最小生成树题目是N台电脑,求每个相连,输入矩阵啊a【i】【j】表示i和j连接所需费用我是用个递增序列,求每增加个点后待连接的最小边.#include#includeint r=0队列右端点,l=1左端点,dui[10001]
你要实现还是要解释?
要解释的话,简而言之就是贪心选择某初始点集的最短邻边n-1条,同时避免构成环.
要实现到处都是,比如下面一段C描述:
/*设定一个比较大的整数INF来表示无穷大∞*/
void Prim(int cost[][MAXV],int n,int v)
{ int lowcost[MAXV],min;
int closest[MAXV],i,j,k;
for (i=0;i