最小生成树prime算法输出异常，求教

最小生成树prime算法输出错误，求教！
graph.h

#ifndef GRAPH_H_INCLUDED
#define GRAPH_H_INCLUDED

#define  MAXVEX   100  /**< 最多顶点数 */
#define  INFINITY    65535/**< 不存在该边是的权值 */

struct  graph;
typedef  struct  graph  *Graph;
typedef  int  VertexType;
typedef  int     EdgeType;

struct   graph
{
    VertexType   vertex[MAXVEX];
    EdgeType   edge[MAXVEX][MAXVEX];
    int   numvertex,numedge;
};

void  CreatGraph(Graph  G);/**< 创建图 */
void  PrintGraph(Graph  G);/**<  将图一临街矩阵的形式打印出来*/
void  Prime(Graph  G);/**< 最小生成树算法 */

#endif // GRAPH_H_INCLUDED

graph.c

#include  <stdio.h>
#include  "graph.h"


void  CreatGraph(Graph  G)
{
    int  i,j,k,w;

    printf("input  the  number  of vertex ang  edge:\n");
    printf("the number of  vertex :");
    scanf("%d",&G->numvertex);
    printf("\n");
    printf("the number of edge:");
    scanf("%d",&G->numedge);

    /**< 输入顶点 */
    for(i=0;i<G->numvertex;i++)
    {
           scanf("%d",&G->vertex[i]);
    }


    /**< 矩阵初始化 */
    for(i=0;i<G->numvertex;i++)
    {
        for(j=0;j<G->numedge;j++)
        {
            G->edge[i][j] = INFINITY;
        }
    }

    /**< 输入边的权值此处一边控制循环次数 */
    for(k=0;k<G->numedge;k++)
    {
        printf("input     vertex  and weight:\n");
        scanf("%d %d %d",&i,&j,&w);
        G->edge[i][j] = w;
        G->edge[j][i] =G->edge[i][j];

    }
}

void  PrintGraph(Graph  G)
{
    int  i,j;

    for(i=0;i<G->numvertex;i++)
    {
        for(j=0;j<G->numedge;j++)
        {
            if(G->edge[i][j] == INFINITY)
                printf("\t**");
            else
                printf("\t%d",G->edge[i][j]);
        }
        printf("\n");
    }
}


void  Prime(Graph  G)
{
      int  min,i,j,k;

      int  adjvertex[MAXVEX];/**< 邻接点数组 */
      int  lowcost[MAXVEX];/**< 值为零表示该点已加入最小生成树 */

      lowcost[0] = 0;
      adjvertex[0] = 0;

      /**< 初始化辅助数组 */
      for(i=1;i<G->numvertex;i++)
      {
          lowcost[i] = 0;
          adjvertex[i] = 0;
      }

      /**< 主循环，不断更换两个数组的值直到lowcost全为零 */
      for(i=1;i<G->numvertex;i++)
      {
          min = INFINITY;

          j=1,k=0;
      /**< 循环全部顶点 */
          while(j<G->numvertex)
          {
              if(lowcost[j] != 0  && lowcost[j] < min)
              {
                  min=lowcost[j];          /**< 求出当前最小权值存入K中 */ 
 
                  k=j;
              }
              j++;
          }

          printf("(%d,%d)",adjvertex[k],k);    /**< 打印边 */

          lowcost[k] = 0;             /**< 表示k已加入生成树 */


          /**< 更新adjvertex数组数据，查找所有与K相邻点的最小权值（即邻接矩阵第k行数据） */
          for(j=1;j<G->numvertex;j++)
          {
              if(lowcost[j] != 0 &&  G->edge[k][j] < lowcost[j])
              {
                  lowcost[j] = G->edge[k][j];         /**< 将较小权值存入lowcost */
                  adjvertex[j] =k;             /**< 将k存入邻接数组以备下次循环比较用 */
              }
          }
      }
}

main.c

#include <stdio.h>
#include <stdlib.h>
#include  <malloc.h>
#include  "graph.c"

int main()
{
    Graph  G;
    G=malloc(sizeof(struct graph));

    CreatGraph(G);
    PrintGraph(G);
    Prime(G);

    return 0;
}

输出后全是零，请各位指点一二！ 算法 c
[解决办法]
main函数中的

G=malloc(sizeof(struct graph));

最好改成

G=(Graph)malloc(sizeof(struct graph));

malloc返回的是void *类型，而G是struct graph *类型
至于你说的主要问题，稍后答复
[解决办法]
      /**< 初始化辅助数组 */
      for(i=1;i<G->numvertex;i++)
      {
          lowcost[i] = 0;
          adjvertex[i] = 0;
      }

你一开始所有的点距离已经是0了，那求出来的距离和当然是0。

查看更多 下一篇