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.
Post Reply
User avatar
Phantom
Posts: 58
Joined: 7 years ago
Location: Cuba
Gender: None specified

BFS

Post by Phantom » 6 years ago

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: 7 years ago
Location: Cuba
Gender: None specified

Re: BFS

Post by Phantom » 6 years ago

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
Posts: 1968
Joined: 7 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

Re: BFS

Post by ymondelo20 » 6 years ago

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. ;)

Post Reply

Return to “Algorithms”