prim算法(普里姆算法)详解

这篇具有很好参考价值的文章主要介绍了prim算法(普里姆算法)详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

prim算法(普里姆算法)详解

了解了什么是最小生成树后,本节为您讲解如何用普里姆(prim)算法查找连通网(带权的连通图)中的最小生成树。

普里姆算法查找最小生成树的过程,采用了贪心算法的思想。对于包含 N 个顶点的连通网,普里姆算法每次从连通网中找出一个权值最小的边,这样的操作重复 N-1 次,由 N-1 条权值最小的边组成的生成树就是最小生成树。

那么,如何找出 N-1 条权值最小的边呢?普里姆算法的实现思路是:

将连通网中的所有顶点分为两类(假设为 A 类和 B 类)。初始状态下,所有顶点位于 B 类;

选择任意一个顶点,将其从 B 类移动到 A 类;

从 B 类的所有顶点出发,找出一条连接着 A 类中的某个顶点且权值最小的边,将此边连接着的 A 类中的顶点移动到 B 类;

重复执行第 3 步,直至 B 类中的所有顶点全部移动到 A 类,恰好可以找到 N-1 条边。

举个例子,下图是一个连通网,使用普里姆算法查找最小生成树,需经历以下几个过程:

prim算法,算法,算法,图论,数据结构,prim算法(普里姆算法)详解,c java python

图 1 连通网

  1. 将图中的所有顶点分为 A 类和 B 类,初始状态下,A = {},B = {A, B, C, D, S, T}。

  2. 从 B 类中任选一个顶点,假设选择 S 顶点,将其从 B 类移到 A 类,A = {S},B = {A, B, C, D, T}。从 A 类的 S 顶点出发,到达 B 类中顶点的边有 2 个,分别是 S-A 和 S-C,其中 S-A 边的权值最小,所以选择 S-A 边组成最小生成树,将 A 顶点从 B 类移到 A 类,A = {S, A},B = {B, C, D, T}。

prim算法,算法,算法,图论,数据结构,prim算法(普里姆算法)详解,c java python

图 2 S-A 边组成最小生成树

  1. 从 A 类中的 S、A 顶点出发,到达 B 类中顶点的边有 3 个,分别是 S-C、A-C、A-B,其中 A-C 的权值最小,所以选择 A-C 组成最小生成树,将顶点 C 从 B 类移到 A 类,A = {S, A, C},B = {B, D, T}。

prim算法,算法,算法,图论,数据结构,prim算法(普里姆算法)详解,c java python

图 3 A-C 边组成最小生成树

  1. 从 A 类中的 S、A、C 顶点出发,到达 B 类顶点的边有 S-C、A-B、C-B、C-D,其中 C-D 边的权值最小,所以选择 C-D 组成最小生成树,将顶点 D 从 B 类移到 A 类,A = {S, A, C, D},B = {B, T}。

prim算法,算法,算法,图论,数据结构,prim算法(普里姆算法)详解,c java python

图 4 C-D 边组成最小生成树

  1. 从 A 类中的 S、A、C、D 顶点出发,到达 B 类顶点的边有 A-B、C-B、D-B、D-T,其中 D-B 和 D-T 的权值最小,任选其中的一个,例如选择 D-B 组成最小生成树,将顶点 B 从 B 类移到 A 类,A = {S, A, C, D, B},B = {T}。

prim算法,算法,算法,图论,数据结构,prim算法(普里姆算法)详解,c java python

图 5 D-B 边组成最小生成树

  1. 从 A 类中的 S、A、C、D、B 顶点出发,到达 B 类顶点的边有 B-T、D-T,其中 D-T 的权值最小,选择 D-T 组成最小生成树,将顶点 T 从 B 类移到 A 类,A = {S, A, C, D, B, T},B = {}。

prim算法,算法,算法,图论,数据结构,prim算法(普里姆算法)详解,c java python

图 6 D-T 边组成最小生成树

  1. 由于 B 类中的顶点全部移到了 A 类,因此 S-A、A-C、C-D、D-B、D-T 组成的是一个生成树,而且是一个最小生成树,它的总权值为 17。

prim算法,算法,算法,图论,数据结构,prim算法(普里姆算法)详解,c java python

图 7 最小生成树

普里姆算法的具体实现

