1#include<stdio.h>
2#include<conio.h>
3int a,b,u,v,n,i,j,ne=1;
4int visited[10]= { 0},min,mincost=0,cost[10][10];
5void main() {
6clrscr();
7printf("\n Enter the number of nodes:");
8scanf("%d",&n);
9printf("\n Enter the adjacency matrix:\n");
10for (i=1;i<=n;i++)
11 for (j=1;j<=n;j++) {
12 scanf("%d",&cost[i][j]);
13 if(cost[i][j]==0)
14 cost[i][j]=999;
15 }
16 visited[1]=1;
17 printf("\n");
18 while(ne<n) {
19 for (i=1,min=999;i<=n;i++)
20 for (j=1;j<=n;j++)
21 if(cost[i][j]<min)
22 if(visited[i]!=0) {
23 min=cost[i][j];
24 a=u=i;
25 b=v=j;
26 }
27 if(visited[u]==0 || visited[v]==0)
28 {
29 printf("\n Edge %d:(%d %d) cost:%d",ne++,a,b,min);
30 mincost+=min;
31 visited[b]=1;
32 }
33 cost[a][b]=cost[b][a]=999;
34 }
35 printf("\n Minimun cost=%d",mincost);
36 getch();
37}
1def empty_graph(n):
2 res = []
3 for i in range(n):
4 res.append([0]*n)
5 return res
6def convert(graph):
7 matrix = []
8 for i in range(len(graph)):
9 matrix.append([0]*len(graph))
10 for j in graph[i]:
11 matrix[i][j] = 1
12 return matrix
13def prims_algo(graph):
14 graph1 = convert(graph)
15 n = len(graph1)
16 tree = empty_graph(n)
17 con =[0]
18 while len(con) < n :
19 found = False
20 for i in con:
21 for j in range(n):
22 if j not in con and graph1[i][j] == 1:
23 tree[i][j] =1
24 tree[j][i] =1
25 con += [j]
26 found = True
27 break
28 if found :
29 break
30 return tree
31matrix = [[0, 1, 1, 1, 0, 1, 1, 0, 0],
32 [1, 0, 0, 1, 0, 0, 1, 1, 0],
33 [1, 0, 0, 1, 0, 0, 0, 0, 0],
34 [1, 1, 1, 0, 1, 0, 0, 0, 0],
35 [0, 0, 0, 1, 0, 1, 0, 0, 1],
36 [1, 0, 0, 0, 1, 0, 0, 0, 1],
37 [1, 1, 0, 0, 0, 0, 0, 0, 0],
38 [0, 1, 0, 0, 0, 0, 0, 0, 0],
39 [0, 0, 0, 0, 1, 1, 0, 0, 0]]
40
41lst = [[1,2,3,5,6],[0,3,6,7],[0,3],[0,1,2,4],[3,5,8],[0,4,8],[0,1],[1],[4,5]]
42print("From graph to spanning tree:\n")
43print(prims_algo(lst))
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <functional>
5#include <utility>
6
7using namespace std;
8const int MAX = 1e4 + 5;
9typedef pair<long long, int> PII;
10bool marked[MAX];
11vector <PII> adj[MAX];
12
13long long prim(int x)
14{
15 priority_queue<PII, vector<PII>, greater<PII> > Q;
16 int y;
17 long long minimumCost = 0;
18 PII p;
19 Q.push(make_pair(0, x));
20 while(!Q.empty())
21 {
22 // Select the edge with minimum weight
23 p = Q.top();
24 Q.pop();
25 x = p.second;
26 // Checking for cycle
27 if(marked[x] == true)
28 continue;
29 minimumCost += p.first;
30 marked[x] = true;
31 for(int i = 0;i < adj[x].size();++i)
32 {
33 y = adj[x][i].second;
34 if(marked[y] == false)
35 Q.push(adj[x][i]);
36 }
37 }
38 return minimumCost;
39}
40
41int main()
42{
43 int nodes, edges, x, y;
44 long long weight, minimumCost;
45 cin >> nodes >> edges;
46 for(int i = 0;i < edges;++i)
47 {
48 cin >> x >> y >> weight;
49 adj[x].push_back(make_pair(weight, y));
50 adj[y].push_back(make_pair(weight, x));
51 }
52 // Selecting 1 as the starting node
53 minimumCost = prim(1);
54 cout << minimumCost << endl;
55 return 0;
56}
1# Prim's Algorithm in Python
2
3INF = 9999999
4# number of vertices in graph
5N = 5
6#creating graph by adjacency matrix method
7G = [[0, 19, 5, 0, 0],
8 [19, 0, 5, 9, 2],
9 [5, 5, 0, 1, 6],
10 [0, 9, 1, 0, 1],
11 [0, 2, 6, 1, 0]]
12
13selected_node = [0, 0, 0, 0, 0]
14
15no_edge = 0
16
17selected_node[0] = True
18
19# printing for edge and weight
20print("Edge : Weight\n")
21while (no_edge < N - 1):
22
23 minimum = INF
24 a = 0
25 b = 0
26 for m in range(N):
27 if selected_node[m]:
28 for n in range(N):
29 if ((not selected_node[n]) and G[m][n]):
30 # not in selected and there is an edge
31 if minimum > G[m][n]:
32 minimum = G[m][n]
33 a = m
34 b = n
35 print(str(a) + "-" + str(b) + ":" + str(G[a][b]))
36 selected_node[b] = True
37 no_edge += 1
38
1//Minimum spanning tree using prim's Algorithm brute force method
2// BRUTE FORCE APPROACH
3#include<bits/stdc++.h>
4using namespace std;
5void addedge(vector<pair<int,int>>adj[],int u,int v,int weight)
6{
7 adj[u].push_back(make_pair(v,weight));
8 adj[v].push_back(make_pair(u,weight));
9}
10int main()
11{
12 int vertex,edges;
13 cout<<"ENTER THE NUMBER OF VERTEX AND EDGES:"<<endl;
14 cin>>vertex>>edges;
15 vector<pair<int,int>>adj[vertex];
16 int a,b,w;
17 cout<<"ENTER THE LINKS:"<<endl;
18 for(int i=0;i<edges;i++)
19 {
20 cin>>a>>b>>w;
21 addedge(adj,a,b,w);
22 }
23 int parent[vertex],key[vertex];
24 bool mset[vertex];
25 for(int i=0;i<vertex;i++)
26 {
27 parent[i]=-1;
28 key[i]=INT_MAX;
29 mset[i]=false;
30 }
31 key[0]=0;
32 parent[0]=-1;
33 for(int i=0;i<vertex-1;i++)
34 {
35 int minimum=INT_MAX,u;
36 for(int v=0;v<vertex;v++)
37 {
38 if(mset[v]==false&&key[v]<minimum)
39 {
40 minimum=key[v];
41 u=v;
42 }
43 }
44 mset[u]=true;
45 for(auto it:adj[u])
46 {
47 int v=it.first;
48 int weight=it.second;
49 if(mset[v]==false&&weight<key[v])
50 {
51 parent[v]=u;
52 key[v]=weight;
53 }
54 }
55 }
56 for(int i=1;i<vertex;i++)
57 {
58 cout<<parent[i]<<"->"<<i<<endl;
59 }
60 return 0;
61}
62
1// Minimum spanning tree using Prim's Algorithm Efficient Approach
2// Using Priority Queue
3// Watch striver graph series :)
4#include<bits/stdc++.h>
5using namespace std;
6void addedge(vector<pair<int,int>>adj[],int u,int v,int weight)
7{
8 adj[u].push_back(make_pair(v,weight));
9 adj[v].push_back(make_pair(u,weight));
10}
11int main()
12{
13 int vertex,edges;
14 cout<<"ENTER THE NUMBER OF VERTEX AND EDGES:"<<endl;
15 cin>>vertex>>edges;
16 vector<pair<int,int>>adj[vertex];
17 int a,b,w;
18 cout<<"ENTER THE LINKS:"<<endl;
19 for(int i=0;i<edges;i++)
20 {
21 cin>>a>>b>>w;
22 addedge(adj,a,b,w);
23 }
24 int parent[vertex],key[vertex];
25 bool mset[vertex];
26 for(int i=0;i<vertex;i++)
27 {
28 parent[i]=-1;
29 key[i]=INT_MAX;
30 mset[i]=false;
31 }
32 priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
33 parent[0]=-1;
34 key[0]=0;
35 pq.push(make_pair(0,0));//storing Key[i] and i
36 for(int count=0;count<vertex-1;count++)
37 {
38 int u=pq.top().second;
39 pq.pop();
40 mset[u]=true;
41 for(auto it:adj[u])
42 {
43 int v=it.first;
44 int weight=it.second;
45 if(mset[v]==false&&weight<key[v])
46 {
47 parent[v]=u;
48 pq.push(make_pair(key[v],v));
49 key[v]=weight;
50 }
51 }
52 }
53 for(int i=1;i<vertex;i++)
54 {
55 cout<<parent[i]<<"->"<<i<<endl;
56 }
57 return 0;
58}
59