BFS, DFS, Topological Sort

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;

}