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 |