无向图(Java)

说起无向图，最常用的两个算法就是深度优先搜索(DFS)和广度优先搜索(BFS)。在介绍这两种搜索方法之前，先给出有关图(Graph)的定义。

public class Graph {
    private final int V;//顶点数目
    private int E;//边的数目
    private Bag<Integer>[] adj;//邻接表
    public Graph(int V){
        this.V = V;
        this.E = 0;
        adj = (Bag<Integer>[])new Bag[V];
        for(int v = 0;v<V;v++){
            adj[v] = new Bag<Integer>();
        }
    }
    public Graph(In in){
        this(in.readInt());
        int E = in.readInt();
        for(int i = 0;i<E;i++){
            int v = in.readInt();
            int w = in.readInt();
            addEdge(v,w);
        }
    }
    public int V(){
        return V;
    }
    public int E(){
        return E;
    }
    public void addEdge(int v,int w){
        adj[v].add(w);
        adj[w].add(v);
        E++;
    }
    public Iterable<Integer> adj(int v){
        return adj[v];
    }
}

1、深度优先搜索(DFS)
顾名思义，所谓深度优先就是在搜索过某个结点后就以该结点作为起点继续搜索其孩子结点而不是其兄弟结点。

代码：

public class DepthFirstSearch {
    private boolean[] marked;
    private int count;
    public DepthFirstSearch(Graph G,int s){
        marked = new boolean[G.V()];
        dfs(G,s);
    }
    private void dfs(Graph G,int v){
        marked[v] = true;
        count++;
        for(int w:G.adj(v))
            if(!marked[w])
                dfs(G,w);
    }
    public boolean marked(int w){
        return marked[w];
    }
    public int count(){
        return count;
    }

}

分析：
主要函数dfs接受图和起点作为参数，一进入此方法就将当前结点标记为已访问，再进入for循环，其循环的范围就是当前结点的邻接点(G.adj(v))，如果发现邻接点没有被访问则继续，若已经被访问则跳出此循环，继续访问下一个(兄弟)结点。

2、广度优先搜索(BFS)
顾名思义，所谓广度优先就是在搜索过某个结点后就以该结点作为起点继续搜索其兄弟结点而不是其孩子结点。

代码：

public class BreadthFirstPaths {
    private boolean[] marked;
    private int[] edgeTo;
    private final int s;//起点
    public BreadthFirstPaths(Graph G,int s){
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        this.s = s;
        bfs(G,s);
    }
    private void bfs(Graph G,int s){
        Queue<Integer> queue = new Queue<Integer>();
        marked[s] = true;//标为起点
        queue.enqueue(s);//加入队列
        while(!queue.isEmpty()){
            int v = queue.dequeue();//从队列中删去下一顶点
            for(int w:G.adj(v)){
                if(!marked[w]){
                    edgeTo[w] = v;
                    marked[w] = true;
                    queue.enqueue(w);//添加进队列
                }
            }
        }
    }
}

分析：
bfs没有采用递归而是采用队列作为中介进行存储，通过对bfs函数进行分析可知，我们以s作为起点，然后通过获得邻接表得到其邻接结点(G.adj(v))，所以当与起点相邻接的结点被访问完之后就开始将第一个邻接点作为起点继续上述操作。

这其中的缺少的数据结构，比如Queue，Bag可以到http://algs4.cs.princeton.edu/code 下载。