接下来,我们将给出实现普里姆算法的 C、Java、Python 程序,程序中有详尽的注释,您可以借助编译器一边运行程序一边观察程序的执行过程,彻底搞清楚普里姆算法是如何找到最小生成树的。

如下是使用普里姆算法在图 1 所示的连通网中查找最小生成树的 C 语言程序:

#include<stdio.h>
#define V 6    // 记录图中顶点的个数
typedef enum { false, true } bool;
//查找权值最小的、尚未被选择的顶点,key 数组记录了各顶点之间的权值数据,visited数组记录着各个顶点是否已经被选择的信息
int min_Key(int key[], bool visited[])
{
    int min = 2147483647, min_index;  //遍历 key 数组使用,min 记录最小的权值,min_index 记录最小权值关联的顶点
    //遍历 key 数组
    for (int v = 0; v < V; v++) {
        //如果当前顶点为被选择,且对应的权值小于 min 值
        if (visited[v] == false && key[v] < min) {
            //更新  min 的值并记录该顶点的位置
            min = key[v];
            min_index = v;
        }
    }
    //返回最小权值的顶点的位置
    return min_index;
}
//输出最小生成树
void print_MST(int parent[], int cost[V][V])
{
    int minCost = 0;
    printf("最小生成树为:\n");
    //遍历 parent 数组
    for (int i = 1; i < V; i++) {
        //parent 数组下标值表示各个顶点,各个下标对应的值为该顶点的父节点
        printf("%d - %d wight:%d\n", parent[i] + 1, i + 1, cost[i][parent[i]]);//由于数组下标从 0 开始,因此输出时各自 +1
        //统计最小生成树的总权值
        minCost += cost[i][parent[i]];
    }
    printf("总权值为:%d", minCost);
}
//根据用户提供了图的信息(存储在 cost 数组中),寻找最小生成树
void find_MST(int cost[V][V])
{    //key 数组用于记录 B 类顶点到 A 类顶点的权值
    //parent 数组用于记录最小生成树中各个顶点父节点的位置,便于最终生成最小生成树
    //visited 数组用于记录各个顶点属于 A 类还是 B 类
    int parent[V], key[V];
    bool visited[V];
    // 初始化 3 个数组
    for (int i = 0; i < V; i++) {
        key[i] = 2147483647;    // 将 key 数组各个位置设置为无限大的数
        visited[i] = false;     // 所有的顶点全部属于 B 类
        parent[i] = -1;         // 所有顶点都没有父节点
    }
    // 选择 key 数组中第一个顶点,开始寻找最小生成树
    key[0] = 0;  // 该顶点对应的权值设为 0
    parent[0] = -1; // 该顶点没有父节点
    // 对于 V 个顶点的图,最需选择 V-1 条路径,即可构成最小生成树
    for (int x = 0; x < V - 1; x++)
    {
        // 从 key 数组中找到权值最小的顶点所在的位置
        int u = min_Key(key, visited);
        // 该顶点划分到 A 类
        visited[u] = true;
        // 由于新顶点加入 A 类,因此需要更新 key 数组中的数据
        for (int v = 0; v < V; v++)
        {
            // 如果类 B 中存在到下标为 u 的顶点的权值比 key 数组中记录的权值还小,表明新顶点的加入,使得类 B 到类 A 顶点的权值有了更好的选择
            if (cost[u][v] != 0 && visited[v] == false && cost[u][v] < key[v])
            {
                // 更新 parent 数组记录的各个顶点父节点的信息
                parent[v] = u;
                // 更新 key 数组
                key[v] = cost[u][v];
            }
        }
    }
    //根据 parent 记录的各个顶点父节点的信息,输出寻找到的最小生成树
    print_MST(parent, cost);
}
// main function
int main()
{
    int p1, p2;
    int wight;
    int cost[V][V] = { 0 };
    printf("输入图(顶点到顶点的路径和权值):\n");
    while (1) {
        scanf("%d %d", &p1, &p2);
        //如果用户输入 -1 -1,表示输入结束
        if (p1 == -1 && p2 == -1) {
            break;
        }
        scanf("%d", &wight);
        cost[p1 - 1][p2 - 1] = wight;
        cost[p2 - 1][p1 - 1] = wight;
    }
    // 根据用户输入的图的信息,寻找最小生成树
    find_MST(cost);
    return 0;
}

