Java、C语言普里姆算法最小生成树

亦凉 2022-04-24 13:24 200阅读 0赞

**目录**

1.生成树的概念

2.普里姆算法最小生成树（Prim）

3.源代码示例

3.1 Java实现

3.2 C语言实现

--------------------

## 1.生成树的概念 ##

（1）子图包含原图全部节点，子图为连通图

（2）在（1）的前提下使子图尽可能的少包含原图中的边

满足以上两点的子图称为原图的生成树。生成树必定包含且仅包含原图的 n - 1 条边

最小生成树：在图的所有生成树中，n - 1 条边上权值和最小的树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70][]

## 2.普里姆算法最小生成树（Prim） ##

G = (V, E)为一连通网。V：网中所有点的集合；E：网中所有带权边的集合

设两个新的集合U，T：

（1）U：存放G的最小生成树的节点

（2）T：存放G的最小生成树的边

Prim算法构造最小生成树步骤：

（1）令集合U的初值为 U = \{ U1 \}（假设构造最小生成树从U1出发）

（2）令集合T的初值为 T = \{ \}

（3）从所有 u ![\\epsilon][epsilon] U，v ![\\epsilon][epsilon] V - U的边中选择具有最小权值的边（u，v），将节点 v 加入 U，边（u，v）加入 T

（4）不断重复步骤（3），直至 U = V 时最小生成树构造完毕。

以上图为例：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 1][]

实现此算法需要设置两个辅助数组：lowcost、adjvex

（1）lowcost：保存集合 V - U 中各节点与集合 U 中各节点构成的边中具有最小权值的边的权值。若lowcost \[ i \]  = 0，表明下标 为 i 的节点已加入集合 U 中

（2）adjvex：保存依附于最小权值边的在集合 U 中的节点

