| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2648 人关注过本帖
标题:求大神帮我改下这个程序,prim算法求最小生成树的,谢谢
取消只看楼主 加入收藏
夙愿000000
Rank: 1
来 自:甘肃张掖
等 级:新手上路
帖 子:10
专家分:0
注 册:2016-4-10
结帖率:50%
收藏
已结贴  问题点数:10 回复次数:0 
求大神帮我改下这个程序,prim算法求最小生成树的,谢谢
#include<iostream.h>
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#define Max 30
typedef struct
{
    int quanzhi;
}leixing[Max][Max];
typedef struct
{
    int dingdian[Max];
    leixing juzhen;
    int dianshu,bianshu;
}Graph;
struct
{
    int adjvex;
    int lowcost;
}closedge[Max];
void Creat(Graph *G)
{
    int i,j,e,w;
    cout<<"请输入点数和边数:";
    cin>>(*G).dianshu>>(*G).bianshu;
    for(i=0;i<(*G).dianshu;i++)
        cin>>(*G).dingdian[i];
    for(i=0;i<(*G).dianshu;i++)
        for(j=0;j<(*G).dianshu;j++)
            (*G).juzhen[i][j].quanzhi=0;
    for(e=0;e<(*G).bianshu;e++)
    {
        cout<<"请输入边(i,j)及边上的权值w:";
        cin>>i>>j>>w;
        (*G).juzhen[i][j].quanzhi=(*G).juzhen[j][i].quanzhi=w;
    }
}
void display(Graph *G)
{
    int i,j;
    cout<<"城市编号名:"<<endl;
    for(i=0;i<(*G).dianshu;i++)
        cout<<(*G).dingdian[i]<<"  ";
    cout<<endl;
    cout<<"该城市的邻接矩阵为:"<<endl;
    for(i=0;i<(*G).dianshu;i++){
        for(j=0;j<(*G).dianshu;j++)
            cout<<(*G).juzhen[i][j].quanzhi<<"   ";
        cout<<endl;
    }
}
int MinNum(Graph *G)
{
    int i,j=0,k=0,min=0;
    for(i=0; i<(*G).dianshu; i++)
    if(closedge[i].lowcost!=0)
    {
        min=closedge[i].lowcost;
        k=i;
        break;
    }
    for(j=i+1;j<(*G).dianshu;j++)
    if(closedge[j].lowcost!=0)
    {
        if(min>=closedge[j].lowcost)
        {
        min=closedge[j].lowcost;
        k=j;
        }
    }
    return k;
}
int VerIndex(Graph *G,int v)
{
    int i;
    for(i=0;i<(*G).dianshu;i++)
        if((*G).dingdian[i]==v)
            return i;
        return -1;
}
void Prim(Graph *G,char v)
{
    int i,j,k;
    k=VerIndex(G,v);
    for(i=0;i<(*G).dianshu;i++)
        if(i!=k)
        {
            closedge[i].lowcost=(*G).juzhen[k][i].quanzhi;
            closedge[i].adjvex=k;
        }
        closedge[k].lowcost=0;
    for(i=0;i<(*G).dianshu;i++)
    {
        k=MinNum(G);
        cout<<closedge[k].adjvex<<"--"<<(*G).dingdian[k]<<endl;
        closedge[k].lowcost=0;
    }
    for(j=0;j<(*G).dianshu;j++)
        if((*G).juzhen[k][j].quanzhi<closedge[j].lowcost)
        {
            closedge[j].lowcost=(*G).juzhen[k][j].quanzhi;
            closedge[j].adjvex=k;
        }
}
int main()
{
    Graph G;
    int v;
    Creat(&G);
    display(&G);
    cout<<"请输入出发点:";
    cin>>v;
    Prim(&G,v);
    return 0;
}
搜索更多相关主题的帖子: include 
2016-07-07 16:30
快速回复:求大神帮我改下这个程序,prim算法求最小生成树的,谢谢
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.016778 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved