그림 의 링크 실현

모든 도시 의 버스 정류장 은 하나의 그림 으로 볼 수 있 고 모든 국가의 도시 교통 은 하나의 그림 으로 볼 수 있 으 며 전체 지구의 모든 국 가 는 하나의 그림 으로 볼 수 있다.우리 학교의 모든 건축물 도 하나의 그림 으로 볼 수 있다. 그림 은 우리 의 데이터 구조 와 가장 가 깝 고 모델 링 을 할 때 자주 사용 하 는 데이터 구조 라 고 할 수 있다. 내 가 접촉 한 그림 은 기본적으로 모두 희소 도 이기 때문에 그림 의 링크 구 조 를 실현 해 보 자.
        우선, 그림 의 정점 클래스 를 정의 합 니 다.  정점 류 는 단독으로 하나의 종 류 를 만 드 는 것 이 가장 좋 고 확장 하기 편리 하 며 반드시 정점 의 좌표 와 정점 에 대응 하 는 변 의 지침 이 없어 서 는 안 된다.정점 클래스 에서 자신 이 필요 로 하 는 정 보 를 추가 할 수 있 습 니 다. 

package graph;

/**  
 *  Vertex : 
 * @author xuejupo  [email protected] 
 * create in 2015-11-30   7:07:03    
 */

public class Vertex {
	public Vertex(int value){
		this.value = value;
		this.edge = null;
	}
	
	//     
	int value;
	
	//    
	String name;
	
	//       
	Edge edge;

	public final int getValue() {
		return value;
	}

	public final void setValue(int value) {
		this.value = value;
	}

	public final Edge getEdge() {
		return edge;
	}

	public final void setEdge(Edge edge) {
		this.edge = edge;
	}
	
}

    변 류: 링크 는 이 변 이 가리 키 는 노드 좌표 와 다음 변 의 지침 이 없어 서 는 안 된다 는 것 을 나타 낸다.필요 에 따라 원 하 는 정 보 를 추가 할 수도 있다.

package graph;

/**  
 *  Edge : 
 * @author xuejupo  [email protected] 
 * create in 2015-11-30   7:03:06    
 */

public class Edge {
	public Edge(int iVex){
		this.iVex = iVex;
	}
	public Edge(int iVex,int value){
		this.iVex = iVex;
		this.value = value;
	}
	//        
	int iVex;
	
	//     
	
	int value;
	
	//       
	Edge next;

	public final int getiVex() {
		return iVex;
	}

	public final void setiVex(int iVex) {
		this.iVex = iVex;
	}

	public final Edge getNext() {
		return next;
	}

	public final void setNext(Edge next) {
		this.next = next;
	}
	
	
}

 그림 종류:  그림 류 는 하나의 대국 류 이다. 가장 중요 한 것 도 모든 노드 의 배열 이 있어 야 한다. 또한 실제 상황 에 따라 자신 이 원 하 는 정 보 를 추가 할 수 있다.  예 를 들 어 그림 속 의 노드 갯 수, 그림 속 의 갯 수 등 이다.

//        
	int num;

	//            
	boolean isVisited[];
	//        
	List<Vertex> vexs;
	//       
	public void initVisited(){
		this.isVisited = new boolean[num];
	}
	/**
	 *  graph.java      createTime:   7:19:11
	 */
	public Graph() {
		//          
		// this.vexs = Collections.synchronizedList(new ArrayList<Vertex>());
		this.vexs = new ArrayList<Vertex>();
	}
	
	/**  
	* getNumner:           
	* @return 
	* int         
	*/
	public int getNumner(){
		return this.num;
	}

	/**
	 * addVex:     
	 * 
	 * @return boolean     
	 */
	public void addVex(int value) {
		if (this.vexs == null) {
			throw new NullIsNotSupported("the graph is null");
		}
		this.num++;
		vexs.add(new Vertex(value));
	}

	/**
	 * addEdge:    
	 * 
	 * @param from
	 *                  
	 * @param to
	 *                   void     
	 */
	public void addEdge(int from, int to, int value) {
		if (from < 0 || to < 0 || from >= this.num || to >= this.num) {
			throw new UnexpectedException("     ");
		}
		Vertex vex = vexs.get(from);
		Edge edge = new Edge(to, value);
		Edge temp = vex.edge;
		if (temp == null) {
			vex.edge = edge;
			return;
		} 
		while(temp.next != null){
			temp = temp.next;
		}
		temp.next = edge;
	}

 깊이 와 넓이:
    깊이 를 옮 겨 다 니 는 것 은 재 귀적 인 것 으로 스 택 으로 옮 겨 다 니 는 것 과 같 습 니 다. 시작 노드 0 에서 출발 하여 한 걸음 한 걸음 깊이 들 어가 서 다시 깊이 들 어가 지 못 할 때 까지 점차적으로 물 러 나 고 재 귀적 으로 종료 노드 를 처리 합 니 다.

/**  
	* depthFirstTraverval:            
	* @param i 
	* void         
	*/
	public void depthFirstTraverval(int i){
		Vertex v = vexs.get(i);
		if(!isVisited[i]){
			visiteVer(i);
		}
		Edge e = v.edge;
		while(e != null){
			depthFirstTraverval(e.iVex);
			e = e.next;
		}
	}

 광 도 를 우선 으로 옮 기 는 것 은 대열 을 이용 하여 대열 의 선진 적 인 선 출 개념 을 이용 하여 시작 노드 에서 출발 하여 (1 층 으로 가정 할 수 있 음) 먼저 실제 노드 와 직접 연 결 된 노드 (2 층) 를 옮 긴 다음 에 2 층 노드 를 대열 에 넣 는 것 이다.그 다음 에 대기 열 에서 데 이 터 를 가 져 옵 니 다 (이때 얻 은 것 은 모두 2 층 입 니 다). 순서대로 노드 에 접근 하고 2 층 과 연 결 된 노드 (3 층) 를 대기 열 에 넣 습 니 다. 대기 열 이 비어 있 을 때 까지.이때 그림 은 시작 노드 부터 한 층 씩 옮 겨 다 녔 다.

/**  
	* breadthFirstTraverval:    i  ，         
	* @param i 
	* void         
	*/
	public void breadthFirstTraverval(int i){
		//       
		this.initVisited();
		//    
		Queue<Integer> q = new LinkedList<Integer>();
		q.offer(i);
		while(!q.isEmpty()){
			int temp = q.poll();
			Vertex v = vexs.get(temp);
			//         
			if(!isVisited[temp]){
				this.visiteVer(temp);
			}
			//      
			Edge e = v.edge;
			//                 
			while(e != null){
				q.offer(e.iVex);
				e = e.next;
			}
		}
	}

 테스트 방법:

public static void main(String[] args) {
		// TODO Auto-generated method stub
		Graph g = new Graph();
		g.addVex(1);
		g.addVex(3);
		g.addVex(9);
		g.addVex(10);
		g.addEdge(0, 1, 1);
		g.addEdge(1, 2, 1);
		g.addEdge(0, 3, 1);
		System.out.println(g.getNumner());
		g.initVisited();
		System.out.println("      ：");
		g.depthFirstTraverval(0);
		System.out.println("\r
      ：");
		g.breadthFirstTraverval(0);
		
	}

 결과:

4
      ：
1	3	9	10	
      ：
1	3	10	9