distgraph.java

国外的数据结构与算法分析用书

/* DistGraph.java
 * ---------------------------------------------
 * Copyright (c) 2001 University of Saskatchewan
 * All Rights Reserved
 * --------------------------------------------- */
 
import dslib.graph.*;
import dslib.dispenser.LinkedQueueUos;

/**	A search graph with a breadth-first search to find shortest distances.  */
public class DistGraph extends SearchGraphLinkedRepUos
{
	/**	Construct a new undirected graph with capacity for up to cap vertices. <br>
		Analysis: Time  = O(cap)
		@param cap maximum number of verticies in the graph */
	public DistGraph(int cap)
	{
		super(cap);
	}

	/**	Return a new vertex that is appropriate for this graph, i.e., a DistVertex. <br>
		Analysis: Time = O(1)
		@param n The name of the vertex that is returned
		@param id The id of the vertex that is returned */
	protected VertexUos createNewVertex(String n, int id)
	{
		return new DistVertex(n, id);
	}

	/**	Set all the vertices to unreached. 
		Analysis: Time = O(n), where n = number of vertices */
	public void setAllUnreached()
	{
		GraphPositionUos position = currentPosition();
		goFirst();
		while (!after())
		{
			((SearchVertexUos)item()).setReached(false);
			goForth();
		}
		goPosition(position);
	}
  
	/**	Breadth-first search of the graph to calculate distances. 
		Analysis: Time = O(n + m), where n = number of vertices, and m = number of edges */
	public void bfs(DistVertex s)
	{		
		GraphPositionUos position = currentPosition();              // step 1
		setAllUnreached();                                          // step 2
		LinkedQueueUos q = new LinkedQueueUos();                    // step 3
		s.setReached(true);                                         // step 4
		s.setDist(0);                                               // step 5
		q.insert(s);                                                // step 6
		while (!q.isEmpty())                                        // step 7 
		{	
			DistVertex currentVertex = (DistVertex)q.item();           // step 8
			q.deleteItem();                                            // step 9  
			eGoFirst(currentVertex);                                   // step 10

			while (!eAfter())                                          // step 11
			{
				DistVertex adjDistVertex = (DistVertex) adjItem();        // step 12
				if (!adjDistVertex.reached())                             // step 13
				{
					adjDistVertex.setReached(true);                          // step 14
					adjDistVertex.setDist(currentVertex.dist() + 1);         // step 15
					q.insert(adjDistVertex);                                 // step 16
				}
				eGoForth();                                               // step 17
			}
		}
		goPosition(position);                                       // step 18
	}

}