Breadth First Search in Python and Java

Breadth-First-Search-Algorithm:

Here is the python code: You can call it like this:

./bfs.py graph.txt v

The file graph.txt:

v:r
r:s,v
s:r,w
w:t,x,s
t:w,x,u
x:w,t,u,y
u:t,x,y
y:x,u

#!/usr/bin/python
import sys

def read_graph(filename):
  f = open(filename,'r')
  graph = {}
  for line in f:
    line = line.replace('\n','')
    fromVertex, toList = line.split(':')
    toList = toList.split(',')
    graph[fromVertex] = toList
  return graph


def bfs(graph,s):
  color = {}
  dist = {}
  pi = {}
  for u in graph.keys():
    if u != s:
      color[u] = 'white'
      dist[u] = None
      pi[u] = None

  color[s] = 'gray'
  dist[s] = 0
  pi[s] = None
  Q = []
  Q.append(s)
  while len(Q) > 0:
    u = Q.pop(0)
    for v in graph[u]:
      if color[v] == 'white':
        color[v] = 'gray'
        dist[v] = dist[u]+1
        pi[v] = u
        Q.append(v)
    color[u] = 'black'
    for x in graph.keys():
      print x,color[x],dist[x],pi[x]
    print "---------------"

  return color,dist,pi

def print_path(graph,s,v,pi):
  if v == s:
    print s
  elif pi[v] is None:
    print "no path from ", s , " to ", v, " exists"
  else:
    print_path(graph, s, pi[v], pi)
    print v

if __name__ == '__main__':
  graph = read_graph(sys.argv[1])
  s = sys.argv[2]
  color,dist,pi = bfs(graph,s)

Here is the java code:

  import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;


public class BFS {

 private static HashMap color;
 private static HashMap dist;
 private static HashMap pi;
 
 public static void bfs(HashMap graph, String s)
 {

  color = new HashMap();
  dist = new HashMap();
  pi = new HashMap();
  for(String u : graph.keySet())
  {
    if( !u.equals(s)){
   color.put(u,  "white");
   dist.put(u, null);
   pi.put(u, null);
    }
  }

  color.put(s, "gray");
  dist.put(s, 0);
  pi.put(s, null);
  ArrayList Q = new ArrayList();
  Q.add(s);
  while( Q.size() > 0)
  {
     String u = Q.get(0);
     Q.remove(0);
     for(String v : graph.get(u))
     {
       if( color.get(v).equals("white") ) 
       {
         color.put(v, "gray");
         dist.put(v, dist.get(u)+1);
         pi.put(v, u);
         Q.add(v);
       }
     }
     color.put(u,"black");
     for( String x : graph.keySet())
     {
      System.out.println( x + " , " + color.get(x) + " , " + dist.get(x) + " , "+pi.get(x));
     }
     System.out.println("---------------");
  }
 }

 
 
 public static HashMap read_graph(String filename)
 {
  HashMap graph = new HashMap();
  try (BufferedReader br = new BufferedReader(new FileReader(filename))) {
      String line;
      while ((line = br.readLine()) != null) {
         String[] splitted1 = line.split(":");
         String fromVertex = splitted1[0];
         String[] toVertexList = splitted1[1].split(",");
         graph.put(fromVertex, toVertexList);
      }
  } catch (FileNotFoundException e) {
   System.out.println("file not found");
   e.printStackTrace();
   System.exit(1);
  } catch (IOException e) {
   e.printStackTrace();
   System.exit(1);
  }
  return graph;
 }
 
 /**
  * @param args
  */
 public static void main(String[] args) {
  // TODO Auto-generated method stub
        HashMap graph = read_graph(args[0]);
        bfs(graph,args[1]);
 }

}

You can call the java program like this:

java BFS graph.txt v

After calling the python / java version, you should get something similar to this:

r , gray , 1 , v
s , white , null , null
t , white , null , null
u , white , null , null
v , black , 0 , null
w , white , null , null
x , white , null , null
y , white , null , null
---------------
r , black , 1 , v
s , gray , 2 , r
t , white , null , null
u , white , null , null
v , black , 0 , null
w , white , null , null
x , white , null , null
y , white , null , null
---------------
r , black , 1 , v
s , black , 2 , r
t , white , null , null
u , white , null , null
v , black , 0 , null
w , gray , 3 , s
x , white , null , null
y , white , null , null
---------------
r , black , 1 , v
s , black , 2 , r
t , gray , 4 , w
u , white , null , null
v , black , 0 , null
w , black , 3 , s
x , gray , 4 , w
y , white , null , null
---------------
r , black , 1 , v
s , black , 2 , r
t , black , 4 , w
u , gray , 5 , t
v , black , 0 , null
w , black , 3 , s
x , gray , 4 , w
y , white , null , null
---------------
r , black , 1 , v
s , black , 2 , r
t , black , 4 , w
u , gray , 5 , t
v , black , 0 , null
w , black , 3 , s
x , black , 4 , w
y , gray , 5 , x
---------------
r , black , 1 , v
s , black , 2 , r
t , black , 4 , w
u , black , 5 , t
v , black , 0 , null
w , black , 3 , s
x , black , 4 , w
y , gray , 5 , x
---------------
r , black , 1 , v
s , black , 2 , r
t , black , 4 , w
u , black , 5 , t
v , black , 0 , null
w , black , 3 , s
x , black , 4 , w
y , black , 5 , x
---------------