[알고리즘2] Heap, adjList and Prim

#include <iostream>

#include <fstream>

using namespace std;

int sum;

struct Link

{

Link()

{

idx = -1;

cost = 0;

next = 0;

}

Link(int i, int _cost){

idx = i;

cost = _cost;

next = 0;

}

int idx;

int cost;

Link *next;

};

Link link[500];

int v, e;

struct Data 

{

int key;

int val;

};

Data heap[500];

int bottom;

void siftdown(int i)

{

Data key = heap[i];

int idx = i;

int largeChild;

while(2 * idx <= bottom)

{

if((2 * idx < bottom) && heap[2 * idx].val > heap[2 * idx + 1].val)

largeChild = 2 * idx + 1;

else

largeChild = 2 * idx;

if(key.val > heap[largeChild].val)

{

heap[idx] = heap[largeChild];

idx = largeChild;

}

else

break;

}

heap[idx] = key;

}

Data deleteHeap()

{

Data ret;

Data temp = heap[bottom];

heap[bottom] = heap[1];

ret = heap[bottom];

heap[1] = temp;

bottom--;

siftdown(1);

return ret;

}

void makeHeap()

{

for(int i = bottom / 2; i >= 1; i --)

{

siftdown(i);

}

}

void siftUp(int i)

{

Data key = heap[i];

int idx = i;

int largeChild;

while(idx / 2 >= 1)

{

if(key.val < heap[idx / 2].val)

{

heap[idx] = heap[idx / 2];

idx = idx / 2;

}

else

break;

}

heap[idx] = key;

}

void insertHeap(int idx, int cost)

{

Data in;

in.key = idx;

in.val = cost;

heap[++bottom] = in;

siftUp(bottom);

}

// dist == heap;

int near[500];

int dist[500];

// 건너간놈 검사

void Prim()

{

    for (int i=2;  i <= v; i ++)

    { 

near[i]=1;

dist[i]= 987654321;

}

for(Link* pt = link[1].next; pt != NULL; pt = pt->next) // 리스트 초기화

{

dist[pt->idx]= pt->cost;

insertHeap(pt->idx, pt->cost);

}

    for(int i = 0; i < v - 1; i ++)

{

Data poped = deleteHeap(); // 제일 작은걸 빼옴

while(dist[poped.key] < 0) // 이미 포함된 쓰레기

{

poped = deleteHeap();

}

for(Link* pt = link[poped.key].next; pt != NULL; pt = pt->next) // 팝된 원소에서 후보가 있는지 확인

{

if(dist[pt->idx] > pt->cost) // 더 쌘애임

{

insertHeap(pt->idx, pt->cost); // 후보를 힙에 추가

dist[pt->idx] = pt->cost;

near[pt->idx] = poped.key;

}

}

dist[poped.key] = -1; // 포함 했다.

}

}

int main()

{

fstream fin("input.txt");

fin >> v >> e;

for(int i = 1; i <= e; i ++)

{

int a, b, c;

fin >> a >> b >> c;

Link* pt = NULL;

if(link[a].next == NULL)

link[a].next = new Link(b, c);

else

{

for(pt = link[a].next; pt->next != NULL; pt = pt->next);

pt->next = new Link(b, c);

}

if(link[b].next == NULL)

link[b].next = new Link(a, c);

else

{

for(pt = link[b].next; pt->next != NULL; pt = pt->next);

pt->next = new Link(a, c);

}

}

Prim();

for(int i = 2; i <= v; i ++)

{

cout << near[i] << endl;

for(Link* pt = link[i].next; pt != NULL; pt = pt->next)

if(pt->idx == near[i])

sum += pt->cost;

}

cout << "COST : " << sum << endl;

return 0;

}