无向图的深度优先搜索

一.概述

所谓的深度优先搜索，指的是在搜索时，如果遇到一个结点既有子结点，又有兄弟结点，那么先找子结点，子节点找完了，再找兄弟结点。

无向图中，一条边在邻接表中出现两次，搜索子节点的时候需要判断此边是否之前被搜索过，如0-6 6-0 ，不能从6再往0方向区搜索，会重复。

从顶点0出发，遍历0的邻接表，找到第一个6 ；
继续递归dfs从6出发，遍历6的邻接表，0搜索过，找到4 ；
继续递归dfs从4出发，找到5；
继续递归dfs从5出发，遍历5的邻接表，找到3；
继续递归dfs从3出发，遍历3的邻接表，找到5搜索过，找到4 也搜索过，子节点搜索完毕，递归在此出口结束，开始退回去找兄弟节点；
往回返到5的邻接表，找3的兄弟节点，3搜过了，4搜过了，0搜过了，3完毕
往回返到4的邻接表，找5的兄弟节点，5搜过了，6搜过了，3搜过了，5完毕
往回返到6的邻接表，找4的兄弟节点，0搜索过，4搜索过，4完毕
往回返到0的邻接表，找6的兄弟节点，2没搜过！

二.实现

public class GraphDFS {
    private boolean[] marked;  //marked数组的索引代表了顶点！
    private int count;  //与s顶点相同的顶点的个数
7
    public GraphDFS(graph g, int s) {
    //初始化marked数组
        this.marked=new boolean[g.V()];   //marked和graph的定点数量一致都是 g.v()
    //初始化跟顶点s相通的顶点数量
        this.count=0;
        dfs(g,s); // 构造方法 调成员函数!!!       搜索与顶点相同的所有顶点
    }

    private void dfs(graph g,int v){  //使用深度优先搜索找出与v相通的顶点
    //将v标记为搜过
        marked[v]=true;
    //遍历当前顶点的邻接表(一个LinkedList)，如果搜过了就找下一个，如果没有则递归dfs深度搜索
        for (Integer k : g.adj(v)) {
            //判断当前k顶点有没有被搜索过
             if(!marked[k]){  //如果k没被搜索过则递归，如果已经搜过了则不进入递归,即递归出口
                dfs(g,k);  //递归dfs
            } 
        }
        //递归完后， 与s顶点相通的数量+1
        count++;
    }

    public int count(){  //获取与顶点s相通的所有顶点的总数
        return count;
    }

    public boolean marked(int w){  //返回顶点是否被搜索过
        return marked[w];
    }

    public static void main(String[] args) {
        //准备一个graph
        graph g = new graph(13);
        g.addEdge(0,5);
        g.addEdge(0,1);
        g.addEdge(0,2);
        g.addEdge(0,6);
        g.addEdge(5,3);
        g.addEdge(5,4);
        g.addEdge(3,4);
        g.addEdge(4,6);
        g.addEdge(0,5);

        g.addEdge(7,8);
        g.addEdge(9,11);
        g.addEdge(9,10);
        g.addEdge(9,12);

        //准备dfs搜索对象（dfs方法在构造方法中调用！一初始化就搜索完毕了）
        GraphDFS search = new GraphDFS(g, 0);//传入图g，起点为0
        //测试与某个顶点相同的数量
        int c = search.count();
        //测试某个顶点与起点是否相同
        System.out.println("与起点相通的顶点的个数为："+c);
  boolean m1 = search.marked(5);
        System.out.println("顶点5和0是否相通："+m1);

        boolean m2=search.marked(7);
        System.out.println("顶点7和0是否相通："+m2);
    }
}