algorithm_/prism-algorithm.css at main · charu237/algorithm_ · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;

int getMinVertex(bool* visited, int* weight, int n){
    int minVertex = -1;
    for(int i = 0; i<n; i++){
        if(!visited[i] &&((minVertex == -1) || (weight[minVertex] > weight[i]))){
            minVertex = i;
        }
    }
    return minVertex;
}
void prims(int** edges, int n){
    bool* visited = new bool[n]();
    int* parent = new int[n];
    int* weight = new int[n];
    for(int i = 0; i<n; i++){
        weight[i] = INT_MAX;
    }
    parent[0] = -1;
    weight[0] = 0;
    for(int i = 0; i<n-1; i++){
        int minVertex = getMinVertex(visited, weight, n);
        visited[minVertex] = true;
        for(int j = 0; j<n; j++){
            if(edges[minVertex][j] != 0 && !visited[j]){
                if(weight[j] > edges[minVertex][j]){
                    weight[j] = edges[minVertex][j];
                    parent[j] = minVertex;
                }
            }
        }
    }
    for(int i = 1; i<n; i++){
        if(parent[i]<i){
            cout<<parent[i]<<" "<<i<<" "<<weight[i]<<endl;
        }else{
            cout<<i<<" "<<parent[i]<<" "<<weight[i]<<endl;

        }
    }
}

int main()
{
  int n, E;
  cin >> n >> E;
  int** edges = new int*[n];
    for(int i = 0; i<n; i++){
        edges[i] =new int[n];
        for(int j = 0; j<n; j++){
            edges[i][j] = 0;
        }
    }
    for(int i = 0; i<E; i++){
        int f, s, weight;
        cin>>f>>s>>weight;
        edges[f][s] = weight;
        edges[s][f] = weight;
    }
    cout<<endl;
    prims(edges, n);

  return 0;
}