Page 1 of 1

### BFS

Posted: Mon Jun 11, 2012 1:09 am
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
``````

### Re: BFS

Posted: Mon Jun 11, 2012 2:32 pm
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}
``````

### Re: BFS

Posted: Tue Jun 12, 2012 5:56 pm
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);
}``````