纯C语言：贪心Prim算法生成树问题源码分享

代码如下:

#include <iostream.h>
#define MAX 100
#define MAXCOST 100000

int graph[MAX][MAX];

int Prim(int graph[MAX][MAX], int n)
{
 /* lowcost[i]记录以i为终点的边的最小权值，当lowcost[i]=0时表示终点i加入生成树 */
 int lowcost[MAX];

/* mst[i]记录对应lowcost[i]的起点 */
 int mst[MAX];

int i, j, min, minid, sum = 0;

/* 默认选择0号节点加入生成树，从1号节点开始初始化 */
 for (i = 1; i < n; i++)
 {
  /* 最短距离初始化为其他节点到0号节点的距离 */
   lowcost[i] = graph[0][i];

/* 标记所有节点的起点皆为默认的0号节点 */
  mst[i] = 0;
 }

/* 标记0号节点加入生成树 */
 lowcost[0] = 0;

/* n个节点至少需要n-1条边构成最小生成树 */
 for (i = 1; i < n; i++)
 {
  min = MAXCOST;
  minid = 0;

/* 找满足条件的最小权值边的节点minid */
  for (j =1; j <n; j++)
  {
   /* 边权值较小且不在生成树中 */
   if (lowcost[j] < min && lowcost[j] != 0)
   {
    min = lowcost[j];
    minid = j;
   }
  }
  /* 输出生成树边的信息:起点，终点，权值 */
  cout<<"生成数边的起点、终点及权值分别为："<< mst[minid]+1<<"  "<<minid+1<<"  "<<min<<endl;
  /* 累加权值 */
  sum += min;

/* 标记节点minid加入生成树 */
  lowcost[minid] = 0;

/* 更新当前节点minid到其他节点的权值 */
  for (j = 1; j < n; j++)
  {
   /* 发现更小的权值 */
   if (graph[minid][j] < lowcost[j])
   {
    /* 更新权值信息 */
    lowcost[j] = graph[minid][j];

/* 更新最小权值边的起点 */
    mst[j] = minid;
   }
  }
 }
 /* 返回最小权值和 */
 return sum;
}

void main()
{
 int i, j,  m,n;
 int  cost;
  /* 读取节点的数目 */
 cout<<"请输入该图结点个数：";
 cin>>m;
 /* 初始化图，所有节点间距离为无穷大 */
 for (i = 0; i <m; i++)
 {
  for (j =i+1; j <m; j++)
  {
   cout<<"请输入结点"<<i+1<<"到结点"<<j+1<<"边的权值，若无边则输入MAXCOST(100000):";
   cin>>n;
   graph[i][j] = n;
   graph[j][i] = n;
  }
  graph[i][i]=MAXCOST;
 }

/* 求解最小生成树 */
 cost = Prim(graph, m);
 cout<<"最小生成树的权值为："<<cost<<endl;
}

赞 (0)

