mygraph.java

java的DFS(Depth-first search )和BFS(Breadth-first search)的实现

class myGraph implements Graph
{
	final int VISITED = 1;
	final int UNVISITED = -1;

	//implement your class myGraph here
	private int[][] matrix;
	private int edgeNum;
	public int[] mark;

	public myGraph( int n )
	{
		mark = new int[n];
		matrix = new int[n][n];
		edgeNum = 0;
	}

    //Number of vertices
	public int n()
	{
		return mark.length;
	}

    //Number of edges
	public int e()		
	{
		return edgeNum;
	}

	//Get first edge for vertex
	public Edge first(int v)
	{
		for ( int i = 0; i < mark.length; i++ )
		{			
			//System.out.println( "!" + matrix[v][i] );
			if ( matrix[v][i] != 0)
			{				
				return new myEdge( v, i );
			}
		}

		return null;
	}
    
	//Get next edge for vertex
	public Edge next(Edge w)
	{
		if ( w == null )
		{
			
			return null;
		}

		for ( int i = w.v2() + 1; i < mark.length; i++ )
		{
			
			if ( matrix[w.v1()][i] != 0 )
			{
				return new myEdge( w.v1(), i );
			}
		}

		return null;
	}

    //True if this is an edge
	public boolean isEdge(Edge w)
    {
		if ( w == null )
		{			
			return false;
		}

		return matrix[w.v1()][w.v2()] != 0;
	}
    
	//True if this is an edge
	public boolean isEdge(int i, int j)

	{
		return matrix[i][j] != 0;
	}
    
	//Where edge came from
	public int v1(Edge w)
	{
		return w.v1();
	}

    //Where edge goes to
	public int v2(Edge w)
	{
		return w.v2();
	}

    //Set edges
	public void setEdge(int i, int j)	
	{
		matrix[i][j]  = 1;		
		edgeNum++;
	}

	//we don't use delEdge methods this lab, but you should finish it after lab
	public void delEdge(int i, int j) {}			//Delete edge(i, j)
	public void delEdge(Edge w){}				//Delete edge w

    //Set Mark for v
	public void setMark(int v, int val)	
    {
		mark[v] =val;
	}

    //Get Mark for v
	public int getMark (int v)		
	{
		return mark[v];
	}

	//end of your implementing

	public void setUNVISITED(Graph G)				//initialize the Marks to UNVISITED
	{
		for(int v = 0; v < G.n(); v++)
			G.setMark(v,UNVISITED);
	}

	//finish following two method
	public void DFS(Graph G, int start)				//depth-first search
	{
		//fill the method with your code

		for ( int v = 0 ; v < ((myGraph)G).n(); v++ )
		{
			if (((myGraph)G).getMark(v) == UNVISITED )
			{
				DFShelp( G, v );
			}
		}			
	}

	private void DFShelp( Graph G, int start)
	{
		System.out.print( start + 1 + " " );

		G.setMark( start, VISITED );

		for ( myEdge w = (myEdge)((myGraph)G).first(start); ((myGraph)G).isEdge((Edge)w); w = (myEdge)((myGraph)G).next(w) )
		{
			//System.out.println( ((myGraph)G).isEdge(w));
			if ( ((myGraph)G).getMark(((myGraph)G).v2(w)) == UNVISITED )
			{
				DFShelp( G,((myGraph)G).v2(w) );
			}
		}	
	}




	public void BFS(Graph G, int start)				//breadth-first search
	{
		//fill the method with your code

		for ( int v = 0 ; v < ((myGraph)G).n(); v++ )
		{
			if (((myGraph)G).getMark(v) == UNVISITED )
			{
				BFShelp( G, v );
			}
		}		
	}

	private void BFShelp( Graph G, int start)
	{
		Queue queue = new Queue( G.n() );

		queue.enqueue( start );
		((myGraph)G).setMark( start, VISITED );

		while ( !queue.isEmpty() )
		{
			int temp = queue.dequeue();
			System.out.print( temp + 1 + " " );

			for ( myEdge w = (myEdge)((myGraph)G).first(temp); ((myGraph)G).isEdge(w); w = (myEdge)((myGraph)G).next(w) )
			{
				if ( ((myGraph)G).getMark( ((myGraph)G).v2(w) ) == UNVISITED )
				{
					((myGraph)G).setMark( ((myGraph)G).v2(w), VISITED );
					queue.enqueue( ((myGraph)G).v2(w) );
				}
			}
		}
	}

	
	//test your lab
	public static void main(String[] args) 
	{
		//Construct your graph according to the doc
		myGraph mg = new myGraph( 12 );

		mg.setEdge( 0, 1 );
		mg.setEdge( 0, 10 );
		mg.setEdge( 0, 11 );
		mg.setEdge( 1, 2 );
		mg.setEdge( 1, 3 );
		mg.setEdge( 1, 4);
		mg.setEdge( 2, 5 );
		mg.setEdge( 2, 6 );
		mg.setEdge( 3, 6 );
		mg.setEdge( 3, 9 );
		mg.setEdge( 4, 9 );
		mg.setEdge( 5, 7 );
		mg.setEdge( 6, 7 );
		mg.setEdge( 11,8 );
			

	//	System.out.println( mg.n() + " " + mg.e() );
		
		//testing your code
		System.out.println("========test========");
		mg.setUNVISITED(mg);
		System.out.println("====test your DFS====");
		System.out.println("your DFS should be 1 2 3 6 8 7 4 10 5 11 12 9");
		System.out.print("your DFS is        ");
		mg.DFS(mg, 0);					//traversal from the first vertex
		System.out.println();
		mg.setUNVISITED(mg);
		System.out.println("====test your BFS====");
		System.out.println("your BFS should be 1 2 11 12 3 4 5 9 6 7 10 8");
		System.out.print("your BFS is        ");
		mg.BFS(mg, 0);					//traversal from the first vertex
		System.out.println();
	}
}