最小二叉树prim算法不知道哪里出错?

作者站长头像
站长
· 阅读数 9
#include <stdio.h>
#include <stdlib.h>
#define mvnum 30//最多顶点 
#define maxlent 50 //无穷 //
#define  true 1
#define  false 0
typedef struct AMGragh
{
    char vexs[mvnum];//顶点数组 
    int arc[mvnum][mvnum];//边信息 
    int vexnum,arcnum;//顶点数和边数 
}AMGraph;
struct closedge
{
    char adjbex;//最小边在u中的顶点 
    int lowcost;//最小边权值 
}closedge[mvnum];

int Locatevex(AMGraph *G,char temp)
 {
     for(int i=0;i<G->vexnum;i++)
     {
         if(G->vexs[i]==temp)
         {
            return i;     
         }    
    }
 }
int CreateUDN(AMGraph *G)//图的生成函数 
{
    
    printf("请输入顶点数和边数:\n"); 
    scanf("%d\t%d",&(G->vexnum),&(G->arcnum)); //输入边数 
    
    for(int i=0;i<G->vexnum;i++)//输入顶点 
    {   
        printf("请输入顶点%d\n",i+1);
        scanf("%*c%c",&(G->vexs[i]));
        printf("\n") ;
    }
    
    for(int j=0;j<(G->arcnum);j++)//初始化邻接矩阵 
    {
        for(int i=0;i<(G->arcnum);i++)
        G->arc[i][j]=maxlent;
    }
    
    for(int k=0;k<(G->arcnum);k++)//构造邻接矩阵 
    {
        char v1,v2;
        int i,j,w;
        printf("请输入顶点v1,v2\n\t权值\n");
        scanf("%*c%c%c%d",&v1,&v2,&w);
        i=Locatevex(G,v1);
        j=Locatevex(G,v2);
        G->arc[i][j]=w;
        G->arc[j][i]=w;
    }
    return 0;
}
int Print(AMGraph *G)
 {
     for(int i=0;i<G->vexnum;i++)
        {
            for(int j=0;j<G->vexnum;j++)
            {
                if(G->arc[i][j]<maxlent)
                {
                printf(" %-d",G->arc[i][j]);
                    if(j==2)
                    {
                        printf("\n");
                    }
                    
                }
                else
                {
                printf(" %-d",maxlent);
                    if(j==2)
                    {
                        printf("\n");
                    }
                    
                }
            }
        }
 }
 int visited[mvnum];        
void DFS(AMGraph *G,int i)
{
    int j;
    printf("%c",G->vexs[i]);
    visited[i]=1;
    
     
    for(j=0;j<G->vexnum;j++)
    {
        if(G->arc[i][j]==1&&visited[j]==0)
        {
            DFS(G,j);
        }
    }
    
}

void DFS_AM(AMGraph *G) 
{
    int i;
    
    //初始化"标志"数组为0,代表未访问
    for(i=0;i<G->vexnum;i++)
    {
        visited[i]=0; 
    } 
    
    for(i=0;i<G->vexnum;i++)
    {
        if(visited[i]==0)
        {
            DFS(G,i);//此处的G已经是指针类型,不需要再&G 
        }
    } 
    
}
int Min( closedge , AMGragh G)
{
    int min = maxlent;
    int index = 0;
    for (int i = 0; i < G.vexnum; i++)
    {
        if (closedge[i].lowcost<min && closedge[i].lowcost != 0)            //权值为0的表示已经加入点集合,所以不再遍历
        {
            min = closedge[i].lowcost;
            index = i;
        }
    }
    return index;
}

void MinispanTree_prim(AMGragh G,char u)
{
    int k=Locatevex(G,u);
    for(int j=0;j<G.vexnum;++j)
    {
        if(j!=k)
        closedge[j]={u,arc[k][j]};
    }
    closedge[k].lowcost=0;
    for(int i=0;i<G.vexnum;i++)
    {
        k=Min(closedge[mvnum],G);
        char u0=closedge[k].adjbex;
        char v0=G.vexs[k];
        printf("%*c%c%c",u0,v0);
        closedge[k].lowcost=0;
        for(j=0;j<G.vexnum;j++)
        {
            if(G.arc[k][j]<closedge[j].lowcost)
            closedge[j]={G.vexs[k],G.arc[k][j]};
        }
    }
}

int main() 
{
    AMGraph G;
    printf("建立无向网\n"); 
    CreateUDN(&G);
    printf("输出矩阵G:[][]\n"); 
    Print(&G);   
    printf("\n深度优先遍历\n"); 
    DFS_AM(&G); 
    printf("prim算法构建最小生成树\n");
    printf("请输入起始顶点v");
    int u; 
    scanf("%c",&u);
    MinispanTree_prim(G,u);
    return 0;
}
回复
1个回答
avatar
test
2024-07-04
void MinispanTree_prim(AMGraph G, char u)
{
    int k = Locatevex(&G, u);
    for (int j = 0; j < G.vexnum; ++j)
    {
        if (j != k)
        {
            closedge[j].adjbex = u;
            closedge[j].lowcost = G.arc[k][j];
        }
    }
    closedge[k].lowcost = 0;
    for (int i = 0; i < G.vexnum; i++)
    {
        k = Min(closedge, G);
        char u0 = closedge[k].adjbex;
        char v0 = G.vexs[k];
        printf("%c-%c\n", u0, v0);
        closedge[k].lowcost = 0;
        for (int j = 0; j < G.vexnum; j++)
        {
            if (G.arc[k][j] < closedge[j].lowcost)
            {
                closedge[j].adjbex = G.vexs[k];
                closedge[j].lowcost = G.arc[k][j];
            }
        }
    }
}
回复
likes
适合作为回答的
  • 经过验证的有效解决办法
  • 自己的经验指引,对解决问题有帮助
  • 遵循 Markdown 语法排版,代码语义正确
不该作为回答的
  • 询问内容细节或回复楼层
  • 与题目无关的内容
  • “赞”“顶”“同问”“看手册”“解决了没”等毫无意义的内容