BFS implementation

Question

i was recently solving a bfs problem where each node is a different arrangement of elements of an array. but i was unable to come up with a suitable data structure to keep track of the visited nodes in the expanded tree. generally the nodes are different strings so we can just use a map to mark a node as visited but what DS should i use in the above case?

Answer 1

Here is BFS implementation using C++ STL(adjacency lists) for Graph. Here three Array and a Queue is used for complete implementation.

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

//Adding node pair of a Edge in Undirected Graph 
void addEdge( vector<int> adj[], int u, int v){
    adj[u].push_back(v);  // 1st push_back
    adj[v].push_back(u);  //2nd push_back
    //for Directed Graph use only one push_back i.e., 1st push_back() rest is same 
}
//Traversing through Graph from Node 0 in Adjacency lists way
void showGraph( vector<int>adj[], int size){
    cout<<"Graph:\n";
    for(int i=0; i<size ; i++){
        cout<<i;
        for( vector<int>::iterator itr= adj[i].begin() ; itr!=adj[i].end(); itr++){
        cout<<" -> "<<*itr;
    }
    cout<<endl;
}
}
//Prints Array elements
void showArray(int A[]){
    for(int i=0; i< 6; i++){
        cout<<A[i]<<" ";
    }
}


void BFS( vector<int>adj[], int sNode, int N){

    //      Initialization
    list<int>queue; //Queue declaration
    int color[N]; //1:White, 2:Grey, 3:Black
    int parentNode[N];  //Stores the Parent node of that node while   traversing, so that you can reach to parent from child using this 
    int distLevel[N];   //stores the no. of edges required to reach the node,gives the length of path

    //Initialization
    for(int i=0; i<N; i++){
        color[i] = 1;   //Setting all nodes as white(1) unvisited
        parentNode[i] = -1;  //setting parent node as null(-1)
        distLevel[i] = 0;  //initializing dist as 0
    }

    color[sNode] = 2;  //since start node is visited 1st so its color is grey(2)
    parentNode[sNode] = -1;  //parent node of start node is null(-1)
    distLevel[sNode] = 0;    //distance is 0 since its a start node
    queue.push_back(sNode);  //pushing start node(sNode) is queue

    // Loops runs till Queue is not empty if queue is empty all nodes are visited
    while( !queue.empty()){

    int v = queue.front();  //storing queue's front(Node) to v
    // queue.pop_front();//Dequeue poping element from queue

    //Visiting all  nodes connected with v-node in adjacency list
    for(int i=0; i<adj[v].size() ;i++){

        if( color[ adj[v][i] ] == 1){// if node is not visited, color[node]==1  which is white 
            queue.push_back(adj[v][i]);  //pushing that node to queue
            color[adj[v][i]]=2;  //setting as grey(2)
            parentNode[ adj[v][i] ] = v; //parent node is stored                distLevel[ adj[v][i] ] = distLevel[v]+1;  //level(dist) is incremented y from dist(parentNode)
        }
    }//end of for
    color[v]=3;
    queue.pop_front();//Dequeue

}

printf("\nColor: \n");showArray(color);
printf("\nDistLevel:\n");showArray(distLevel);
printf("\nParentNode:\n");showArray(parentNode);
}

int main(){

int N,E,u,v;//no of nodes, No of Edges, Node pair for edge
cout<<"Enter no of nodes"<<endl;
cin>>N;
vector<int> adj[N];  //vector adjacency lists

cout<<"No. of edges"<<endl;
cin>>E;

cout<<"Enter the node pair for edges\n";
for( int i=0; i<E;i++){
    cin>>u>>v;
    addEdge(adj, u, v);  //invoking addEdge function
}

showGraph(adj,N);  //Printing Graph in Adjacency list format
BFS(adj,0,N);  /invoking BFS Traversal
}

Answer 2

