package com.cust.grape;import java.util.ArrayList;import java.util.HashSet;import java.util.LinkedList;import java.util.List;import java.util.Queue;import java.util.Set;/** *  * 描述:图的深度遍历和广度遍历 * 深度遍历： * 	 * 广度遍历： *  * @author cookie */public class DeptSearch {	public static void main(String[] args) {		Node a = new Node(1);		Node b = new Node(2);		Node c = new Node(3);		Node d = new Node(4);		Node e = new Node(5);		Node f = new Node(6);		Node g = new Node(7);		Node h = new Node(8);		Node k = new Node(9);		Arc ab = new Arc(a, b);		Arc ac = new Arc(a, c);		Arc ad = new Arc(a, d);		Arc be = new Arc(b,e);		Arc bf = new Arc(b,f);		Arc cg = new Arc(c,g);		Arc ch = new Arc(c,h);		Arc ek = new Arc(e,k);		a.aList.add(ab);		a.aList.add(ac);		a.aList.add(ad);		b.aList.add(be);		b.aList.add(bf);		c.aList.add(cg);		c.aList.add(ch);		e.aList.add(ek);		System.out.print("广度遍历：");		widthSort(a);		System.out.println();		System.out.print("深度遍历：");		List<Node> visited = new ArrayList<Node>();		deptSort(a,visited);	}	/**深度遍历：递归向下*/	public static void deptSort(Node a,List<Node> visited){		if(visited.contains(a)){//访问过，直接返回			return;		}else{			visited.add(a);			System.out.print(a.val+" ");			for (int i = 0; i < a.aList.size(); i++) {				deptSort(a.aList.get(i).end,visited);			}		}			}	/**广度遍历：非递归*/	public static void widthSort(Node start){		Set<Node> visited = new HashSet<Node>();		Queue<Node> queue =new LinkedList<Node>();		queue.offer(start);//首元素进栈		while(!queue.isEmpty()){//栈不为空时			Node n = queue.poll();			if(!visited.contains(n)){//没有访问过，继续；访问过的元素跳过，继续下一个				System.out.print(n.val+" ");				visited.add(n);				for (int i = 0; i < n.aList.size(); i++) {//被弹出元素的下一行元素，并非所有的下一行元素					queue.offer(n.aList.get(i).end);//节点关系的end节点				}			}		}	}		}/** *  * 描述:节点 * @author cookie */class Node{	public List<Arc> aList = new ArrayList<Arc>();	public Integer val;//节点值	public Node(Integer val) {		this.val = val;	}} /** *  * 描述:节点之间的关系 * @author cookie */class Arc{	public Node start;	public Node end;	public Arc(Node start, Node end) {		this.start = start;		this.end = end;	}}