Prim's Algorithm In Python Code Example

Example 1: prim's algorithm python

def empty_graph(n):     res = []     for i in range(n):         res.append([0]*n)     return res def convert(graph):     matrix = []     for i in range(len(graph)):          matrix.append([0]*len(graph))         for j in graph[i]:             matrix[i][j] = 1     return matrix def prims_algo(graph):     graph1 = convert(graph)     n = len(graph1)     tree = empty_graph(n)     con =[0]     while len(con) < n :         found = False         for i in con:             for j in range(n):                 if j not in con and graph1[i][j] == 1:                     tree[i][j] =1                     tree[j][i] =1                     con += [j]                     found  = True                     break             if found :                 break     return tree matrix = [[0, 1, 1, 1, 0, 1, 1, 0, 0],           [1, 0, 0, 1, 0, 0, 1, 1, 0],           [1, 0, 0, 1, 0, 0, 0, 0, 0],           [1, 1, 1, 0, 1, 0, 0, 0, 0],           [0, 0, 0, 1, 0, 1, 0, 0, 1],           [1, 0, 0, 0, 1, 0, 0, 0, 1],           [1, 1, 0, 0, 0, 0, 0, 0, 0],           [0, 1, 0, 0, 0, 0, 0, 0, 0],           [0, 0, 0, 0, 1, 1, 0, 0, 0]]  lst = [[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]] print("From graph to spanning tree:\n") print(prims_algo(lst))

Example 2: prims c++

#include <iostream> #include <vector> #include <queue> #include <functional> #include <utility>  using namespace std; const int MAX = 1e4 + 5; typedef pair<long long, int> PII; bool marked[MAX]; vector <PII> adj[MAX];  long long prim(int x) {     priority_queue<PII, vector<PII>, greater<PII> > Q;     int y;     long long minimumCost = 0;     PII p;     Q.push(make_pair(0, x));     while(!Q.empty())     {         // Select the edge with minimum weight         p = Q.top();         Q.pop();         x = p.second;         // Checking for cycle         if(marked[x] == true)             continue;         minimumCost += p.first;         marked[x] = true;         for(int i = 0;i < adj[x].size();++i)         {             y = adj[x][i].second;             if(marked[y] == false)                 Q.push(adj[x][i]);         }     }     return minimumCost; }  int main() {     int nodes, edges, x, y;     long long weight, minimumCost;     cin >> nodes >> edges;     for(int i = 0;i < edges;++i)     {         cin >> x >> y >> weight;         adj[x].push_back(make_pair(weight, y));         adj[y].push_back(make_pair(weight, x));     }     // Selecting 1 as the starting node     minimumCost = prim(1);     cout << minimumCost << endl;     return 0; }