BFS

[Phantom]

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

[Phantom]

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}

[ymondelo20]

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