如下是使用普里姆算法在图 1 所示的连通网中查找最小生成树的 Java 程序:

import java.util.Scanner;
public class prim {
    static int V = 6;
    public static int min_Key(int []key,boolean []visited) {
        //遍历 key 数组使用,min 记录最小的权值,min_index 记录最小权值关联的顶点
        int min = 2147483647,min_index = 0;
        //遍历 key 数组
        for (int v = 0; v < V; v++) {
            //如果当前顶点为被选择,且对应的权值小于 min 值
            if (visited[v] == false && key[v] < min) {
                //更新  min 的值并记录该顶点的位置
                min = key[v];
                min_index = v;
            }
        }
        //返回最小权值的顶点的位置
        return min_index;  
    }
  
    public static void print_MST(int []parent, int [][]cost) {
        int minCost = 0;
        System.out.println("最小生成树为:");
        //遍历 parent 数组
        for (int i = 1; i < V; i++) {
            //parent 数组下标值表示各个顶点,各个下标对应的值为该顶点的父节点
            System.out.println((parent[i]+1)+" - "+(i+1)+" wight:"+cost[i][parent[i]]);//由于数组下标从 0 开始,因此输出时各自 +1
            //统计最小生成树的总权值
            minCost += cost[i][parent[i]];
        }
        System.out.print("总权值为:"+minCost);
    }
    public static void find_MST(int [][]cost) {
        //key 数组用于记录 B 类顶点到 A 类顶点的权值
        //parent 数组用于记录最小生成树中各个顶点父节点的位置,便于最终生成最小生成树
        //visited 数组用于记录各个顶点属于 A 类还是 B 类
        int []parent = new int[V];
        int []key = new int[V];
        boolean []visited=new boolean[V];
        // 初始化 3 个数组
        for (int i = 0; i < V; i++) {
            key[i] = 2147483647;    // 将 key 数组各个位置设置为无限大的数
            visited[i] = false;     // 所有的顶点全部属于 B 类
            parent[i] = -1;         // 所有顶点都没有父节点
        }
        // 选择 key 数组中第一个顶点,开始寻找最小生成树
        key[0] = 0;  // 该顶点对应的权值设为 0
        parent[0] = -1; // 该顶点没有父节点
        // 对于 V 个顶点的图,最需选择 V-1 条路径,即可构成最小生成树
        for (int x = 0; x < V - 1; x++)
        {
            // 从 key 数组中找到权值最小的顶点所在的位置
            int u = min_Key(key, visited);
            // 该顶点划分到 A 类
            visited[u] = true;
            // 由于新顶点加入 A 类,因此需要更新 key 数组中的数据
            for (int v = 0; v < V; v++)
            {
                // 如果类 B 中存在到下标为 u 的顶点的权值比 key 数组中记录的权值还小,表明新顶点的加入,使得类 B 到类 A 顶点的权值有了更好的选择
                if (cost[u][v] != 0 && visited[v] == false && cost[u][v] < key[v])
                {
                    // 更新 parent 数组记录的各个顶点父节点的信息
                    parent[v] = u;
                    // 更新 key 数组
                    key[v] = cost[u][v];
                }
            }
        }
        //根据 parent 记录的各个顶点父节点的信息,输出寻找到的最小生成树
        print_MST(parent, cost);
    }
    public static void main(String[] args) {
        int [][]cost = new int[V][V];
        System.out.println("输入图(顶点到顶点的路径和权值):");
        Scanner sc = new Scanner(System.in);
        while (true) {
            int p1 = sc.nextInt();
            int p2 = sc.nextInt();
          //  System.out.println(p1+p2);
            if (p1 == -1 && p2 == -1) {
                break;
            }
            int wight = sc.nextInt();
            cost[p1-1][p2-1] = wight;
            cost[p2-1][p1-1] = wight;
        }
        // 根据用户输入的图的信息,寻找最小生成树
        find_MST(cost);
    }
}

如下是使用普里姆算法在图 1 所示的连通网中查找最小生成树的 Python 程序:

V = 6     #图中顶点的个数
cost = [[0]*V for i in range(V)]
print("输入图(顶点到顶点的路径和权值):")
while True:
    li = input().split()
  
    p1 = int(li[0])
    p2 = int(li[1])
    if p1 == -1 and p2 == -1:
        break
    wight = int(li[2])
    cost[p1-1][p2-1] = wight
    cost[p2-1][p1-1] = wight