<table> 
 <tbody> 
  <tr> 
   <td style="width:89px;">节点下标</td> 
   <td style="width:56px;">0</td> 
   <td style="width:50px;">1</td> 
   <td style="width:51px;">2</td> 
   <td style="width:56px;">3</td> 
   <td style="width:56px;">4</td> 
   <td style="width:59px;">5</td> 
   <td style="width:203px;">U</td> 
   <td style="width:176px;">V-U</td> 
   <td>K</td> 
  </tr> 
  <tr> 
   <td style="width:89px;">lowcost</td> 
   <td style="width:56px;">0</td> 
   <td style="width:50px;">6</td> 
   <td style="width:51px;">1</td> 
   <td style="width:56px;">5</td> 
   <td style="width:56px;"><img alt="\infty" src="https://private.codecogs.com/gif.latex?%5Cinfty"></td> 
   <td style="width:59px;"><img alt="\infty" src="https://private.codecogs.com/gif.latex?%5Cinfty"></td> 
   <td colspan="1" style="width:203px;">{V1}</td> 
   <td colspan="1" style="width:176px;">{V2，V3，V4，V5，V6}</td> 
   <td colspan="1">2</td> 
  </tr> 
  <tr> 
   <td style="width:89px;">adjvex</td> 
   <td style="width:56px;">&nbsp;</td> 
   <td style="width:50px;">V1</td> 
   <td style="width:51px;">V1</td> 
   <td style="width:56px;">V1</td> 
   <td style="width:56px;">&nbsp;</td> 
   <td style="width:59px;">&nbsp;</td> 
  </tr> 
  <tr> 
   <td style="width:89px;">lowcost</td> 
   <td style="width:56px;">0</td> 
   <td style="width:50px;">5</td> 
   <td style="width:51px;">0</td> 
   <td style="width:56px;">5</td> 
   <td style="width:56px;">6</td> 
   <td style="width:59px;">4</td> 
   <td colspan="1" style="width:203px;">{V1，V3}</td> 
   <td colspan="1" style="width:176px;">{V2，V4，V5，V6}</td> 
   <td colspan="1">5</td> 
  </tr> 
  <tr> 
   <td style="width:89px;">adjvex</td> 
   <td style="width:56px;">&nbsp;</td> 
   <td style="width:50px;">V3</td> 
   <td style="width:51px;">&nbsp;</td> 
   <td style="width:56px;">V3/V1</td> 
   <td style="width:56px;">V3</td> 
   <td style="width:59px;">V3</td> 
  </tr> 
  <tr> 
   <td style="width:89px;">lowcost</td> 
   <td style="width:56px;">0</td> 
   <td style="width:50px;">5</td> 
   <td style="width:51px;">0</td> 
   <td style="width:56px;">2</td> 
   <td style="width:56px;">6</td> 
   <td style="width:59px;">0</td> 
   <td colspan="1" style="width:203px;">{V1，V3，V6}</td> 
   <td colspan="1" style="width:176px;">{V2，V4，V5}</td> 
   <td colspan="1">3</td> 
  </tr> 
  <tr> 
   <td style="width:89px;">adjvex</td> 
   <td style="width:56px;">&nbsp;</td> 
   <td style="width:50px;">V3</td> 
   <td style="width:51px;">&nbsp;</td> 
   <td style="width:56px;">V6</td> 
   <td style="width:56px;">V3/V6</td> 
   <td style="width:59px;">&nbsp;</td> 
  </tr> 
  <tr> 
   <td style="width:89px;">lowcost</td> 
   <td style="width:56px;">0</td> 
   <td style="width:50px;">5</td> 
   <td style="width:51px;">0</td> 
   <td style="width:56px;">0</td> 
   <td style="width:56px;">6</td> 
   <td style="width:59px;">0</td> 
   <td colspan="1" style="width:203px;">{V1，V3，V6，V4}</td> 
   <td colspan="1" style="width:176px;">{V2，V5}</td> 
   <td colspan="1">1</td> 
  </tr> 
  <tr> 
   <td style="width:89px;">adjvex</td> 
   <td style="width:56px;">&nbsp;</td> 
   <td style="width:50px;">V3</td> 
   <td style="width:51px;">&nbsp;</td> 
   <td style="width:56px;">&nbsp;</td> 
   <td style="width:56px;">V3/V6</td> 
   <td style="width:59px;">&nbsp;</td> 
  </tr> 
  <tr> 
   <td style="width:89px;">lowcost</td> 
   <td style="width:56px;">0</td> 
   <td style="width:50px;">0</td> 
   <td style="width:51px;">0</td> 
   <td style="width:56px;">0</td> 
   <td style="width:56px;">3</td> 
   <td style="width:59px;">0</td> 
   <td colspan="1" style="width:203px;">{V1，V3，V6，V4，V2}</td> 
   <td colspan="1" style="width:176px;">{V5}</td> 
   <td colspan="1">4</td> 
  </tr> 
  <tr> 
   <td style="width:89px;">adjvex</td> 
   <td style="width:56px;">&nbsp;</td> 
   <td style="width:50px;">&nbsp;</td> 
   <td style="width:51px;">&nbsp;</td> 
   <td style="width:56px;">&nbsp;</td> 
   <td style="width:56px;">V2</td> 
   <td style="width:59px;">&nbsp;</td> 
  </tr> 
  <tr> 
   <td style="width:89px;">lowcost</td> 
   <td style="width:56px;">0</td> 
   <td style="width:50px;">0</td> 
   <td style="width:51px;">0</td> 
   <td style="width:56px;">0</td> 
   <td style="width:56px;">0</td> 
   <td style="width:59px;">0</td> 
   <td colspan="1" style="width:203px;">{V1，V3，V6，V4，V2，V5}</td> 
   <td colspan="1" style="width:176px;">{}</td> 
   <td colspan="1">&nbsp;</td> 
  </tr> 
  <tr> 
   <td style="width:89px;">adjvex</td> 
   <td style="width:56px;">&nbsp;</td> 
   <td style="width:50px;">&nbsp;</td> 
   <td style="width:51px;">&nbsp;</td> 
   <td style="width:56px;">&nbsp;</td> 
   <td style="width:56px;">&nbsp;</td> 
   <td style="width:59px;">&nbsp;</td> 
  </tr> 
 </tbody> 
</table>

## 3.源代码示例 ##

### 3.1 Java实现 ###

