비 왔으면 좋겠다

BFS 

#include <iostream>

#include <fstream>

using namespace std;

int v, e;

struct Link

{

Link(int val)

{

this->val = val;

next = NULL;

}

int val;

Link *next;

};

Link* store = NULL;

Link* graph[500];

int seen[500];

int queue[500];

int parent[500];

int front;

int back;

void push(int val)

{

queue[back] = val;

back = (back + 1) % 500;

}

int pop()

{

int ret = queue[front];

front = (front + 1) % 500;

return ret;

}

bool queueEmpty()

{

return back == front;

}

void bfs(int n)

{

push(n);

while(!queueEmpty())

{

int i = pop();

seen[i] = 2;

//cout << i << endl;

for(Link *temp = graph[i]; temp != NULL; temp = temp->next)

{

if(seen[temp->val] == 0)

{

parent[temp->val] = i;

push(temp->val);

seen[temp->val] = 1;

}

}

}

}

void bfs_all()

{

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

{

if(seen[i] == 0)

bfs(i);

}

}

int main()

{

fstream fin("input.txt");

fin >> v >> e;

memset(parent, -1, sizeof(parent));

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

{

int a, b;

fin >> a >> b;

if(graph[a] == NULL)

{

graph[a] = new Link(b);

}

else

{

Link *temp = NULL;

for(temp = graph[a]; temp->next != NULL; temp = temp->next);

temp->next = new Link(b);

}

}

//cout << "<--DFS Result-->" << endl;

bfs_all();

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

{

cout << parent[i] << endl;

}

}

DFS

#include <iostream>

#include <fstream>

using namespace std;

int v, e;

struct Link

{

Link(int val)

{

this->val = val;

next = NULL;

}

int val;

Link *next;

};

Link* store = NULL;

Link* graph[500];

int seen[500];

int parent[500];

void dfs(int i)

{

//cout << i << endl;

seen[i] = 1;

for(Link *temp = graph[i]; temp != NULL; temp = temp->next)

{

if(seen[temp->val] == 0)

{

parent[temp->val] = i;

dfs(temp->val);

}

}

}

void dfs_all()

{

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

{

if(seen[i] == 0)

dfs(i);

}

}

int main()

{

fstream fin("input.txt");

fin >> v >> e;

memset(parent, -1, sizeof(parent));

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

{

int a, b;

fin >> a >> b;

if(graph[a] == NULL)

{

graph[a] = new Link(b);

}

else

{

Link *temp = NULL;

for(temp = graph[a]; temp->next != NULL; temp = temp->next);

temp->next = new Link(b);

}

}

//cout << "<--DFS Result-->" << endl;

dfs_all();

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

{

cout << parent[i] << endl;

}

}

TOPOL

#include <iostream>

#include <fstream>

using namespace std;

int v, e;

struct Link

{

Link(int val)

{

this->val = val;

next = NULL;

}

int val;

Link *next;

};

Link* store = NULL;

Link* graph[500];

int seen[500];

void dfs(int i)

{

cout << i << endl;

if(seen[i])

return;

seen[i] = true;

for(Link *temp = graph[i]; temp != NULL; temp = temp->next)

{

dfs(temp->val);

}

if(store == NULL)

{

store = new Link(i);

}

else

{

Link *temp = store;

store = new Link(i);

store->next = temp;

}

}

void topological_sort()

{

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

{

dfs(i);

}

}

int main()

{

fstream fin("input.txt");

fin >> v >> e;

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

{

int a, b;

fin >> a >> b;

if(graph[a] == NULL)

{

graph[a] = new Link(b);

}

else

{

Link *temp = NULL;

for(temp = graph[a]; temp->next != NULL; temp = temp->next);

temp->next = new Link(b);

}

}

cout << "<--DFS Result-->" << endl;

topological_sort();

cout << "<--Topological Sort Result-->" << endl;

for(Link * temp= store; temp != NULL; temp = temp->next)

cout << temp->val << endl;

}

#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];

int flag[500];

// 건너간놈 검사

void dij()

{

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

{ 

near[i]= 1;

dist[i]= 987654321;

flag[i]= true;

}

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(!flag[poped.key]) // 이미 포함된 쓰레기

{

poped = deleteHeap();

}

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

{

if(dist[pt->idx] > pt->cost + dist[poped.key]) // 더 짧은애임

{

insertHeap(pt->idx, pt->cost + dist[poped.key]); // 후보를 힙에 추가

dist[pt->idx] = pt->cost + dist[poped.key];

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

}

}

flag[poped.key] = false; // 포함 했다.

}

}

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);

}

}

dij();

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

{

cout << near[i] << endl;

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

if(pt->idx == i)

sum += pt->cost;

}

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

return 0;

}

#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;

}