数据结构：prim算法

╰半夏微凉° 2022-05-30 05:23 192阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    #define inf 999999
    
    bool visit[6] = {false};
    int dist[6] = {0};
    int graph[6][6] = {
        {inf, 7, 4, inf, inf, inf},
        {7, inf, 6, 2, inf, 4},
        {4, 6, inf, inf, 9, 8},
        {inf, 2, inf, inf, inf, 7},
        {inf, inf, 9, inf, inf, 1},
        {inf, 4, 8, 7, 1, inf}};
    
    int prim (int cur) {
        int index = cur;
        int sum = 0;
        printf("%d ", index);
        visit[cur] = true;
        for (int i=0; i<6; i++) {//计算cur与其他节点的距离
            dist[i] = graph[cur][i];
        }
        for (int i=1; i<6; i++) {
            int min = inf;
            for (int j=0; j<6; j++) {
                if (!visit[j] && dist[j] < min) {
                    min = dist[j];
                    index = j;
                }
            }
            visit[index] = true;
            printf("%d ", index);
            sum += min;
            for (int j=0; j < 6; j++) {
                if (!visit[j] && graph[index][j] < dist[j]) {
                    dist[j] = graph[index][j];
                }
            }
        }
        return sum;
    }
    
    int main (int argc, char **argv) {
        printf("%d", prim(0));
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关数据结构-最小生成树Prim算法的实现

目录一、前言二、最小生成树三、Prim算法四、Prim算法的实现 -------------------- 一、前言在计算机科学中，数据结构是一种组

悠悠/ 2024年03月17日 11:21/ 0 赞/ 63 阅读

相关 prim算法

1.prim算法概述普里姆算法（[Prim算法][Prim]），图论中的一种算法，可在加权连通图里搜索[最小生成树][Link 1]。意即由此算法搜索到的边子集所构成

电玩女神/ 2023年10月02日 19:51/ 0 赞/ 13 阅读

相关数据结构——图——普里姆（Prim )算法

数据结构——图——普里姆（Prim )算法我们先构造图7-6-1的邻接矩阵，如图7-6-3的右图所示： ![在这里插入图片描述][watermark_type_ZmF

旧城等待，/ 2023年01月11日 14:27/ 0 赞/ 144 阅读

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

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

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

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

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

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

相关数据结构：最小生成树--Prim算法

最小生成树：Prim算法最小生成树给定一无向带权图，顶点数是n，要使图连通只需n-1条边，若这n-1条边的权值和最小，则称有这n个顶点和n-1条边构成了图的最小

àì夳堔傛蜴生んèń/ 2022年06月12日 04:24/ 0 赞/ 233 阅读

相关数据结构：prim算法

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

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

相关 Prim算法

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

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

相关 Java数据结构之普里姆算法（Prim算法）

介绍普里姆算法是图结构中寻找最小生成树的一种算法。所谓生成树，即为连通图的极小连通子图，其包含了图中的n个顶点，和n-1条边，这n个顶点和n-1条边所构成的树即为生成树

- 日理万妓/ 2022年02月12日 11:23/ 0 赞/ 243 阅读

相关 [数据结构][Python][经典题目]Prim算法

from heapq import heappop,heappush def prim(G,s): P,Q = {},[(0,None,s)]

àì夳堔傛蜴生んèń/ 2022年01月23日 04:53/ 0 赞/ 260 阅读