相关推荐

  • 最小生成树算法之Prim算法

    最小生成树算法之Prim算法

    本文介绍了最小生成树的定义,Prim算法的实现步骤,通过简单举例实现了C语言编程. 1.什么是最小生成树算法? 简言之,就是给定一个具有n个顶点的加权的无相连通图,用n-1条边连接这n个顶点,并且使得连接之后的所有边的权值之和最小.这就叫最小生成树算法,最典型的两种算法就是Kruskal算法和本文要讲的Prim算法. 2.Prim算法的步骤是什么? 这就要涉及一些图论的知识了. a.假定图的顶点集合为V,边集合为E. b.初始化点集合U={u}.//u为V中的任意选定的一点 c.从u的邻接结点中

  • 最小生成树算法C语言代码实例

    在贪婪算法这一章提到了最小生成树的一些算法,首先是Kruskal算法,实现如下: MST.h 复制代码 代码如下: #ifndef H_MST#define H_MST #define NODE node *#define G graph *#define MST edge ** /* the undirect graph start */typedef struct _node { char data; int flag; struct _node *parent;} node; typede

  • 纯C语言：贪心Prim算法生成树问题源码分享

    复制代码 代码如下: #include <iostream.h>#define MAX 100#define MAXCOST 100000 int graph[MAX][MAX]; int Prim(int graph[MAX][MAX], int n){ /* lowcost[i]记录以i为终点的边的最小权值,当lowcost[i]=0时表示终点i加入生成树 */ int lowcost[MAX]; /* mst[i]记录对应lowcost[i]的起点 */ int mst[MAX]; in

  • 纯C语言:递归二进制转十进制源码分享

    复制代码 代码如下: #include<stdio.h>#include<math.h>int change(int n,int *sum,int *m)//n为第n位,m总位数{    char c;    if(c!='#')    {        *m=*m+1;        change(n+1,sum,m);    }    if(c=='#')    {        return *sum=int(*sum+pow(2,*m-n));    }}void main

  • C语言实现学生管理系统的源码分享

    C语言实现学生管理系统的源码分享

    注意:没有用到数据库使用链表完成此系统! 多文件实现 正式开始 代码都可以直接使用 不想看的,直接复制代码块里面的内容就行! 我用的visual studio 2019   有些使用了 _s  如果是用别的编译器,可以自行修改! 功能介绍 增,删,改,查,退出,保存,以至于格式化! 1.录入学生信息 2.查看录入的学生信息(全部学生信息) 3.修改已录入的学生信息(以学号) 4.删除已录入的学生信息(以学号) 5.保存信息到文件 6.指定查找(以学号) 7.隐藏选项(格式化链表--清空) 'q'

  • C语言实现的ls命令源码分享

    在之前的一些看书或者学习中,一直有一种感觉有问题的态度,那就是认为看懂了,但是不动手,感觉这样看书的效果不是很大.ls命令估计是我们在linux/unix里面用的最多的一个命令了,我们就用c来简单的实现一下ls命令. // // ls.c // apue // // Created by chenqing on 13-8-22. // Copyright (c) 2013年 chenqing. All rights reserved. // #include "/usr/include/apue

  • Go语言读写锁RWMutex的源码分析

    Go语言读写锁RWMutex的源码分析

    目录 前言 RWMutex 总览 深入源码 数据结构 RLock() RUnlock() Lock() Unlock() 常见问题 实战一下 前言 在前面两篇文章中 初见 Go Mutex .Go Mutex 源码详解,我们学习了 Go语言 中的 Mutex,它是一把互斥锁,每次只允许一个 goroutine 进入临界区,可以保证临界区资源的状态正确性.但是有的情况下,并不是所有 goroutine 都会修改临界区状态,可能只是读取临界区的数据,如果此时还是需要每个 goroutine 拿到锁依

  • Android开发数据结构算法ArrayList源码详解

    目录 简介 ArrayList源码讲解 初始化 扩容 增加元素 一个元素 一堆元素 删除元素 一个元素 一堆元素 修改元素 查询元素 总结 ArrayList优点 ArrayList的缺点 简介 ArrayList是List接口的一个实现类,它是一个集合容器,我们通常会通过指定泛型来存储同一类数据,ArrayList默认容器大小为10,自身可以自动扩容,当容量不足时,扩大为原来的1.5倍,和上篇文章的Vector的最大区别应该就是线程安全了,ArrayList不能保证线程安全,但我们也可以通过其

  • 神经网络python源码分享

    神经网络python源码分享

    神经网络的逻辑应该都是熟知的了,在这里想说明一下交叉验证 交叉验证方法: 看图大概就能理解了,大致就是先将数据集分成K份,对这K份中每一份都取不一样的比例数据进行训练和测试.得出K个误差,将这K个误差平均得到最终误差 这第一个部分是BP神经网络的建立 参数选取参照论文:基于数据挖掘技术的股价指数分析与预测研究_胡林林 import math import random import tushare as ts import pandas as pd random.seed(0) def getD

  • JS原生2048小游戏源码分享(全网最新)

    JS原生2048小游戏源码分享(全网最新)

    最近在学习算法方面的知识,看到了一个由算法主导的小游戏,这里给大家分享下代码: 效果: 代码: <head> <meta charset="UTF-8"> <meta name="viewport" content="width=360px,user-scalable=no" /> <title>2048小游戏</title> <style> body,h1,div,tabl

  • Spring Boot 员工管理系统超详细教程(源码分享)

    Spring Boot 员工管理系统超详细教程(源码分享)

    员工管理系统 1.准备工作 资料下载 内含源码 + 笔记 + web素材 源码下载地址: http://xiazai.jb51.net/202105/yuanma/javaguanli_jb51.rar 笔记 素材 源码 1.1.导入资源 将文件夹中的静态资源导入idea中 位置如下 1.2.编写pojo层 员工表 //员工表 @Data @NoArgsConstructor public class Employee { private Integer id; private String l

  • 14 个Python小游戏 源码分享

    14 个Python小游戏 源码分享

    目录 1.吃金币 2.打乒乓 3.滑雪 4.并夕夕版飞机大战 5.打地鼠 6.小恐龙 7.消消乐 8.俄罗斯方块 9.贪吃蛇 10.24点小游戏 11.平衡木 12.外星人入侵 13.贪心鸟 14.井字棋888'' 1.吃金币 源码分享: import os import cfg import sys import pygame import random from modules import * '''游戏初始化''' def initGame(): # 初始化pygame, 设置展示窗口

随机推荐