prims minimum spanning tree

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)))