深度优先遍历（Depth First Search）,从图中某个顶点V出发，访问此顶点，然后从v顶点的未被访问的邻接点出发，深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。以下图为例

图的深度优先遍历 - 图1

BFS示例

定义图的数据结构

  1. pbulic class Graph {
  3.     public String[] vertexs;
  4.     public int[][] edageMatrix;
  6.     public Graph(String[] vertexs) {
  7.         this.vertexs = vertexs;
  8.         this.edageMatrix = new int[vertexs.length][vertexs.length];
  9.     }
  11.     public void addEdage(int i, int j) {
  12.         this.edageMatrix[i][j] = 1;
  13.     }
  15.     public int[] getAdjVertex(int i) {
  16.         return this.edageMatrix[i];
  17.     }
  18. }

使用深度优先遍历图的顶点，

  1. public static void main(String[] args) {
  2.     String[] vertexs = {"A0", "B1", "C2", "D3", "E4", "F5", "G6", "H7"};
  3.     Set<Integer> visited = new LinkedHashSet<Integer>();
  4.     Graph graph = new Graph(vertexs);
  5.     graph.addEdage(0, 1);
  6.     graph.addEdage(0, 5);
  8.     graph.addEdage(1, 2);
  9.     graph.addEdage(1, 6);
  11.     graph.addEdage(2, 3);
  13.     graph.addEdage(5, 6);
  14.     graph.addEdage(5, 4);
  15.     graph.addEdage(5, 7);
  16.     graph.addEdage(6, 3);
  19.     DFS(0, visited, graph);
  21.     for (int i : visited) {
  22.         System.out.print(vertexs[i] + "->");
  23.     }
  24. }

DFS深度优先遍历

  1. public static void DFS(int index, Set<Integer> visited, Graph graph) {
  2.     if (visited.contains(index)) {
  3.         return;
  4.     }
  5.     visited.add(index);
  6.     int[] adj = graph.getAdjVertex(index);
  7.     for (int i = 0; i < adj.length; i++) {
  8.         if (adj[i] == 1) DFS(i, visited, graph);
  9.     }
  10.   }