HLDEC :: the mobile experience ::

'mst'에 해당되는 글 2건

2007/05/18 Prim Algorithm
2007/05/18 Kruscal Algorithm

Prim Algorithm

전처리문 :

[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]

자료 변환 함수 : ConvertData(2차원 배열그래프, STL 리스트)

[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]

사용법 : Prim(변환된 그래프 리스트, 반환할 MST 리스트)

[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]

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

'Development & Tips > Algorithms' 카테고리의 다른 글

3-Standard Quick Sort (0)	2007/05/22
Prim Algorithm (0)	2007/05/18
Kruscal Algorithm (0)	2007/05/18
Quick Sort (0)	2007/05/18
Merge Sort (0)	2007/05/18

Posted by HLDEC

TAG Algorithm, mst, Prim, source code, 알고리즘, 프림

Trackback 0 Comment 0

Kruscal Algorithm

필요 전처리문 :

[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]

자료 변환 함수 : ConvertData(2차원 배열그래프, STL 리스트)

[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]

사용법 : Kruscal(변환된 그래프 리스트, 반환할 MST 리스트)

[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]

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.