首页 > 其他分享 >c: Prim's Algorithm

c: Prim's Algorithm

时间:2023-09-26 17:57:51浏览次数:54  
标签:Prim Algorithm int selected vertex number edge include

PrimsAlgorithm.h  

/**
 * *****************************************************************************
 * @file        PrimsAlgorithm.h
 * @brief       Prim's Algorithm
 * @author       (geovindu,Geovin Du,涂聚文)
 * @date        2023-09-26
 * @copyright   geovindu
 * *****************************************************************************
 */
#ifndef PRIMSALGORITHM_H
#define PRIMSALGORITHM_H

#include<stdio.h>
#include<stdbool.h> 

#define INF 9999999

// number of vertices in graph
#define V 5
/**
 * @brief       
 * 
 * @param       G 
 */
void Prims(int G[V][V]);



#endif

  

PrimsAlgorithm.c  
/**
 * *****************************************************************************
 * @file        PrimsAlgorithm.c
 * @brief       Prim's Algorithm
 * @author       (geovindu,Geovin Du,涂聚文)
 * @date        2023-09-26
 * @copyright   geovindu
 * *****************************************************************************
 */

#include<stdio.h>
#include<stdbool.h> 
#include "include/PrimsAlgorithm.h"



/**
 * @brief       
 * 
 */
void Prims(int G[V][V])
{
    
    int no_edge;  // number of edge

    // create a array to track selected vertex
    // selected will become true otherwise false
    int selected[V];

    // set selected false initially
    memset(selected, false, sizeof(selected));
    
    // set number of edge to 0
    no_edge = 0;

    // the number of egde in minimum spanning tree will be
    // always less than (V -1), where V is number of vertices in
    //graph

    // choose 0th vertex and make it true
    selected[0] = true;

    int x;  //  row number
    int y;  //  col number

    // print for edge and weight
    printf("\n16.Prim's Algorithm\n Edge : Weight\n");

    while (no_edge < V - 1) {
        //For every vertex in the set S, find the all adjacent vertices
        // , calculate the distance from the vertex selected at step 1.
        // if the vertex is already in the set S, discard it otherwise
        //choose another vertex nearest to selected vertex  at step 1.

        int min = INF;
        x = 0;
        y = 0;

        for (int i = 0; i < V; i++) {
        if (selected[i]) {
            for (int j = 0; j < V; j++) {
            if (!selected[j] && G[i][j]) {  // not in selected and there is an edge
                if (min > G[i][j]) {
                min = G[i][j];
                x = i;
                y = j;
                }
            }
            }
        }
        }
        printf("%d - %d : %d\n", x, y, G[x][y]);
        selected[y] = true;
        no_edge++;


    }
}

  

调用:

    //16 Prim's Algorithm
    int G[V][V] = {
    {0, 9, 75, 0, 0},
    {9, 0, 95, 19, 42},
    {75, 95, 0, 51, 66},
    {0, 19, 51, 0, 31},
    {0, 42, 66, 31, 0}};
    Prims(G);

  

 

标签:Prim,Algorithm,int,selected,vertex,number,edge,include
From: https://www.cnblogs.com/geovindu/p/17730817.html

相关文章

  • c: Dijkstra's Algorithm
     DijkstrasAlgorithm.h /*********************************************************************************@fileDijkstrasAlgorithm.h*@briefDijkstra'sAlgorithminC迪杰斯特拉算法最短路径算法https://www.programiz.com/dsa/dijkstra......
  • c: Ford - Fulkerson Algorithm
     FordFulkersonAlgorithm.h /*********************************************************************************@fileFordFulkersonAlgorithm.h*@briefFord-FulkersonAlgorithminCFord-Fulkerson算法(FFA)是一种贪婪算法,用于计算流网络......
  • c: Kruskal Algorithm
    KruskalAlgorithm.h /*****************************************************************//***\fileKruskalAlgorithm.h*\briefKruskalAlgorithm克鲁斯卡尔算法*IDE:VSCODEc11https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/2.selectio......
  • isPrimitive()方法和包装类
    java.lang.Class.isprimitive()是说:确定指定的Class对象是基本类型,其返回是个boolean值,true代表你指定的这个Class对象是基本类型,false代表这个Class对象不是基本类型。所以在java.lang.Class.isPrimitive()中: .isPrimitive()是用来判断是否是基本类型的:           ......
  • python: Sorting Algorithms
     #encoding:utf-8#版权所有2023涂聚文有限公司#许可信息查看:PythonSortingAlgorithms#描述:*https://www.programiz.com/dsa/counting-sort#*https://www.geeksforgeeks.org/sorting-algorithms/#Author:geovindu,GeovinDu涂聚文.#IDE:PyC......
  • 《C++ Primer Plus》
    第一章预备知识1.1C++简介C++编程语言融合了3种不同的编程方式:C语言代表的过程性语言、面向对象语言、C++模板支持的泛型编程。1.2C++简史C语言  20世纪70年代,贝尔实验室的DennisRitchie致力开发UNIX操作系统。传统上,程序员使用汇编语言来满足这些需求。但由于汇编语......
  • python: Essential Algorithms
     #encoding:utf-8#版权所有2023涂聚文有限公司#许可信息查看:#描述:#Author:geovindu,GeovinDu涂聚文.#IDE:PyCharm2023.1python311#Datetime:2023/9/2121:28#User:geovindu#Product:PyCharm#Project:EssentialAlgor......
  • c: Sorting Algorithms
    SortAlgorithm.h /*****************************************************************//***\fileSortAlgorithm.h*\brief业务操作方法*VSCODEc11https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/2.selectionSort.md*https://www.progra......
  • KingbaseES V8R6集群备份恢复案例之---备份初始化“can not find primary node”故障
    案例说明:KingbaseESV8R6集群,备库作为repo-path节点,建立类型为‘cluster’模式的备份,在执行sys_backup.shinit时,出现“cannotfindprimarynode”故障。故障如下图所示:适用版本:KingbaseESV8R6一、集群及备份配置1、集群节点状态[kingbase@node101bin]$./repmgrclus......
  • C++ Primer 学习笔记——第十章
    第10章前言在前面我们学习容器的时候,是否发现标准库下的对容器的操作并不是太多(或许,初学时已经觉得好多了......