## 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: Thu Nov 17, 2011 11:21 am
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: Thu Nov 17, 2011 11:21 am
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  endend#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
COJ Administrator
Posts: 1968
Joined: Sun Nov 13, 2011 12:32 pm
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 1001using 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.

Return to “Algorithms”

### Who is online

Users browsing this forum: No registered users and 1 guest