ADS-With-cpp/prims.cpp at main · Ahad-23/ADS-With-cpp · 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
111
112
113
114
115
116
117
118
119
#include <iostream>
using namespace std;
class graph
{
  int cost[10][10];
  int cities;
public:
graph()
{
  cities=0;
  cout<<"Enter the number of cities:"<<endl;
  cin>>cities;
  for(int i=0;i<cities;i++)
    {
      for(int j=0;j<cities;j++)
        {
          cost[i][j]=999;
        }
    }
}

  void create()
{
  cout<<"Enter the cost matrix:"<<endl;
  for(int i=0;i<cities;i++)
    {
      for(int j=0;j<cities;j++)
        {
          bool choice=0;
          cout<<"Do you have edge between "<<i+1<<" and "<<j+1<<"(1/0)?"<<endl;
          cin>>choice;
          if(choice)
          {
            cout<<"Enter the cost of edge between "<<i+1<<" and "<<j+1<<endl;
            cin>>cost[i][j];
          }
          else
            cost[i][j]=999;
        }
    }
}

void display()
{
  cout<<"The cost matrix is:"<<endl;
  for(int i=0;i<cities;i++)
    {
      for(int j=0;j<cities;j++)
        {
          cout<<cost[i][j]<<"\t";
        }
      cout<<endl;
    }
}

int prims()
{
    int start_v;
    int r=0;
    int j;
    int mincost=0;
    int min;
    int t[cities-1][3];
    int nearest[cities];
    cout<<"Enter starting vertex"<<endl;
    cin>>start_v;
    nearest[start_v]=-1;
        for(int i=0;i<cities-1;i++)
            {
            if(i!=start_v)
                nearest[i]=start_v;
            }

    for(int i=0;i<cities-1;i++)
        {
             min=999;
            for(int k=0;k<cities-1;k++)
            {

                if(nearest[k]!=-1 && cost[k][nearest[k]]<min )
                {
                    j=k;
                    min=cost[k][nearest[k]];
                }
            }
        t[r][0]=j;
        t[r][1]=nearest[j];
        t[r][2]=min;
        r=r+1;
        mincost+=cost[j][nearest[j]];
        nearest[j]=-1;

        for(int k=0;k<cities-1;k++)
        {
            if(nearest[k]!=-1 && cost[k][nearest[k]]>cost[k][j])
            nearest[k]=j;
        }
        cout<<"T matrix"<<endl;
        for(int i=0;i<cities;i++)
        {
          for(int a=0;a<3;a++)
          {
            cout<<t[i][a]<<"\t";
          }
          cout<<"\n";
        }

        }
        return mincost;
}
};

int main() {
 graph g1;
  g1.create();
  g1.display();
  int mincost=g1.prims();
cout<<"Mincost:"<<mincost<<endl;
}