| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2644 人关注过本帖
标题:求大神帮我改下这个程序,prim算法求最小生成树的,谢谢
只看楼主 加入收藏
夙愿000000
Rank: 1
来 自:甘肃张掖
等 级:新手上路
帖 子:10
专家分:0
注 册:2016-4-10
结帖率:50%
收藏
已结贴  问题点数:10 回复次数:1 
求大神帮我改下这个程序,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
书生牛犊
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:星夜征程
等 级:贵宾
威 望:10
帖 子:1101
专家分:5265
注 册:2015-10-27
收藏
得分:0 
对不起,你这是C++,我没学过。。看不太懂誒。。。
不知道你是Prim算法出了问题还是语法的,由于缺少iostream(C++标准输入输出流头文件),我也不能调试运行。
我是用C的,勉强找了一些不是问题的问题。
第一,Create()函数里,你在初始化哥哥边的权值时是赋零,那么零权值能代表两个顶点是不连通的吗?我记得我学的时候老师是说要赋“无穷大”,(一个不可能的足够大的数,或者-1)
第二,Prim()的部分我虽然不能完全理解,但感觉怪怪的,只有三个独立的一层循环,可以吗?
Prim*()的工作原理是从图上任意一点出发,找到花销最小的一个顶点链接它并把它收入地图,然后找到和这两个点钟任意一个相连的,花销最小的把它收入地图,,以此类推,直到地图收录了所有顶点。
那么第一,你要有这样一个数组或者别的机制来用来记录每次访问过的位置。第二你每次去找最短边的时候应该是从所有已经收入地图的顶点出发(这里至少得用一个两层循环)。

我不知道是不是题目要求你用邻接矩阵来存储这些数据(你这貌似也不算邻接矩阵,邻接矩阵应该就一个二维数组,没这么复杂),反正下面这一部分内存开销蛮大的。
typedef struct
{
    int quanzhi;
}leixing[Max][Max];
而且每次要找最小边也得遍历所有的边,太麻烦了。一种更好的方案是用链表。然后在读取数据的时候就直接把从每个点出发的边按照权值从小到大挂下去,以后每次要找顶点的最小边就直接知道是在表头,取出就能用,用过 就free。
--------------------------------------------------------------------------------------------
当然了,前面那么多都是废话,因为我不会用C++啦,还是建议你把帖子发表到C++论坛,那里的人气也更活跃,可以帮你指出问题症结。

φ(゜▽゜*)♪
2016-07-09 13:06
书生牛犊
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:星夜征程
等 级:贵宾
威 望:10
帖 子:1101
专家分:5265
注 册:2015-10-27
收藏
得分:10 
下文附我写的C语言的Prim

程序代码:
#include<stdlib.h>
#include<stdio.h>

/*

 评测结果 时间     结果     得分     题目     编译器     用时(ms)     内存(MB)     用户
2016-04-18 16:57     答案正确     30     08-图7     gcc     41     5     569985011
测试点结果 测试点     结果     得分/满分     用时(ms)     内存(MB)     要点提示
测试点1     答案正确     15/15     1     1     sample换数字,各种回路判断
测试点2     答案正确     2/2     2     1     M<N-1,不可能有生成树
测试点3     答案正确     2/2     1     1     M达到N-1,但是图不连通
测试点4     答案正确     5/5     41     5     最大N和M,连通
测试点5     答案正确     6/6     14     5     最大N和M,不连通
*/
struct data {
    int VerNode,Coast;
};
typedef struct LNode* Vertex;
struct LNode {
    struct data a[1001];
    int Left,Right;
};
void InsertV(Vertex,int ,int,int);
int Prim(Vertex ,int );
Vertex CreatV(int);
int Comp(const void*a,const void*b) {
    struct data x=*(struct data *)a;
    struct data y=*(struct data *)b;
    return x.Coast - y.Coast ;
}

int main() {
    int N,M;
    scanf("%d%d",&N,&M);
    Vertex V=CreatV(N+1);

    int from,to,lenth;
    for(int i=0; i<M; i++) {
        scanf("%d%d%d",&from,&to,&lenth);
        InsertV(V,from,to,lenth);
    }
    for(int i=1; i<=N; i++) {
        qsort(V[i].a,V[i].Right-V[i].Left,sizeof(struct data),Comp);
//        printf("%d",i);
//        for(int j=V[i].Left;j<V[i].Right ;j++){
//            printf("{-%d=%d}",V[i].a[j].VerNode,V[i].a[j].Coast  );
//        }printf("\n");
    }
   

    printf("%d",Prim(V,N));
    return 0;
}

int Prim(Vertex V,int N) {
    int right=0,left=0,Node[1001],Coast=0;
    for(int i=1; i<=N; i++) {
        if(V[i].Right >V[i].Left) {
            if(right) {
                if(V[i].a[0].Coast <V[Node[0]].a[0].Coast) {
                    Node[0]=i;
                }
            } else {
                Node[right++]=i;
            }

        }
    }
    Coast+=V[Node[0]].a[0].Coast ;

    Node[right++]=V[Node[0]].a[0].VerNode;
    V[Node[0]].Left ++;
//    printf("-%d-",right);
    while(right<N) {
        int flag=-1;
        for(int i=0; i<right; i++) {
            if(V[Node[i]].Left<V[Node[i]].Right) {
                if(flag!=-1) {
                    if(V[Node[i]].a[V[Node[i]].Left].Coast <V[Node[flag]].a[V[Node[flag]].Left ].Coast)
                        flag=i;
                } else {
                    flag=i;
                }
            }
        }
        if(-1==flag)break;
        int i;
        for(i=0;i<right;i++){
            if(V[Node[flag]].a[V[Node[flag]].Left].VerNode==Node[i])break;
        }
        if(i==right){
            Node[right++]=V[Node[flag]].a[V[Node[flag]].Left].VerNode;
            Coast+=V[Node[flag]].a[V[Node[flag]].Left].Coast ;
        }
        V[Node[flag]].Left++;
    }
    for(int i=0;i<right;i++){
//        printf("[%d]",Node[i]);
    }
if(right>=N)return Coast;
    else return -1;
}

Vertex CreatV(int num) {
    Vertex V=(Vertex)malloc(sizeof(struct LNode)*num);
    for(int i=0; i<num; i++) {
        V[i].Left =0;
        V[i].Right =0;
    }

    return V;
}
void InsertV(Vertex V,int from,int to,int lenth) {
    V[from].a[V[from].Right].Coast =lenth;
    V[from].a[V[from].Right++].VerNode =to;
    V[to].a[V[to].Right].Coast =lenth;
    V[to].a[V[to].Right++].VerNode =from;
}


φ(゜▽゜*)♪
2016-07-09 13:07
快速回复:求大神帮我改下这个程序,prim算法求最小生成树的,谢谢
数据加载中...
 
   



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

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