prims algorithm

Solutions on MaxInterview for prims algorithm by the best coders in the world

showing results for - "prims algorithm"
Lara
09 May 2019
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}
Vicente
20 Mar 2016
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))
Luca
21 Feb 2020
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}
Irina
15 Apr 2020
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
Noah
31 Sep 2017
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
Kylen
25 Feb 2018
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
queries leading to this page
prims algorithm in pythonprims algorithm in c 2b 2bprims c 2b 2bprim algorithm c 2b 2b for powergridwhat is prim e2 80 99s algorithm prim 27s algorithm inccode for prim 27s algorithm in cprims algorithm using c 2b 2bprims and kruskal algorithmprism algorithmimplement prim e2 80 99s algorithm in cprims algorithm implementation in pythonprim 27s algorithm python using listminimum cost spanning tree using prim 27s program in cprims algorithm c 2b 2b linear searchprim kruskal dijkstra pythongive algorithm for prims and kruskal algorithm prims algorithm implementation write a program in c to find minimum cost spanning tree of an undirected graph using prim e2 80 99s algorithm minimum cost spanning tree using prim 27s algorithmusing prims algo find the minimum spanning tree of the following graphprim graph algorithmprims algoritm in pythonprims algorithm gfgcpp primsprims algorithm c 2bprim 27s mst algorithmprim 27s spanning treeminimum cost spanning tree prim 27s algorithm c 2b 2bprim 27s spanning tree algorithmprince algorithm in cprims algorithm with pythonprim e2 80 99s algorithmprims algo codeapply prim e2 80 99s algorithm on the following graph and show all the steps what are needed to be done 2c starting vertex is a 7bsolution requird in table format 5dhow to draw prim 27s algorithm in pythonprims algorithm c programwrite a c program to accept undirected weighted graph from user and represent it with adjacency list and find a minimum spanning tree using prims algorithm primes and kruskal algorithmjava prim timewhile finding the minimum spanning distance using prim 22s algorithm 2c what are the required conditionssolving total cost using prims algorithm in pyhtonprims algorithm mst c codeprims algorithm in c languageprims algorithm codewrite a c program to accept undirected weighted graph from user and represent it with adjacency list and find a minimum spanning tree using prims algorithmprim 27s algorithm python codeprim e2 80 99s algorithm is a solve mst prime graphprims algor for minum spanning treec program to implement prim 27s algorithm to find mstprims algoritham python codec 2b 2b program to implement minimum spanning tree using prim 27s algorithmmst prim algorithm c 2b 2bconcept of prism algoprim algorithm c 2b 2bprims algorithm program in cppprimes algorithim in greeks for greeksfind the mst using prim e2 80 99s algorithm prims algorithm in c 2b 2b gfgprims 26 dijkstra project c 2b 2b exampleprim 27s algorithm in c 2b 2b using adjacency matrixminimum spanning tree solution pythonprim greedyprims algorithm is based onadding an edge to mst java prim dfswhy is it called prim 27s algorithm 29 given the following graph 2c use prim e2 80 99s algorithm to compute the minimum spanning tree 28mst 29 of the graph write down the edges of the mst in sequence based on the prim e2 80 99s algorithmprims kruskal algorithmimplementation of prims algorithmprim 27s algorithm in c 2b 2bprims algorithm graph in pythonwrite a c program to find the minimum spanning tree of the following graph using prim e2 80 99s algorithm prim 27s algorithm example with solutionprim 27s algorithm practicewhat is the agenda of prim 27s and kruskal algorithmprim minimum spanning treeprim e2 80 99s algorithm for the computation of minimum cost spanning tree for an undirected graphpython prim algorithmprim 27s algorithm numericalrun the prim 27s algorithm starting at epython program to implement prim 27s algorithm to find mstimplementation of prim e2 80 99s algorithmprim 27s algorithm c implementationsopannig tree primc program code for prims algorithmprims algorithm cprim 27s algorithm pythonprim 27s algorithmprims algorithm implementation javaprims algorithm python geeksforgeeksprim in cprim 27s algorithm c programprims algo implementation pthonprim algorithm pythonprim 27s algorithm using graph python implementationwhen we use prims algorithmjava primprims algorithm in cminimum spanning tree using prim 27s algorithm c programwhat is prims algorithmwhich approach is used in prim e2 80 99s algorithmimplement prims algorithm in cminimum spanning tree pythonprims algorithm examples matrixsteps of prim 27s algorithmprim 27s algo mst code in cprims algorithm implementation in pythonprime algorithm for mstprims algorithm stl cppmst using prim 27s algorithmprim algorithm in cpython prims algorithmprims algorithm using cminimum cost spanning tree using greedy method program for prims algorithm in cc program to implement prim 27s algorithmsimple prime algorithm for mst implementationprims algorithm explainc to implement prim 27s algorithmwhat is the time complexity for prims algorithm for finding mst for graph with n number of nodes 3fwhy do we use prim 27s algorithmprims algorithm in c codeprim 27s algorithm methodwrite prim 27s algorithmhow to program a algorithm in c prim 27s algorithm questionsprim 27s algorithm using greedy method exampleprim 27s algorithm pseudocode geeks for geekswhat is prim 27s algorithmprims code in cc program for prim 27s algorithmprims algorithm implementation c 2b 2bprim 27s algorithm mediumhow to optimize prims algorithm in 22complete 22 graphprim algo in cprim 27s algorithm is used to findc program for prims algorithmprims algorithmprim 27s algorithm minimum spanning treemst codewrite prim 27s algorithm for adjacenecy listprim e2 80 99s algorithm pythonprim 27s pythonfind mst using prims algorithmprim in c programizhow is prim 27s algorithm calculated 3fprim algorithm codeprims algorithm pythonprims algorithm jacaprims algorithm code in cspanning tre eprogtam in cprims and kruskal algorithm in pythonprim 27s algorithm c codeprin algorithmprim 5c 27s algorithmhow does prims algorithm workimplementation of prim 27s algorithm in c programmingprint minimum spanning treemst primm algorithmprim 27s algorithm using adjacency matrixprim javapython code for prim 27s algorithmprim 27s algorithm in c 2b 2b with outputprim 27s minimum spanning tree algorithm in c 2b 2bkruskal 27s algorithm and prim 27s algorithm createprims algorithm programmizprim 27s algorithm in pythonminimum spanning tree prim 27s algorithm codeprim algorithm on graphs is for finding implementation of prims algorithm in cprim 27s mst algorithm c 2b 2bprims program in cpphow does prim 27s algorithm workprims c is prim 27s algorithm greedycode of minimum spanning tree of given undirected graph using prims algorithmprims algorithm geekslimitations of prim 27s algorithmtracing of prims algorithmprims algorithm using dynamic programmingcreate a minimal spanning tree using prims 2c then find the minimum total cost prim mst is a dynamic programmingwrite a program to find minimum cost spanning tree of a given undirected graph using prims algorithm prims algorithm in cppmst algorithm primmst using prim e2 80 99s algoprim algorithm for binary treesprim 27s algorithm c 2b 2b codeprim 27s algorithm code in c languageprim 27s algorithm spanning treeprims algorithm is aprims minimal spamming tree phtyonprim 27s algorithm geeksforgeeksprims algorithm implementation in c 2b 2bprims o 28e log v 29prim algorithmprimes algorithmprim 27s algorithm c 2b 2bprims program in javaminimum spanning tree primprim 27s algorithm implementation in pythonprim 27s algorithm exampleprim algorithm cppprims algorithm inmplementation in javaprim 27s algo in javaprims algorithm program in cprim 27s algorithm cprims algo cppprim 27s algorithm in cprim algorithm javaprim e2 80 99s algorithm is aprim 27s algorithm python implementationminimum spanning trees 3f prims algorithmprint minimum spanning tree prim 27s algorithmhow to find mst from adjacency matrix prims questionawith solutionprims algorithm c 2b 2b2 29find the mst and cost of given graph using prims algorithm in cminimum spanning tree using prim 27s algorithm in c 2b 2bprim algorithm code pythonwap to construct a minimum cost spanning tree of a graph using prim e2 80 99s algorithm implement prim 27s algorithmprims algorithm simple implementationminimum spanning tree using prims algorithmprims algorithm examplepython graph prim 27s algorithmprim 27s algorithm gfgprims e2 80 99s algorithm for the computation of minimum cost spanning tree for an undirected graphprims algorithm program in pythonprim algorythm pythonprims code in c 2b 2bprim mst pythonprim 27s algorithm for finding minimum spanning tree 28coding approach using adjacency matrix 29graph prim algorithmprims kruskal algorithm exampleprims algo in cprims in capply prim e2 80 99s algorithm on the following graph and show all the steps what are needed to be done 2c starting vertex is a 7bsolution required in table format 5dfind edges in the minimum spanning tree for the given graph using prim e2 80 99s algorithm 28initialization from node a 29prims algorithm c 2b 2b programminimum spanning tree prim 27s algorithmprimm 27s algorithmminimum spanning tree prim 27s algorithm c 2b 2bprims algorithm cppprims mst algorithmprim jarnik algorithm javawhile finding the minimum spanning distance using prim 22s algorithm 2c which is trueminimum spanning tree algorithm geeks for geeksprim 27s algorithm javawrite the prim algorithmprim 27s algorithm iprim 27s algorithm is a explain the greedy strategy involved in prim e2 80 99s algorithm to find minimum spanning treeprims algorithm greedy techniqueprims prim implementation cimplementing prims algorithm c 2b 2bprim 27s algorithm for minimum spanning treeprim 27s algorithm using three arrayprims and kruskal algorithm gfgprim 27s algorithm codeprim pythonalgorithm of spanning tree pythonprims algorithm stepsprim mst usesimpleemnt prim 27s algorithm in pythonprims cppprims minimum spanning treeprims javabest way to implement prims algorithm in c 2b 2bprim and kruskal algorithmprims algorithm code in javawrite a program to implement prim e2 80 99s algorithmprims algorithm code c 2b 2bprims algorithm wikiwrite a program to find minimum cost spanning tree of a given undirected graph using prim 27s algorithm prim 27s algorithm implementationprim 27s minimal spanning tree algorithmprim 27s algorithm pseudocode in pythonprim 27s algorithm minimum spanning tree java codeprims algorithm methodalgorithm for prims and kruskalprim 27s algorithm stepsprim 27s algorithm mstundirected graph prim c 2b 2balgorithm constructs a spanning tree by considering one vertex at a time 2 pointskruskal 27s algorithmprim 27s algorithmshortest path algorithm 27prims algo javamst prim 27s algorithmprin 27s algorithmprims algorithm program injavaprims exampleprims algorithm given connections classprims algorithm c codeprims algorithm uses which strategyprims algorithm valuesprims algorithm code in cppdefine prim e2 80 99s algorithm with examplecode for prims algorithmprim 27s algorithm analysisprime algorithmprims graph in pythonfind the correct statement data structure prim 27s minimal spanning tree algorithm dijkstra 27s minimum spanning tree algorithm floyd warshall 27s all pairs shortest path algorithmprims input c 2b 2bmst prim algorithmminimum spanning tree prim javaprims algorithm in javaprim implementation c 2b 2bprim 27s algorithm program in javaprims algorithm notesimplement prims algorithmprims algorithm competitive program in cppprim 27s algorithm on adjacency matrixpython prim 27s algorithmprims spannig treeprims mst algorithm with example in c 2b 2bprims algorithm in c programminimum cost spanning tree using greedy method program for prims algorithmprims algorithm javaprims algorithm