package math_problem;
    
    import java.util.Arrays;
    import java.util.Scanner;
    
    class Graph {
        static final int MAX_VEX_NUM = 20;     // 最大顶点数
        char[] vertex = new char[MAX_VEX_NUM]; // 顶点数组
        int graphType;                         // 图的类型。1-有向图，0-无向图
        int vexNum;                            // 实际顶点数
        int edgeNum;                           // 实际边数
        int[][] edgeWeight = new int[MAX_VEX_NUM][MAX_VEX_NUM];   // 保存边的权值
    }
    
    public class MinimumSpanningTreeDemo {
        static Scanner input = new Scanner(System.in);
        static final int MAXVALUE = Integer.MAX_VALUE;      // 边上最大权值
    
        private static int getIndexOfChar(char[] charArray, char c) {
            for (int i = 0; i < charArray.length; i++) {
                if (c == charArray[i])
                    return i;
            }
            return -1;
        }
    
        private void createGraph(Graph g) {
            int weight;
            char sVex, eVex;// 边的起始、结束顶点
    
            System.out.print("创建图，请输入图的类型（1：有向图/0：无向图)：");
            g.graphType = input.nextInt();
    
            System.out.println("创建图，请输入各顶点信息...");
            System.out.print("请输入顶点数量：");
            g.vexNum = input.nextInt();
            for (int l = 0; l < g.vexNum; l++) {
                System.out.printf("第 %d 个顶点：", l+1);
                g.vertex[l] = (input.next().toCharArray())[0];
            }
    
            System.out.println("创建图，请输入各边顶点及权值...");
            System.out.print("请输入边数量：");
            g.edgeNum = input.nextInt();
    
            // 初始化邻接矩阵
            for (int i = 0; i < g.vexNum; i++) {
                for (int j = 0; j < g.vexNum; j++) {
                    g.edgeWeight[i][j] = MAXVALUE;
                }
            }
    
            System.out.println("请依次输入每条边的信息(起始顶点，结束顶点，权值)：");
            int indexOfsVex, indexOfeVex;
            for (int i = 0; i < g.edgeNum; i++) {
                sVex = input.next().charAt(0);
                eVex = input.next().charAt(0);
                weight = input.nextInt();
    
                indexOfsVex = getIndexOfChar(g.vertex, sVex);
                indexOfeVex = getIndexOfChar(g.vertex, eVex);
                g.edgeWeight[indexOfsVex][indexOfeVex] = weight;
                // 若是无向图，保存边 E（k，j）的权值
                if (g.graphType == 0) {
                    g.edgeWeight[indexOfeVex][indexOfsVex] = weight;
                }
            }
        }
    
        // 输出邻接矩阵
        private void displayAdjMatrix(Graph g) {
            int i, j;
    
            // 先输出顶点信息
            for (i = 0; i < g.vexNum; i++) {
                System.out.printf("\t%c", g.vertex[i]);
            }
            System.out.println();
    
            // 输出邻接矩阵
            for (j = 0; j < g.vexNum; j++) {
                System.out.printf("%c", g.vertex[j]);
                for (i = 0; i < g.vexNum; i++) {
                    if (g.edgeWeight[j][i] == MAXVALUE) {
                        // 权值大于等于最大权值时，输出无穷大的符号
                        System.out.print("\t∞");
                        continue;
                    }
                    System.out.printf("\t%d", g.edgeWeight[j][i]);
                }
                System.out.println();
            }
        }
    
        private static void primMinSpanTree(Graph g) {
            int k = 0, minWeight;
    
            // lowCost：保存集合 V-U 中各节点与集合 U 中各节点构成的边中具有最小权值的边的权值。
            // 若 lowcost[i] = 0，表明下标为 i 的节点已加入集合 U 中
            int[] lowCost = new int[g.vexNum];
            int[] adjVex = new int[g.vexNum];   // 按顺序存放最小生成树的节点
    
            System.out.print("请输入最小生成树开始节点：");
            char startVex = input.next().charAt(0);             // 开始节点
            int sVexIndex = getIndexOfChar(g.vertex, startVex); // 开始节点下标
    
            // 令集合 U 的初值为 U = { U1 }（假设构造最小生成树从 U1 出发）
            adjVex[0] = sVexIndex;
            // 初始化 lowCost 为开始节点与其余各节点边上权值
            for (int i = 0; i < g.vexNum; i++) {
                lowCost[i] = g.edgeWeight[sVexIndex][i];
            }
            lowCost[sVexIndex] = 0;
    
            // 从所有 u ∈ U，v ∈ V-U 的边中选择具有最小权值的边（u，v）
            for (int i = 1; i < g.vexNum; i++) {
                minWeight = MAXVALUE;
                for (int j = 0; j < g.vexNum; j++) {
                    if (lowCost[j] < minWeight && lowCost[j] != 0) {
                        minWeight = lowCost[j];
                        k = j;  // k：记录最小权值边上的节点 v（v ∈ V-U ）的下标
                    }
                }
    
                System.out.printf("顶点：%c ;权值：%d\n", g.vertex[k], minWeight);
                lowCost[k] = 0; // 边（u，v）加入 T
                adjVex[i] = k;  // 将节点 v 加入 U
    
                // 更新集合 V-U 各节点与集合 U 中各节点构成的边中具有最小权值的边的权值
                for (int m = 0; m < g.vexNum; m++) {
                    if (g.edgeWeight[k][m] < lowCost[m])
                        lowCost[m] = g.edgeWeight[k][m];
                }
            }
    
            System.out.print("生成 最小生成树 的节点顺序为：");
            Arrays.stream(adjVex).mapToObj(e -> g.vertex[e] + ", ").forEach(System.out::print);
        }
    
        public static void main(String[] args) {
            Graph graph = new Graph();
            MinimumSpanningTreeDemo demo = new MinimumSpanningTreeDemo();
            demo.createGraph(graph);
            demo.displayAdjMatrix(graph);
            demo.primMinSpanTree(graph);
        }
    }

