prim 27s algorithm

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

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

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