最小生成树问题 - JAVA

假设要在n个城市之间建立通信网，则联通n个城市只需要n-1条线路，这是，自然会考虑如何在最节省经费的前提下建立这个通信网，这就是经典的最小生成树问题。

构造最小生成树有多种算法，多数利用最小生成树的MST性质，此处以普里姆算法为例。

MST性质：

N={V, {E}}是连通网, V顶点集合, E边的集合,

TE是N上最小生成树中边的集合

从U = {u0} (U0属于V)，TE = { } 开始，重复执行下列错做：

在所有u属于V，v属于V-U的边（u, v）属于E中找一条代价最小的边(u0, v0)并入集合TE ,同时v0并入U,直至U=V为止，此时TE中必有n-1条边，则T = {U, {TE}}为最小生成树。

此处以数组法表示的无向网构造最小生成树，用邻接表示法表示的网算法与此类似。

首先构造一个无向网，再用该无向网从第0个顶点出发构造一棵最小生成树。

无向网G

构造后的最小生成扫ky"http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vc8L3A+CjxwPjxpbWcgc3JjPQ=="https://www.cppentry.com/upload_files/article/76/1_if4sl__.jpg" alt="\">

#include 
  
   

#define MAX 20 //最大顶点数

typedef struct ArcCell //无向网中的弧
{
    int adj; //弧的权值
}ArcCell, AdjMatrix[MAX][MAX];

typedef struct MGraph //数组表示法表示图
{
    char vexs[MAX]; //顶点值
    AdjMatrix arcs; //临接矩阵
    int vexnum; //顶点数
    int arcnum; //弧数
}MGraph;

typedef struct Arc //生成树中的弧
{
    int fir; //生成树中表示弧的第一个顶点
    int sec; //生成树中表示弧的第二个顶点
    int weight; //弧的权值
}Arc;

typedef struct Vex //生成树中的顶点
{
    char value; //存放顶点值
}Vex;

typedef struct MiniTree //最小生成树
{
    Arc arcs[MAX]; //弧
    Vex vexs[MAX]; //顶点
    int vexnum; //顶点数
    int arcnum; //弧数
}MiniTree;

typedef enum Bool{FALSE, TRUE} Bool;
typedef struct Temp  //辅助结构
{
    int pos; //存放顶点编号
    int lowcost; //存放最小值
    Bool visited; //访问标志
}Temp;

//确定输入的顶点值在无向网中的位置
int LocateVex(MGraph **G, char c)
{
    int i;
    for(i=0; i<(*G)->vexnum; i++)
    {
        if((*G)->vexs[i] == c)
	    return i;
    }
    return -1;
}

//数组表示法构造无向网
void CreateUDN(MGraph *G)
{
    int i, j, k;
    
    printf("Input vexnum and arcnum:\n"); //提示输入顶点数和弧数
    scanf("%d", &(G->vexnum));getchar();
    scanf("%d", &(G->arcnum));getchar();
    
    printf("Input vex's value:\n"); //输入顶点值
    for(i=0; i
   
    vexnum; i++) { scanf("%c", &(G->vexs[i])); getchar(); } for(i=0; i
    
     vexnum; i++) //初始化临接矩阵 { for(j=0; j
     
      vexnum; j++) G->arcs[i][j].adj = 0; } printf("Input %d arc\n", G->arcnum); for(k=0; k
      
       arcnum; k++) { char v1, v2; //两个顶点值 int w; //两个顶点间的权值 scanf("%c %c %d", &v1, &v2, &w); getchar(); i = LocateVex(&G,v1); j = LocateVex(&G,v2); G->arcs[i][j].adj = G->arcs[j][i].adj = w; } } //选出辅助数组中未访问的非0最小值 int selectMin(Temp *temp, MiniTree **mt) { //找到第一个不为0的元素，设为最小值 int i, min; for(i=0; i<(*mt)->vexnum; i++) { if(temp[i].lowcost != 0 && temp[i].visited == FALSE) break; } min = i; for(i=0; i<(*mt)->vexnum; i++) { if(temp[i].lowcost !=0 && temp[i].visited == FALSE) { if(temp[min].lowcost > temp[i].lowcost) min = i; } } return min; } //以无向网为例，从第u个顶点出发，构造最小生成树 void CreateMiniTree(MGraph *G, int u, MiniTree *mt) { int i, j, k; Temp temp[MAX]; mt->vexnum = G->vexnum; mt->arcnum = mt->vexnum - 1; for(i=0; i
       
        vexnum; i++) //辅助数组初始化 { if(i != u) { Temp t = {u, G->arcs[u][i].adj, FALSE}; temp[i] = t; } } Temp t = {u, 0, TRUE}; temp[u] = t; for(i=1; i
        
         vexnum; i++) { k = selectMin(temp, &mt); mt->arcs[i-1].fir = temp[k].pos; mt->arcs[i-1].sec = k; mt->arcs[i-1].weight = temp[k].lowcost; temp[k].lowcost = 0; //第k个顶点并入U temp[k].visited = TRUE; //开始调整下一行,保留存在路径的较小值及顶点值，保留之前lowcost为0后来存在路径的新值及顶点值 for(j=0; j
         
          vexnum; j++) { if(temp[j].visited == FALSE) { if(temp[j].lowcost != 0) { if(G->arcs[k][j].adj < temp[j].lowcost && G->arcs[k][j].adj != 0) { Temp t = {k, G->arcs[k][j].adj, FALSE}; temp[j] = t; } } else { if(G->arcs[k][j].adj != 0) { Temp t = {k, G->arcs[k][j].adj, FALSE}; temp[j] = t; } } } } } } int main() { int i, j, k; MGraph G; MiniTree mt; CreateUDN(&G); //构造无向网G for(i=0; i
           
            
           
  测试数据 
           
  
           输入G的顶点数和边数 
           
 
  
           输入G的顶点值，此处以1代表v1，2代表v2，以此类推 
           
  
           
  
           输入表示弧的两个顶点的编号以及弧的权值 
           
  
           
  
           显示构造的无向网G的各个顶点值 ,此处以1代

最小生成树问题(一)