java 实现DFS和BFS

 摘抄自：http://blog.csdn.net/lemon_tree12138/article/details/47319659

 1.图中的节点：    public class GraphNode {

 public List<GraphEdge> edgeList = null;    private String label = "";    public GraphNode(String label) {   this.label = label;   if (edgeList == null) {    edgeList = new ArrayList<GraphEdge>();//建一个集合为每个节点存储边   }  }    /**   * 给当前节点添加一条边   * GraphNode   * @param edge   *    添加的边   */  public void addEdgeList(GraphEdge edge) {   edgeList.add(edge);  }    public String getLabel() {   return label;  } }

 2.图中的边：

 public class GraphEdge {

 private GraphNode nodeLeft;    private GraphNode nodeRight;

 /**   * @param nodeLeft   *    边的左端   * @param nodeRight   *    边的右端   */  public GraphEdge(GraphNode nodeLeft, GraphNode nodeRight) {  //   this.nodeLeft = nodeLeft;   this.nodeRight = nodeRight;  }

 public GraphNode getNodeLeft() {   return nodeLeft;  }

 public GraphNode getNodeRight() {   return nodeRight;  }   }

 3.把节点和边组合成一个图结构：    public class MyGraph {

 private List<GraphNode> nodes = null;    public void initGraph(int n) {   if (nodes == null) {    nodes = new ArrayList<GraphNode>();   }      GraphNode node = null;   for (int i = 0; i < n; i++) {    node = new GraphNode(String.valueOf(i));    nodes.add(node);   }  }    public void initGraph(int n, boolean b) {   initGraph(n);   GraphEdge edge01 = new GraphEdge(nodes.get(0), nodes.get(1));   GraphEdge edge02 = new GraphEdge(nodes.get(0), nodes.get(2));   GraphEdge edge13 = new GraphEdge(nodes.get(1), nodes.get(3));   GraphEdge edge14 = new GraphEdge(nodes.get(1), nodes.get(4));   GraphEdge edge25 = new GraphEdge(nodes.get(2), nodes.get(5));   GraphEdge edge26 = new GraphEdge(nodes.get(2), nodes.get(6));   GraphEdge edge37 = new GraphEdge(nodes.get(3), nodes.get(7));   GraphEdge edge47 = new GraphEdge(nodes.get(4), nodes.get(7));   GraphEdge edge56 = new GraphEdge(nodes.get(5), nodes.get(6));         nodes.get(0).addEdgeList(edge01);   nodes.get(0).addEdgeList(edge02);   nodes.get(1).addEdgeList(edge13);   nodes.get(1).addEdgeList(edge14);   nodes.get(2).addEdgeList(edge25);   nodes.get(2).addEdgeList(edge26);   nodes.get(3).addEdgeList(edge37);   nodes.get(4).addEdgeList(edge47);   nodes.get(5).addEdgeList(edge56);  }    public void initGraph() {   initGraph(8, false);  }    public List<GraphNode> getGraphNodes() {   return nodes;  } }

 啦啦啦啦啦啦啦啦啦啦啦有了图的结构，我们就可以进行一些实际的操作了。

 深度优先搜索（你也是很帮帮的哦）

 public class DFSearch {    /**   * 深度遍历   * DFSearch   * @param node   *    当前节点   * @param visited   *    被访问过的节点列表   */  public void searchTraversing(GraphNode node, List<GraphNode> visited) {   // 判断是否遍历过   if (visited.contains(node)) {    return;   }      visited.add(node);   System.out.println("节点：" + node.getLabel());//功能处理模块   for (int i = 0; i < node.edgeList.size(); i++) {    searchTraversing(node.edgeList.get(i).getNodeRight(), visited);//递归深层次遍历   }  } }

 广度优先搜索：

 public class BFSearch {    /**   * 广度优先搜索   * BFSearch   * @param node   *    搜索的入口节点   */  public void searchTraversing(GraphNode node) {   List<GraphNode> visited = new ArrayList<GraphNode>(); // 已经被访问过的元素   Queue<GraphNode> q = new LinkedList<GraphNode>(); // 用队列存放依次要遍历的元素   q.offer(node);//向队列添加一个元素成功则返回true，如果队列已满则返回false      while (!q.isEmpty()) {    GraphNode currNode = q.poll();//移除并返回队列头部的元素，如果队列为空则返回null    if (!visited.contains(currNode)) {     visited.add(currNode);     System.out.println("节点：" + currNode.getLabel());     for (int i = 0; i < currNode.edgeList.size(); i++) {      q.offer(currNode.edgeList.get(i).getNodeRight());     }    }   }  } }