深度优先搜索的基本思想

1.深度优先搜索，从初始访问节点出发，初始访问节点可能有多个邻接节点，深度优先搜索的策略就是首先访问第一个邻接节点，然后再以这个被访问的邻接节点为初始节点，访问它的第一个邻接节点。可以这样理解：每次都在访问完当前节点后首先访问当前节点的第一个邻接节点

2.我们可以看到，这样的访问策略是优先往纵向挖掘深入，而不是对一个节点的所有邻接节点进行横向访问

3.显然，深度优先搜索是一个递归的过程

深度优先按搜索算法步骤

1.访问初始节点 v，并标记节点 v 为已访问

2.查找节点 v 的第一个邻接节点 w

3.若 w 存在，则继续执行 4，如果 w 不存在，则回到第 1 步，将从 v 的下一个节点继续

4.若 w 未被访问，对 w 进行深度优先遍历递归（即把 w 当作另一个 v，然后进行步骤 1 2 3）

5.查找节点 v 的 w 邻接节点的下一个邻接节点，转到步骤 3

public class Graph {     private ArrayList vertexList;  //存储顶点的集合     private int[][] edges;  //存储图对应的邻接矩阵     private int numOfEdges;  //表示边的数目     //定义一个数组 boolean[]，记录某个节点是否被访问     private boolean[] isVisited;      public static void main(String[] args) {         //测试         int n = 5;  //节点的个数         String[] Vertexs = {"A", "B", "C", "D", "E"};         //创建图对象         Graph graph = new Graph(n);         //循环的添加顶点         for (String vertex : Vertexs) {             graph.insertVertex(vertex);         }          //添加边         // A-B  A-C  B-C  B-D  B-E         graph.insertEdge(0, 1, 1);         graph.insertEdge(0, 2, 1);         graph.insertEdge(1, 2, 1);         graph.insertEdge(1, 3, 1);         graph.insertEdge(1, 4, 1);          graph.showGraph();          //测试 dfs         System.out.println("深度遍历");         graph.dfs();     }      //构造器     public Graph(int n) {         //初始化矩阵和 vertexList         edges = new int[n][n];         vertexList = new ArrayList(n);         numOfEdges = 0;         isVisited = new boolean[n];     }      //得到第一个邻接节点的下标 w     /**      *      * @param index      * @return  如果存在，返回对应下标，否则返回 -1      */     public int getFirstNeighbor(int index) {         for (int j = 0;j < vertexList.size(); j++) {             if (edges[index][j] > 0) {                 return j;             }         }         return -1;     }      //根据前一个邻接节点的下标来获取下一个邻接节点     public int getNextNeighbor(int v1, int v2) {         for (int j = v2 + 1; j < vertexList.size(); j++) {             if (edges[v1][j] > 0) {                 return j;             }         }         return -1;     }      //深度优先搜索算法     private void dfs(boolean[] isVisited, int i) {         //首先我们访问该节点，输出         System.out.print(getValueByIndex(i) + " -> ");         //将节点设置为已经访问         isVisited[i] = true;         //查找节点 i 的第一个邻接节点 w         int w = getFirstNeighbor(i);         while (w != -1) {  //说明存在             if (!isVisited[w]) {                 dfs(isVisited, w);             }             //如果 w 节点已经被访问过             w = getNextNeighbor(i, w);         }     }      //对 dfs 进行一个重载，遍历我们所有的节点，并进行 dfs     public void dfs() {         //遍历所有的节点，进行 dfs （回溯）         for (int i = 0; i < getNumOfEdges(); i++) {             if (!isVisited[i]) {                 dfs(isVisited, i);             }         }     }      //图中常用的方法     //返回节点的个数     public int getNumOfVertex() {         return vertexList.size();     }     //返回边的个数     public int getNumOfEdges() {         return numOfEdges;     }     //返回节点 i(下标)对应的数据 0->"A" 1->"B" 2->"C"     public String getValueByIndex(int i) {         return vertexList.get(i);     }     //返回 v1 和 v2 的权值     public int getWeight(int v1, int v2) {         return edges[v1][v2];     }     //显示图对应的矩阵     public void showGraph() {         for (int[] link : edges) {             System.out.println(Arrays.toString(link));         }     }      //插入节点     public void insertVertex(String vertex) {         vertexList.add(vertex);     }      //添加边     /**      *      * @param v1  代表第一个顶点对应的下标      * @param v2  代表第二个顶点对应的下标      * @param weight      */     public void insertEdge(int v1, int v2, int weight) {         edges[v1][v2] = weight;         edges[v2][v1] = weight;         numOfEdges++;     } }