# 深度优先遍历

```java
//得到第一个邻接结点的下标w
    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;
    }

    /**
     *深度优先遍历
     * @param isVisited ,记录某个结点是否被访问
     * @param i         某个结点的下标
     */
    public void dfs(boolean[] isVisited, int i){
        //输出访问的结点
        System.out.print( getValueByIndex(i)+"->");
        //将被访问过的结点置为已访问
        isVisited[i] = true;
        //查找结点i的第一个邻接结点
        int w = getFirstNeighbor(i);
        //如果存在就继续访问
        while (w != -1){
            //还需要判断这个结点是否被访问过
            if ( ! isVisited [w] ){
                //没被访问过，那我们就递归,
                dfs(isVisited,w);
            }
            //如果已经被访问过了，就对w的下一个邻接结点进行查找
            w = getNextNeighbor(i,w);
        }
    }
    //对dfs重载，遍历所有的结点
    public void dfs(){
        //遍历所有的结点，进行dfs回溯
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]){
                dfs(isVisited,i);
            }
        }
    }


```
