您的位置:威尼斯官方网站 > 威尼斯正规官网 > 数据结构之---C语言达成最小生成树之prim(普Ri

数据结构之---C语言达成最小生成树之prim(普Ri

发布时间:2019-08-24 19:00编辑:威尼斯正规官网浏览(71)

    数据结构之---C语言实现最小生成树之prim(普Rim)算法

    图片 1

     

     

     

     

    //最小生成树之Prim算法
    //杨鑫
    #include 
    #include 
    #define n 6
    #define MaxNum 10000  /*定义一个最大整数*/
    
    /*定义邻接矩阵类型*/
    typedef int adjmatrix[n   1][n   1];   /*0号单元没用*/
    typedef struct
    {
     int fromvex, tovex;         //生成树的起点和终点        
     int weight;       //边的权重
    }Edge;
    typedef Edge *EdgeNode;     //定义生成树的别名
    int arcnum;     /*边的个数*/
    
    /*建立图的邻接矩阵*/
    void CreatMatrix(adjmatrix GA)
    {
     int i, j, k, e;
     printf(=============================
    );
     printf(图中有%d个顶点
    , n);
     for(i=1; i<=n; i  )
     {
      for(j=1; j<=n; j  )
      {
       if(i==j)
       {
        GA[i][j]=0;         /*对角线的值置为0*/
       }
       else
       {
        GA[i][j]=MaxNum;    /*其它位置的值置初始化为一个最大整数*/
       }
      }
     }
     printf(请输入边的个数:
    );
     scanf(%d, &arcnum);
     printf(请输入边的信息,按照起点,终点,权值的形式输入:
    );
     for(k=1;k<=arcnum;k  )
     {
      scanf(%d,%d,%d,&i,&j,&e);  /*读入边的信息*/
      GA[i][j]=e;
      GA[j][i]=e;
     }
    }
    
    /*初始化图的边集数组*/
    void InitEdge(EdgeNode GE,int m)
    {
     int i;
     for(i=1;i<=m;i  )
     {
      GE[i].weight=0;
     }
    }
    
    /*根据图的邻接矩阵生成图的边集数组*/
    void GetEdgeSet(adjmatrix GA,EdgeNode GE)
    {
     int i, j, k = 1;
     for(i=1;i<=n;i  )
     {
      for(j=i 1;j<=n;j  )
      {
       if(GA[i][j] !=0 && GA[i][j] != MaxNum)
       {
        GE[k].fromvex = i;
        GE[k].tovex = j;
        GE[k].weight = GA[i][j];
        k  ;
       }
      }
     }
    }
    
    /*按升序排列图的边集数组*/
    void SortEdge(EdgeNode GE,int m)
    {
     int i,j,k;
     Edge temp;
     for(i=1;i GE[j].weight)
       {
        k=j;
       }
      }
      if(k!=i)
      {
       temp = GE[i];
       GE[i]=GE[k];
       GE[k]=temp;
      }
     }
    }
    
    /*利用普里姆算法从初始点v出发求邻接矩阵表示的图的最小生成树*/
    void Prim(adjmatrix GA,EdgeNode T)
    {
     int i,j,k,min,u,m,w;
     Edge temp;
     /*给T赋初值,对应为v1依次到其余各顶点的边*/
     k=1;
     for(i=1;i<=n;i  )
     {
      if(i!=1)
      {
       T[k].fromvex=1;
       T[k].tovex=i;
       T[k].weight=GA[1][i];
       k  ;
      }
     }
     /*进行n-1次循环,每次求出最小生成树中的第k条边*/
     for(k=1;k  结果: 
    

    //最小生成树之Prim算法//杨鑫#include #include #define n 6#define MaxNum 10000 /*概念一个最大...

    本文由威尼斯官方网站发布于威尼斯正规官网,转载请注明出处:数据结构之---C语言达成最小生成树之prim(普Ri

    关键词:

上一篇:然后射击(即使气球在飞船的正上方)

下一篇:没有了