Just for the purpose of understanding, i have provided my sample code here (its in C#)

  private void Breadth_First_Travers(Node node)
  {
        // First Initialize a queue - 
        // it's retrieval mechanism works as FIFO - (First in First Out)
        Queue<Node> myQueue = new Queue<Node>();

        // Add the root node of your graph into the Queue
        myQueue.Enqueue(node);

        // Now iterate through the queue till it is empty
        while (myQueue.Count != 0)
        {
            // now, retrieve the first element from the queue 
            Node item = myQueue.Dequeue();
            Console.WriteLine("item is " + item.data);

            // Check if it has any left child   
            if (item.left != null)
            {
                // If left child found - Insert/Enqueue into the Queue
                myQueue.Enqueue(item.left);
            }

            // Check if it has right child 
            if (item.right != null)
            {
                // If right child found Insert/Enqueue into the Queue  
                myQueue.Enqueue(item.right);
            }

            // repeat the process till the Queue is empty
        }
   }

Here sample code is give with reference of http://en.wikipedia.org/wiki/Binary_tree as tree is a type of graph it self.

Answer 3

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author VAISAKH N
 */
public class BFSME {

public static String path = "";
public static String add = "";

public static void findrec(String temp, String end, String[][] m, int j) {
    if (temp.equals(m[j][1])) {
        add = m[j][0] + temp + end + "/";
        end = temp + end;
        System.out.println(end);
        path = path + add;
        temp = "" + add.charAt(0);
        System.out.println("Temp" + temp);
        for (int k = 0; k < m.length; k++) {
            findrec(temp, end, m, k);
        }
    }
}

public static void main(String[] args) {

    String[][] data = new String[][]{{"a", "b"}, {"b", "c"}, {"b", "d"}, {"a", "d"}};
    String[][] m = new String[data.length][2];
    for (int i = 0; i < data.length; i++) {
        String temp = data[i][0];
        String end = data[i][1];
        m[i][0] = temp;
        m[i][1] = end;
        path = path + temp + end + "/";
        for (int j = 0; j < m.length; j++) {

            findrec(temp, end, m, j);
        }

    }
    System.out.println(path);
}
}

Answer 4

Consider the following pseudocode:

type Node;  // information pertaining to a node
type Path;  // an ordered list of nodes
type Area;  // an area containing linked neighboring nodes
type Queue; // a FIFO queue structure

function Traverse(Area a, Node start, Node end) returns Path:
    Queue q;
    Node n;
                        // traverse backwards, from finish to start
    q.push(end);        // add initial node to queue
    end.parent = end;   // set first node's parent to itself

    while (not q.empty()):
        n = q.pop();    // remove first element

        if (n == start) // if element is the final element, we're done
            break;

        for (Node neighbor in a.neighbors(n)): // for each neighboring node
            if (neighbor.parent != Null):      // if already visited, skip
                continue;
            neighbor.parent = n;               // otherwise, visit 
            q.push(neighbor);                  // then add to queue

    Path p;             // prepare to build path from visited list

    for (Node previous = Null, current = n;
              previous != current;
              previous = current, current = current.parent):
        p.add(current); // for each node from start to end, add node to p
                        // Note that the first node's parent is itself
                        // thus dissatisfying the loop condition
    return p;

The "visited list" is stored as the node's parent. Coding this to C++, you would probably handle most of the nodes as references or pointers since this pseudocode relies on referential behavior.

You start with an Area, which is a field of Nodes. The area knows where each node is in relation to the others. You start at one specific Node, the "start" node, and push it into a queue.

Traversing the area is as simple as getting the list of neighboring nodes from the Area, skipping them if they're already visited, and setting their parent and adding them to the queue otherwise. Traversal ends when a node removed from the queue equals the destination node. You could speed up the algorithm a little by doing this check during the neighbor loop, when the node is initially encountered.

NOTE: You do not need to generate every possible node within the area before beginning the traversal, the Area requires only that once it has created a node, it keeps track of it. This might help your situation where it appears you use permutations of strings or arrays: you could push the starting and ending nodes into the Area, and it could generate and cache neighbor nodes on the fly. You might store them as vectors, which can be compared for equality based on their order and contents with the == operator. See this example.

The traversal goes backwards rather than forwards because it makes rebuilding the path easier (rather than ending up at the end node, with each parent the node before it, you end up at the start node, with each parent the node after it)

Data Structure Summary

Node would need to keep track of enough information for Area to identify it uniquely (via an array index or a name or something), as well as a parent node. The parent nodes should be set to NULL before the traversal to avoid weird behavior, since traversal will ignore any node with its parent set. This keeps track of the visited state too: visited is equivalent to (parent != NULL). Doing it this way also keeps you from having to keep track of the entire path in the queue, which would be very computationally intensive.

Area needs to maintain a list of Node, and needs a neighbor map, or a mapping of which nodes neighbor which other nodes. It's possible that this mapping could be generated on the fly with a function rather than being looked up from a table or some more typical approach. It should be able to provide the neighbors of a node to a caller. It might help to have a helper method that clears the parents of every node as well.

Path is basically a list type, containing an ordered list of nodes.

Queue is whatever FIFO queue is available. You could do it with a linked list.

I like how the syntax highlighting worked on my Wuggythovasp++.

Answer 5

At least as a start, you could try using/implementing something like Java's Arrays.toString() and using a map. Each arrangement would result in a different string, and thus it'll at least get somewhere.