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