prim 27s algorithm python

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}