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}
1import math
2def empty_tree (n):
3 lst = []
4 for i in range(n):
5 lst.append([0]*n)
6 return lst
7def min_extension (con,graph,n):
8 min_weight = math.inf
9 for i in con:
10 for j in range(n):
11 if j not in con and 0 < graph[i][j] < min_weight:
12 min_weight = graph[i][j]
13 v,w = i,j
14 return v,w
15
16def min_span(graph):
17 con = [0]
18 n = len(graph)
19 tree = empty_tree(n)
20 while len(con) < n :
21 i ,j = min_extension(con,graph,n)
22 tree[i][j],tree[j][i] = graph[i][j], graph[j][i]
23 con += [j]
24 return tree
25
26def find_weight_of_edges(graph):
27 tree = min_span(graph)
28 lst = []
29 lst1 = []
30 x = 0
31 for i in tree:
32 lst += i
33 for i in lst:
34 if i not in lst1:
35 lst1.append(i)
36 x += i
37 return x
38
39graph = [[0,1,0,0,0,0,0,0,0],
40 [1,0,3,4,0,3,0,0,0],
41 [0,3,0,0,0,4,0,0,0],
42 [0,4,0,0,2,9,1,0,0],
43 [0,0,0,2,0,6,0,0,0],
44 [0,3,4,9,6,0,0,0,6],
45 [0,0,0,1,0,0,0,2,8],
46 [0,0,0,0,0,0,2,0,3],
47 [0,0,0,0,0,6,8,3,0]]
48graph1 = [[0,3,5,0,0,6],
49 [3,0,4,1,0,0],
50 [5,4,0,4,5,2],
51 [0,1,4,0,6,0],
52 [0,0,5,6,0,8],
53 [6,0,2,0,8,0]]
54print(min_span(graph1))
55print("Total weight of the tree is: " + str(find_weight_of_edges(graph1)))