Prim算法

阳光穿透心脏的1/2处 2022-02-26 03:42 166阅读 0赞

#include <iostream>  
    using namespace std;  
    const int infinity = 999999;  
      
      
    int EXTRACT_MIN( int *d, bool *visited, int n)  
    {  
        int min = infinity;  
        int m = -1;  
        for ( int i = 0; i < n; i++ )  
        {  
            if ( !visited[i] && d[i] < min)  
            {  
                min = d[i];  
               m = i;  
            }  
        }  
        return m;  
    }  
      
    int MST_PRIM( int Adj[9][9],int r, int n)  
    {  
        int i;  
        int *d = new int[n];  
       bool *visited = new bool[n];  
     
        for ( i = 0; i < n; i++)  
        {  
            d[i] = infinity;  
            visited[i] = false;  
        }  
      
        d[r] = 0;  
        int len = 0;  
        for ( i = 0; i < n; i++)  
        {  
            int u = EXTRACT_MIN(d, visited, n);  
            visited[u] = true;  
            len += d[u];  
           for ( int v = 0; v < n; v++)  
            {  
               if ( !visited[v] && Adj[u][v] < d[v])  
                {  
                    d[v] = Adj[u][v];  
               }  
            }  
        }  
        delete [] d;  
        delete [] visited;  
        return len;  
    }  
      
    int main(int argc, char* argv[])  
    {  
        int num=9;
        int Adj[9][9]={
       {999,4,999,999,999,999,999,8,999},{4,999,8,999,999,999,999,11,999},{999,8,999,7,999,4,999,999,2},{999,999,7,999,9,14,999,999,999},
    	{999,999,999,9,999,1999,999,999,999},{999,999,4,14,1999,999,2,999,999},{999,999,999,999,999,2,999,1999,6},{8,11,999,999,999,999,1,999,7},{999,999,2,999,999,999,6,7,999}};;  
        cout << MST_PRIM(Adj,0, num) << endl;  
        return 0;  
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，166人围观）

还没有评论，来说两句吧...

相关阅读

相关 prim法matlab,Prim算法

该楼层疑似违规已被系统折叠隐藏此楼查看此楼 A.Prim算法： procedure prim(v0:integer); var lowcost,closest:arr

电玩女神/ 2023年01月16日 09:42/ 0 赞/ 107 阅读

相关数据结构----C++实现Prim算法（贪心算法）

> 理解最小生成树的定义 > > 生成树：连通图的生成树是包含全部顶点的一个极小连通子图 > 生成树的代价：在无向连通网中，生成树上各边的权值之和 >

叁歲伎倆/ 2022年10月25日 11:26/ 0 赞/ 200 阅读

相关《大话数据结构》之Prim算法

Prim算法作用是构造连通网的最小代价生成树。算法思想：以任意一个点开始，找权值最小的一条边，将此边和两个顶点加入最小生成树集合，以最小生成树的点集合中的每一个点为起点，找

傷城~/ 2022年08月17日 14:20/ 0 赞/ 221 阅读

相关 Prim算法和Kruskal算法

原文地址: http://blog.csdn.net/believejava/article/details/17414037 http://www.cnblogs

骑猪看日落/ 2022年07月12日 08:52/ 0 赞/ 215 阅读

相关最小生成树Prim算法(贪心算法)

// //Description:最小生成树算法 // include <iostream> using namespace std;

╰半夏微凉°/ 2022年06月18日 01:56/ 0 赞/ 214 阅读

相关数据结构：prim算法

include <stdio.h> include <stdlib.h> define inf 999999 bool visit[6

╰半夏微凉°/ 2022年05月30日 05:23/ 0 赞/ 176 阅读

相关 Prim算法解释

MST（Minimum Spanning Tree，最小生成树）问题有两种通用的解法，Prim算法就是其中之一，它是从点的方面考虑构建一颗MST，大致思想是：设图G顶点集合为U

朱雀/ 2022年05月19日 04:49/ 0 赞/ 191 阅读

相关 Prim算法演示

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5

朱雀/ 2022年03月28日 13:11/ 0 赞/ 198 阅读

相关 Prim算法

include <iostream> using namespace std; const int infinity = 999999;

阳光穿透心脏的1/2处/ 2022年02月26日 03:42/ 0 赞/ 167 阅读

相关 prim算法--最小生成树

首先我们在这里先介绍一下prim算法，我记得大学数据结构先讲完最小生成树，再讲最短路径，也是考研必考问题。 prim算法在加权连通图里面寻找全局最小的生成树。是一个贪心算法。

悠悠/ 2021年11月17日 02:28/ 0 赞/ 445 阅读