graph.java

Java实现的常用数据结构算法

package graph;
import java.awt.Point;
 class Graph implements Cloneable{
	private boolean[][] edges;
	private Object[] labels;
	public Graph(int n){
		edges=new boolean[n][n];
		labels=new Object[n];
	}
	public void setLabels(Object[] obj){
		int len=labels.length;
		for(int i=0;i<len;i++){
			labels[i]=obj[i];
		}
	}
	public void addEdge(int source ,int target){
		edges[source][target]=true;
	}
	
	public Object clone(){
		Graph answer;
		try{
			answer=(Graph)super.clone();
		}
		catch(CloneNotSupportedException e)
		{
			throw new RuntimeException
			("this class does not implement Clonesable");
		}
		answer.edges=(boolean[][])edges.clone();
		answer.labels=(boolean[][])labels.clone();
		return answer;
	}
	public Object getLabel(int vertex){
		return labels[vertex];
	}
	public boolean isEdge(int source ,int target){
		return edges[source][target];
	}
	public int[] neighbors(int vertex){
		int i;
		int count;
		int[] answer;
		count=0;
		for( i=0;i<labels.length;i++){
			if(edges[vertex][i])
			count++;
		}
		answer=new int[count];
		count=0;
		for( i=0;i<labels.length;i++){
			if(edges[vertex][i])
			answer[count++]=i;
		}
		return answer;
	}
	public void removeEdge(int source,int target){
		edges[source][target]=false;
	}
	public void setLabel(int vertex,Object newLabel)
	{
		labels[vertex]=newLabel; 
	}
	public int size(){
		return labels.length;
	}
	public static void dfr(Graph g,int v,boolean[] marked){
		int[] connections=g.neighbors(v);
		int i;
		int nextNeighbor;
		marked[v]=true;
		Point p=(Point)g.getLabel(v);
		System.out.println("x->"+p.x+" y->"+p.y);
		for(i=0;i<connections.length;i++){
			nextNeighbor=connections[i];
			if(!marked[nextNeighbor])
			dfr(g,nextNeighbor,marked);
		}
	}
	public static void dfPrint(Graph g,int start){
		boolean[] marked=new boolean[g.size()];
		dfr(g,start,marked);
	}
	public static void main(String args[]){
		Graph g=new Graph(6);
		boolean[] visited=new boolean[6];
		Point[] p=new Point[]{
			new Point(1,1),new Point(1,2),
			new Point(2,1),new Point(2,2),
			new Point(3,1),new Point(3,2)
		};
		g.setLabels(p);
		g.addEdge(0,1);
		g.addEdge(1,2);
		g.addEdge(5,0);
		g.addEdge(1,2);
		g.addEdge(2,4);
		g.addEdge(3,4);
		g.addEdge(3,5);
		g.addEdge(2,5);
		dfr(g,0,visited);
		
	}
}