/*
 * BFSearch.java
 *
 *    A class implementing a Breadth First Search on a graph.
 *
 * Copyright (c) Renaud Waldura, Fri Jun  9 19:46:55 1995
 */

package graph;

import awt.Color;



public
class BFSearch
    extends GraphSearch
{
    
    public
    void search (Graph g)
    {
	g.paint(Color.white);   // paint all the graph vertices with white
	g.mark(false);          // unmark the whole graph
	refresh(null);          // and redraw it

	Vertex r = g.root();	// the root is painted grey
	g.paint(r, Color.gray);       refresh(g.box(r));

	java.util.Vector queue = new java.util.Vector();	
	queue.addElement(r);	// and put in a queue


	while (!queue.isEmpty())
	{
	    Vertex u = (Vertex) queue.firstElement();
	    queue.removeElement(u); // extract a vertex from the queue

	    g.mark(u, true);          refresh(g.box(u));

	    int dp = g.degreePlus(u);

	    for (int i = 0; i < dp; i++) // look at its successors
	    {
		Vertex v = g.ithSucc(i, u);

		if (Color.white == g.color(v))
		{		    
		    queue.addElement(v);		    
		    g.paint(v, Color.gray);   refresh(g.box(v));
		}
	    }

	    g.paint(u, Color.black);  refresh(g.box(u));
	    g.mark(u, false);         refresh(g.box(u));	    
	}
    }

}