创建图，请输入图的类型（1：有向图/0：无向图)：0
    创建图，请输入各顶点信息...
    请输入顶点数量：6
    第 1 个顶点：A
    第 2 个顶点：B
    第 3 个顶点：C
    第 4 个顶点：D
    第 5 个顶点：E
    第 6 个顶点：F
    创建图，请输入各边顶点及权值...
    请输入边数量：10
    请依次输入每条边的信息(起始顶点，结束顶点，权值)：
    A B 6
    A C 1
    A D 5
    B C 5
    C D 5
    B E 3
    C E 6
    C F 4
    E F 6
    D F 2
    	A	B	C	D	E	F
    A	∞	6	1	5	∞	∞
    B	6	∞	5	∞	3	∞
    C	1	5	∞	5	6	4
    D	5	∞	5	∞	∞	2
    E	∞	3	6	∞	∞	6
    F	∞	∞	4	2	6	∞
    请输入最小生成树开始节点：A
    顶点：C ;权值：1
    顶点：F ;权值：4
    顶点：D ;权值：2
    顶点：B ;权值：5
    顶点：E ;权值：3
    生成 最小生成树 的节点顺序为：A, C, F, D, B, E, 
    Process finished with exit code 0

### 3.2 C语言实现  ###

#include <stdio.h>
    #include <stdlib.h>
    
    #define INFINITY 10000      /* 假定边上权值无穷大时为10000 */
    #define MAX_VERTEX_NUM 100  /* 图中最大节点数 */
    typedef char VertexType;    /* 顶点类型设置为字符型 */
    typedef int EdgeType;       /* 边上权值类型设置为整型 */
    typedef struct              /* 边表节点 */
    {
        VertexType vex[MAX_VERTEX_NUM];                 /* 图中节点 */
        EdgeType edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; /* 邻接矩阵 */
        int vexnum;                                     /* 节点的数目 */
        int edgenum;                                    /* 边的数目 */
    }MGraph;
     
    void CreateMG(MGraph * MG);         /* 邻接矩阵法创建无向图 */
    void PrintMG(MGraph MG);            /* 邻接矩阵形式输出图MG */
    void MiniSpanTree_Prim(MGraph MG);  /* Prim算法建立最小生成树 */
    void locateVex(MGraph MG, VertexType vex, int * index);
                                        /* 定位节点vex的下标并赋给index */
                                 
    int main(void)
    {
        MGraph g;
     
        CreateMG(&g);
        printf("------------------------------\n");
        printf("vexnum = %d ; edgenum = %d\n", g.vexnum, g.edgenum);
        printf("------------------------------\n");
        PrintMG(g);
        printf("------------------------------\n");
        MiniSpanTree_Prim(g);
    
        return 0;
    }
    void CreateMG(MGraph * MG)
    {
        int i = 0, j, k, w;                 /* w：权值 */
        char ch;
     
        printf("请依次输入顶点数、边数：");
        scanf("%d %d", &(MG->vexnum), &(MG->edgenum));
     
        printf("请依次输入顶点（以回车结束输入）：");
        getchar();
        while ((ch = getchar()) != '\n')    /* 输入顶点信息 */
            MG->vex[i++] = ch;
     
        for (i = 0; i < MG->vexnum; i++)    /* 初始化邻接矩阵 */
            for (j = 0; j < MG->vexnum; j++)
                MG->edges[i][j] = INFINITY;
     
        printf("顶点 | 下标\n");
        for (i = 0; i < MG->vexnum; i++)    /* 显示图中顶点及其对应下标 */
        {
            printf("%3c%6d\n", MG->vex[i], i);
        }
     
        printf("请输入每条边对应的两个顶点下标及边的权值（格式：i j w）：\n");
        for (k = 0; k < MG->edgenum; k++)   /* 建立邻接矩阵 */
        {
            scanf("\n%d%d%d", &i, &j, &w);  /* 输入边的两个节点及权值 */
            MG->edges[i][j] = w;            /* 将矩阵对应位置元素置为权值 */
            MG->edges[j][i] = w;
        }
    }
    void PrintMG(MGraph MG)
    {
        int i, j;
     
        for (i = 0; i < MG.vexnum; i++)         /* 输出邻接矩阵 */
        {
            for (j = 0; j < MG.vexnum; j++)
            {
                if (MG.edges[i][j] == INFINITY) /* 节点不连通时，输出'#'代表无穷大 */
                    printf("%3c", '#');
                else                            /* 节点连通时，输出边上权值 */
                    printf("%3d", MG.edges[i][j]);
            }
            printf("\n");
        }
    }
    void MiniSpanTree_Prim(MGraph MG)
    {
        int i, j, k, index, mincost;        /* index：开始节点下标 */
        int lowcost[MG.vexnum], closevertex[MG.vexnum];
        char ch;                            /* 最小生成树的开始节点 */
    
        printf("请输入开始节点：");
        getchar();
        scanf("%c", &ch);
        locateVex(MG, ch, &index);          /* 求出开始节点的下标并赋给index */
    
        lowcost[index] = 0;
        closevertex[0] = index;             /* 将开始节点加入集合U */
        for (i = 0; i < MG.vexnum; i++)     /* 辅助数组初始化 */
            if (i != index) 
                lowcost[i] = MG.edges[index][i];
        
        for (i = 1; i < MG.vexnum; i++)
        {
            mincost = INFINITY;
            for (j = 0; j < MG.vexnum; j++)
            {
                if (lowcost[j] < mincost && lowcost[j] != 0)
                {
                    mincost = lowcost[j];   /* 最小权值 */
                    k = j;                  /* 权值最小的节点下标 */
                }
            } 
                                            /* 输出当前顶点边中权值最小的边 */
            printf("顶点：%c ;权值：%d\n", MG.vex[k], mincost);
            lowcost[k] = 0;                 /* 将当前顶点的权值设为0，表示此顶点已经完成任务 */
            closevertex[i] = k;             /* 与权值最小边关联的节点下标并入集合U */
    
            for (j = 0; j < MG.vexnum; j++) /* 更新节点与其他节点之间的最小权值和集合U */
            {
                if (MG.edges[k][j] < lowcost[j])
                    lowcost[j] = MG.edges[k][j];
            }
        } 
    } 
    void locateVex(MGraph MG, VertexType vex, int * index)
    {
        int i;
    
        for (i = 0; i < MG.vexnum; i++)
        {
            if (MG.vex[i] == vex)
            {
                *index = i;
                return;
            }
        }
        printf("节点定位失败！\n");
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 2][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70]: /images/20220214/be7c9b9d7a8f4402a2dd6c53fe2b090e.png
[epsilon]: https://private.codecogs.com/gif.latex?%5Cepsilon
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 1]: /images/20220214/1e50bb76960c4e5780679d196ca878ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 2]: /images/20220214/fd8aa9759fbd4c61b9c961a7e3557921.png