'공부'에 해당되는 글 13건

  1. 2014.10.02 BFS, DFS, Topological Sort
  2. 2014.10.02 다잌스트라
  3. 2014.09.25 [알고리즘2] Heap, adjList and Prim
posted by pflower 2014. 10. 2. 11:18


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;

}







'공부 > 알고리즘2' 카테고리의 다른 글

maxflow bipar  (0) 2014.11.06
maxflow 탈출문제  (0) 2014.11.06
bfs  (0) 2014.10.16
다잌스트라  (0) 2014.10.02
[알고리즘2] Heap, adjList and Prim  (0) 2014.09.25
posted by pflower 2014. 10. 2. 09:44

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


}

'공부 > 알고리즘2' 카테고리의 다른 글

maxflow bipar  (0) 2014.11.06
maxflow 탈출문제  (0) 2014.11.06
bfs  (0) 2014.10.16
BFS, DFS, Topological Sort  (0) 2014.10.02
[알고리즘2] Heap, adjList and Prim  (0) 2014.09.25
posted by pflower 2014. 9. 25. 11:26

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

}

'공부 > 알고리즘2' 카테고리의 다른 글

maxflow bipar  (0) 2014.11.06
maxflow 탈출문제  (0) 2014.11.06
bfs  (0) 2014.10.16
BFS, DFS, Topological Sort  (0) 2014.10.02
다잌스트라  (0) 2014.10.02