Untitled

mail@pastecode.io avatar
unknown
plain_text
22 days ago
1.1 kB
2
Indexable
Never
#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;
}
Leave a Comment