NikPortFolio/Prims.cpp at master · nikhilstarinfinity/NikPortFolio · 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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<bits/stdc++.h>
using namespace std;
//more change git me check krna hua ki nhi change???
//2n ss are ay
int getminvtx(int * weight,bool* visited,int v)
{

int minVertex=-1;

for(int i=0;i<v;i++)
{
if(!visited[i] and (minVertex==-1 || weight[i]<weight[minVertex]))
{
minVertex=i;
}

}

return minVertex;
}

void prims(int ** graph,int v,int e)
{

bool* visited=new bool[v];
int* weight=new int[v];
int* parent=new int[v];

for(int i=0;i<v;i++)
{
weight[i]=INT_MAX;
visited[i]=false;
}

parent[0]=-1;
weight[0]=0;

for(int j=0;j<v;j++)
{
int minVertex=getminvtx(weight,visited,v);
visited[minVertex]=true;
for(int i=0;i<v;i++)
{

if(graph[minVertex][i] and !visited[i])
{
if(graph[minVertex][i]<weight[i])
{
weight[i]=graph[minVertex][i];
parent[i]=minVertex;
}
}

}
}

for(int i=1;i<v;i++)
{

if(parent[i]<i)
cout<<parent[i]<<" "<<i<<" "<<weight[i]<<endl;
else
cout<<i<<" "<<parent[i]<<" "<<weight[i]<<endl;
}


}
//commited in git
int main()
{

int v,e;
cin>>v>>e;
int ** graph=new int*[v];

for(int i=0;i<v;i++)
{
graph[i]=new int[v];
}

for(int i=0;i<v;i++)
{

for(int j=0;j<v;j++)
{
graph[i][j]=0;
}


}

for(int i=0;i<e;i++)
{

int s,e,w;
cin>>s>>e>>w;
graph[s][e]=w;
graph[e][s]=w;
}

cout<<endl;
prims(graph,v,e);

for(int i=0;i<v;i++)
{
delete [] graph[i];
}

delete [] graph;
}