HLDEC.NET

[code cpp:nocontrols]
#include <list>
using namespace std;
[/code]

[code cpp:nocontrols]
typedef struct tagEDGE{
 int  iNodeA;
 int  iNodeB;
 int  iWeight;
public:
 bool operator < (const struct tagEDGE &vector) {
  if (iWeight < vector.iWeight) return 1;
  else return 0;
 }
 void OutputScreen() {
  printf("( %d, %d : %d )\n", iNodeA, iNodeB, iWeight );
 }
}EDGE;
[/code]

[code cpp:nocontrols]
void ConvertData(const int iTree[SIZE][SIZE], std::list<EDGE> &listData)
{
 EDGE edge;
 
 for (int i=1; i<SIZE; i++) {
  for (int j=0; j<i; j++) {
   if (iTree[i][j]!=INFINITE) {
    edge.iNodeA = i;
    edge.iNodeB = j;
    edge.iWeight = iTree[i][j];
    listData.push_back(edge);
   }
  }
 }
 listData.sort();
}
[/code]

[code cpp:nocontrols]
void Prim(std::list<EDGE> &listData, std::list<EDGE> &listOutput)
{
 std::list<EDGE>::iterator it;
 EDGE edgeMin;
 int iMinWeight;
 bool *pBoundNode = new bool[SIZE];
 memset(pBoundNode, 0, sizeof(bool)*SIZE);
 it = listData.begin();
 listOutput.push_back(*it);
 pBoundNode[it->iNodeA] = TRUE;
 pBoundNode[it->iNodeB] = TRUE;
 while(listOutput.size() < SIZE-1) {
  iMinWeight = INFINITE;
  for (int i=0; i<SIZE; i++) {
   if (pBoundNode[i] == TRUE) {
    it = listData.begin();
    while(it != listData.end()) {
     if (it->iNodeA == i && pBoundNode[it->iNodeB] == FALSE ||
      it->iNodeB == i && pBoundNode[it->iNodeA] == FALSE ) {
      if (iMinWeight > it->iWeight) {
       iMinWeight = it->iWeight;
       edgeMin = *it;
      }
     }
     ++it;
    }
   }
  }
  if (iMinWeight != INFINITE) {
   pBoundNode[edgeMin.iNodeA] = TRUE;
   pBoundNode[edgeMin.iNodeB] = TRUE;
   listOutput.push_back(edgeMin);
  }
 }
 delete[] pBoundNode;
}
[/code]

[code cpp:nocontrols]
#include <list>
using namespace std;
[/code]

[code cpp:nocontrols]
typedef struct tagEDGE{
 int  iNodeA;
 int  iNodeB;
 int  iWeight;
 bool bVisited;
public:
 bool operator < (const struct tagEDGE &vector) {
  if (iWeight < vector.iWeight) return 1;
  else return 0;
 }
 void OutputScreen() {
  printf("( %d, %d : %d )\n", iNodeA, iNodeB, iWeight );
 }
}EDGE;
[/code]

[code cpp:nocontrols]
void ConvertData(const int iTree[SIZE][SIZE], std::list<EDGE> &listData)
{
 EDGE edge;
 
 for (int i=1; i<SIZE; i++) {
  for (int j=0; j<i; j++) {
   if (iTree[i][j]!=INFINITE) {
    edge.iNodeA = i;
    edge.iNodeB = j;
    edge.iWeight = iTree[i][j];
    edge.bVisited = FALSE;
    listData.push_back(edge);
   }
  }
 }
 listData.sort();
}
[/code]

[code cpp:nocontrols]
void Kruscal(std::list<EDGE> &listData, std::list<EDGE> &listOutput)
{
 std::list<EDGE>::iterator it, itClear, itNest;
 std::list<int> queueNode;
 std::list<int>::iterator itQueue;
 int iCount;
 it = listData.begin();
 while (it != listData.end() ) {
  listOutput.push_back(*it);
  // Looping check
  for (itClear = listOutput.begin(); itClear != listOutput.end(); ++itClear) itClear->bVisited = FALSE;
  itNest = --listOutput.end();
  queueNode.push_back(itNest->iNodeA);
  queueNode.push_back(itNest->iNodeB);
  itNest->bVisited = TRUE;
  itQueue = queueNode.begin();
  while(itQueue != queueNode.end()) {
   iCount = 0;
   itNest = listOutput.begin();
   while(itNest != listOutput.end()) {
    if (iCount < 2) {
     if (itNest->iNodeA == *itQueue) {
      if (itNest->bVisited == TRUE) {
       iCount++;
      } else {
       queueNode.push_back(itNest->iNodeB);
       itNest->bVisited = TRUE;
      }
     } else if (itNest->iNodeB == *itQueue) {
      if (itNest->bVisited == TRUE) {
       iCount++;
      } else {
       queueNode.push_back(itNest->iNodeA);
       itNest->bVisited = TRUE;
      }
     }
    }
    ++itNest;
   }
   if(iCount < 2)++itQueue;
   else {
    queueNode.erase(queueNode.begin(), queueNode.end());
    break;
   }
   queueNode.pop_front();
  }
  if (iCount >= 2) listOutput.pop_back();
  ++it;
 }
}
[/code]