Untitled
1 week ago in Plain Text
#include <cstring>
#include <iostream>
#define INF 9999999
#define V 6
using namespace std;
int G[V][V] = {
{0, 5, 8, 7, 0, 0},
{5, 0, 0, 6, 0, 0},
{8, 0, 0, 4, 5, 0},
{7, 6, 4, 0, 3, 1},
{0, 0, 5, 3, 0, 2},
{0, 0, 0, 1, 2, 0}};
int main() {
int no_edge;
int selected[V];
memset(selected, false, sizeof(selected));
no_edge = 0;
selected[0] = true;
int x;
int y;
cout << "Edge" << " : " << "Weight";
cout << endl;
while (no_edge < V - 1)
{
int min = INF;
x = 0;
y = 0;
for (int i = 0; i < V; i++)
{
if (selected[i])
{
for (int j = 0; j < V; j++)
{
if (!selected[j] && G[i][j])
{ // not in selected and there is an edge
if (min > G[i][j])
{
min = G[i][j];
x = i;
y = j;
}
}
}
}
}
cout << x << " - " << y << " : " << G[x][y];
cout << endl;
selected[y] = true;
no_edge++;
}
return 0;
}