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.
User avatar
Phantom
Posts: 58
Joined: Thu Nov 17, 2011 11:21 am
Location: Cuba
Gender: None specified

BFS

Postby Phantom » 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
Last edited by Phantom on Wed Jun 13, 2012 11:19 pm, edited 1 time in total.



User avatar
Phantom
Posts: 58
Joined: Thu Nov 17, 2011 11:21 am
Location: Cuba
Gender: None specified

Re: BFS

Postby Phantom » 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}
Last edited by Phantom on Wed Jun 13, 2012 11:19 pm, edited 1 time in total.

User avatar
ymondelo20
COJ Administrator
Posts: 1968
Joined: Sun Nov 13, 2011 12:32 pm
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

Re: BFS

Postby ymondelo20 » 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);
}
"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