BFS

Discussion around the algorithms: the most powerful tool of the contest programmer. This is the place to ask about the algorithms you have heard mention, or to share with the community your knowledge about them.
Forum rules
Remember that you may not post the AC solution to any of the problems on the COJ. Only code pertaining to a general algorithm will be allowed.
Posting AC solutions will be penalized.
Phantom
Posts: 58
Joined: 9 years ago
Location: Cuba
Gender:

BFS

Here an example of BFS in Python(my implementation):

Code: Select all

``````def BFS(graph, pos):
queue, mark = [pos], [False] * len(graph)
mark[pos] = True
while queue:
act = queue.pop(0)
for i in graph[act]:
if not mark[i]:
queue.append(i)
mark[i] = True
yield i

#Example:
graph = [[3], [0, 2, 5], [3, 4], [1, 0], [5, 3], [0, 1, 2, 3]]
for i in BFS(graph, 1): print i
``````
Last edited by Phantom on Wed Jun 13, 2012 11:19 pm, edited 1 time in total.

Phantom
Posts: 58
Joined: 9 years ago
Location: Cuba
Gender:

Re: BFS

Here an example of BFS in Ruby(my implementation):

Code: Select all

``````def BFS(graph, pos)
marks, queue = [false] * graph.length, [pos]
marks[pos] = true
while !queue.empty?
act = queue.delete_at(0)
for i in graph[act]:
if !marks[i]:
marks[i] = true
queue.push(i)
yield i
end
end
end
end

#Example:
graph = [[3], [0, 2, 5], [3, 4], [1, 0], [5, 3], [0, 1, 2, 3]]
BFS(graph, 1){ |val| puts val}
``````
Last edited by Phantom on Wed Jun 13, 2012 11:19 pm, edited 1 time in total.

ymondelo20
Posts: 1968
Joined: 9 years ago
Location: Universidad de las Ciencias Informáticas
Gender:
Contact:

Re: BFS

This is my implementation in C++.

Code: Select all

``````//------------------------------- Graph Theory (BFS Implementation)
// Author : Yonny Mondelo...
#define CICLE(i,a,b,c) for(int i=(a); i<=(b); i += (c))
#define MAXNODS 1001
using namespace std;
#include <stdio.h>
#include <vector>
#include <queue>
#include <stack>
int mark[MAXNODS], pred[MAXNODS], dist[MAXNODS];
int nodes, edges, start, destiny;
vector<int> G[MAXNODS];

void DoBFS(int src)
{
queue<int> Q; Q.push(src);
dist[src] = mark[src] = 1;
while(!Q.empty())
{
int nod = Q.front(); Q.pop();
int large = G[nod].size() - 1;
CICLE(p,0,large,1) if(0 == mark[G[nod][p]])
{
Q.push(G[nod][p]);
mark[G[nod][p]] = 1;
pred[G[nod][p]] = nod;
dist[G[nod][p]] = dist[nod] + 1;
}
}
}

void PrintPATH(int src, int nod)
{
start = nod;
printf("%d\n",dist[start]);
if(-1 != dist[start])
{
stack<int> S; while(start != src)
{ S.push(start); start = pred[start]; } S.push(src);
while(!S.empty()) { printf("%d\n",S.top()); S.pop(); }
}
}

int main()
{
scanf("%d%d",&nodes,&edges);
CICLE(p,1,nodes,1) { G[p].clear(); mark[p] = 0; dist[p]=-1; }
CICLE(p,1,edges,1) { scanf("%d%d",&start,&destiny); G[start].push_back(destiny); }
DoBFS(1); PrintPATH(1,nodes);
}``````
"Every problem has a simple, fast and wrong solution" OJ's Main Law.