#查找权值最小的、尚未被选择的顶点,key 列表记录了各顶点之间的权值数据,visited列表记录着各个顶点是否已经被选择的信息
def min_Key(key,visited):
    #遍历 key 列表使用,min 记录最小的权值,min_index 记录最小权值关联的顶点
    min = float('inf')
    min_index = 0
    #遍历 key 列表
    for v in range(V):
        #如果当前顶点为被选择,且对应的权值小于 min 值
        if visited[v] == False and key[v]<min:
            #更新  min 的值并记录该顶点的位置
            min = key[v]
            min_index=v
    #返回最小权值的顶点的位置
    return min_index
#输出最小生成树
def print_MST(parent,cost):
    minCost=0
    print("最小生成树为:")
    #遍历 parent 列表
    for i in range(1,V):
        #parent 列表下标值表示各个顶点,各个下标对应的值为该顶点的父节点
        print("%d - %d wight:%d"%(parent[i]+1, i+1, cost[i][parent[i]]))
        #统计最小生成树的总权值
        minCost = minCost + cost[i][parent[i]];
    print("总权值为:%d"%(minCost))
#根据用户提供了图的信息(存储在 cost 列表中),寻找最小生成树
def find_MST(cost):
    #key 列表用于记录 B 类顶点到 A 类顶点的权值
    #parent 列表用于记录最小生成树中各个顶点父节点的位置,便于最终生成最小生成树
    #visited 列表用于记录各个顶点属于 A 类还是 B 类
    parent = [-1]*V
    key = [float('inf')]*V
    visited = [False]*V
    # 选择 key 列表中第一个顶点,开始寻找最小生成树
    key[0] = 0
    parent[0]= -1
    # 对于 V 个顶点的图,最需选择 V-1 条路径,即可构成最小生成树
    for x in range(V-1):
        # 从 key 列表中找到权值最小的顶点所在的位置
        u = min_Key(key,visited)
        visited[u] = True
        # 由于新顶点加入 A 类,因此需要更新 key 列表中的数据
        for v in range(V):
            # 如果类 B 中存在到下标为 u 的顶点的权值比 key 列表中记录的权值还小,表明新顶点的加入,使得类 B 到类 A 顶点的权值有了更好的选择
            if cost[u][v] !=0 and visited[v] == False and cost[u][v] < key[v]:
                # 更新 parent 列表记录的各个顶点父节点的信息
                parent[v] = u
                # 更新 key 列表
                key[v] = cost[u][v]
    # 根据 parent 记录的各个顶点父节点的信息,输出寻找到的最小生成树
    print_MST(parent,cost);
find_MST(cost)

图 1 连通网中的顶点 A、B、C、D、S、T 分别用 1~6 的数字表示,上面程序的运行结果均为:

输入图(顶点到顶点的路径和权值):
1 5 7
1 3 3
5 3 8
1 2 6
2 3 4
2 4 2
3 4 3
2 6 5
4 6 2
-1 -1
最小生成树为:
4 - 2 wight:2
1 - 3 wight:3
3 - 4 wight:3
1 - 5 wight:7
4 - 6 wight:2
总权值为:17文章来源地址https://www.toymoban.com/news/detail-794410.html

到了这里,关于prim算法(普里姆算法)详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 求最小生成树Prim(普里姆)和Kruskal(克鲁斯卡尔)算法

     想求最小生成树,我们首先得弄懂以下几个概念   连通图 :图中任意两个顶点都是连通的 极小连通子图 :既要保持图连通又要使得边数最少的子图 生成树 : 包含图中全部顶点的一个极小连通子图 连通图用通俗的话来讲就是,某一个顶点,可以 直接或者间接 (通过其他顶点

    2024年02月05日
    浏览(45)
  • 最小生成树(详解普里姆算法)

    首先,我们来看一下 图的一些基本知识点 : 图 :图 G=(V,E) 由顶点集 V 和边集 E 组成。每条边对应一个点对 (v,w),其中 v,w 属于 V 。如果图中的点对是有序的,那么该图就是有向图,反之为无向图。 邻接点 :若顶点 v 与 w 之间存在一条边,则认为顶点 v 与 w 邻接。 权 :图

    2024年01月19日
    浏览(82)
  • 数据结构(Java)最小生成树(普里姆、克鲁斯卡尔算法)

    最小生成树 (Minimum Cost Spanning Tree) ,简称 MST 。 1) 给定一个带权的无向连通图 , 如何选取一棵生成树 , 使树上所有 边上权的总和为最小 ,就 叫最小生成树 2) N 个顶点,一定有 N-1 条边 3) 包含全部顶点 4) N-1 条边都在图中 (好像不能形成闭合回路) 求最小生成树的算法主要是

    2023年04月08日
    浏览(42)
  • 数据结构---最小生成树((普里姆算法)C语言看了就懂教程)

        普里姆算法就是“加点法”,是一种将连通网转换成最小生成树的一种算法     在一个连通图的所有生成树中,各边代价之和最小的那颗生成树称为该连通图的最小代价生成树(MST)     ①对于任意一张连通图,假设 N = (V,E)是连通网,TE就是最小生成树中边的集合    

    2024年02月03日
    浏览(48)
  • 已知无向图G如下所示,使用普里姆 (Prim)算法求图G的最小生成树。 (a)请写出从顶点T出发,加到最小生成树中的边次序。 (6分) (2)说明Prim算法更适用于求哪种类型无向图的最小生 成树。(2分) (3)当图中顶点个数为n,边的个数为e时,该算法

    (a)从顶点T出发,加到最小生成树中的边次序如下: 先加入顶点T到顶点E的边,得到的最小生成树为:T-E 再加入顶点E到顶点D的边,得到的最小生成树为:T-E-D 再加入顶点D到顶点B的边,得到的最小生成树为:T-E-D-B 再加入顶点B到顶点C的边,得到的最小生成树为:T-E-D-B-C 再加

    2024年01月17日
    浏览(48)
  • 【图论】Prim算法

     Prim算法是一种用于解决最小生成树问题的贪心算法。 最小生成树问题是指在一个连通无向图中找到一个生成树,使得树中所有边的权重之和最小。 Prim算法的基本思想是从一个起始顶点开始,逐步扩展生成树,直到覆盖所有顶点。具体步骤如下: 选择一个起始顶点作为生成

    2024年02月15日
    浏览(41)
  • 图论13-最小生成树-Kruskal算法+Prim算法

    基本思想:按照权值从小到大的顺序选择 n-1 条边,并保证这 n-1 条边不构成回路 具体做法:首先构造一个只含 n 个顶点的森林,然后依权值从小到大从连通网中选择边加入到森林中,并使森林中 不产生 回路,直至森林变成一棵树为止。 2.2.1 如果图不联通,直接返回空,该

    2024年02月01日
    浏览(50)
  • 【算法基础:搜索与图论】3.5 求最小生成树算法(Prim&Kruskal)

    最小生成树 有关树的定义 生成子图 :生成子图是从原图中选取部分节点以及这些节点之间的边所组成的图。生成子图中的所有节点和边都必须在原图中存在。 生成树 :一个连通 无向图 的 生成子图 ,同时要求是树。也即在图的边集中选择 n - 1 条,将所有顶点连通。 我们

    2024年02月16日
    浏览(40)
  • 算法基础复盘笔记Day07【搜索与图论】—— Prim、Kruskal、染色体判定二分图、匈牙利算法

    ❤ 作者主页:欢迎来到我的技术博客😎 ❀ 个人介绍:大家好,本人热衷于 Java后端开发 ,欢迎来交流学习哦!( ̄▽ ̄)~* 🍊 如果文章对您有帮助,记得 关注 、 点赞 、 收藏 、 评论 ⭐️⭐️⭐️ 📣 您的支持将是我创作的动力,让我们一起加油进步吧!!!🎉🎉 1. 题目

    2024年02月02日
    浏览(50)
  • (数据结构)普利姆算法(Prim)实现

    假设要在n个城市之间建立通信联络网,每两个城市之间建立线路都需要花费不同大小的经费,则连通n个城市只需要n-1个条线路,最小生成树解决的问题就是: 如何在最节省经费的前提下建立这个通信网 也可以理解为:n个城市之间最多可以建立n(n-1)/2条线路,我们要从这里挑

    2024年02月03日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包