图的BFS和DFS

图的遍历对于图这类题目来说非常重要，但是图的实现又非常的难。在这里我介绍下图的广度优先遍历和深度优先遍历，讲一下其中的算法思想。

1.图的存储结构

邻接矩阵表示：

DA2A674FD8873E6A42FFC1BCE0DFCD26.jpg

图的邻接矩阵存储结构定义如下：

    int n;
    boolean[][] a;
    Node(int n){
        this.n=n;
        a = new boolean[n][n];
    }
    void addEdge(int i, int j) {
        a[i][j] = true;
    }
    void removeEdge(int i, int j) {
        a[i][j] = false;
    }
    boolean hasEdge(int i, int j) {
        return a[i][j];
    }

邻接矩阵表示法的时间复杂度为O(n^{2)，空间复杂度也是O(n}2)。n代表图中顶点的个数。

邻接表表示：

BA4F709248944B0E15982967F382428A.jpg

图的邻接表存储结构定义如下：

   //顶点的数量
    private int V;
    //邻接表-数组类型的链表
    private LinkedList<Integer> adj[];

    //构造一个图
    DepthFirstSearch(int  v){
        V = v;
        //数组链表
        adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i]=new LinkedList();
        }
    }

    //加入与顶点v相连的边v-w
    void addEdge(int v,int w){
        adj[v].add(w);
    }

时间复杂度为：O（V + E）其中V是图中顶点的数量，E是图中边的数量 。

还是看以前的书比较有亲和感！

2.广度优先遍历（Breadth-First-Search，BFS）

广度优先遍历类似与二叉树的层序遍历。它是一种分层的查找过程，每向前走一步能访问一批顶点，不像深度优先遍历那样有往回退的情况，因此它不是一个递归的算法。为了实现逐层的访问，算法必须借助一个辅助队列，以记忆正在访问顶点的下一层顶点。

package com.zhoujian.solutions.dataStructure.graph;
import java.util.*;
/**
 * @author zhoujian123@hotmail.com 2018/4/26 10:28
 * 图的广度优先遍历----借助队列
 * 广度优先遍历类似于二叉树的层序遍历
 * 图是用邻接表来存储（对于稀疏图来说，邻接表比较合适）
 * 时间复杂度：O(V+E)，其中V是图中顶点的数量，E是图中边的数量
 */
public class BreadthFirstSerch {
    private int V; //顶点
    private LinkedList<Integer> adj[]; //领接表
    //构造器，利用链表。v是顶点的个数
    BreadthFirstSerch(int v){
        V=v;
        adj = new LinkedList[v];
        for (int i = 0; i <v; i++) {
            adj[i]=new LinkedList();
        }
    }
    //加入一条边到图中
    void addEdge(int v,int w){
        adj[v].add(w);
    }
    //从给定的顶点开始遍历
    void BFS(int s){
        //默认将所有的顶点设置为未被访问（false）
        boolean visited[] = new boolean[V];
        //创建一个队列
        LinkedList<Integer> queue = new LinkedList<Integer>();
        //把当前顶点设置为已访问并且入队
        visited[s] = true;
        queue.add(s);
        while (queue.size()!=0){
            //出队并打印出来
            s=queue.poll();
            System.out.println(s+"");
            //获取与s相关联的全部的顶点，如果邻接的点未被访问，则设置为已被访问且入队
            //i是一种list列表的迭代器，用于存储相邻节点的列表
            ListIterator<Integer> i = adj[s].listIterator();
            while (i.hasNext()){
                int n = i.next();
                if (!visited[n]){
                    visited[n]=true;
                    queue.add(n);
                }
            }
        }
    }

    public static void main(String[] args) {
        BreadthFirstSerch g = new BreadthFirstSerch(4);
        g.addEdge(0,1);
        g.addEdge(0,2);
        g.addEdge(1,2);
        g.addEdge(2,0);
        g.addEdge(2,3);
        g.addEdge(3,3);
        //这个函数只能从指定顶点开始遍历。要是打印所有顶点，可以需要修改BFS函数，逐个从所有节点开始遍历
        System.out.println("广度优先遍历从0开始遍历");
        g.BFS(0);
        System.out.println("广度优先遍历从1开始遍历");
        g.BFS(1);
        System.out.println("广度优先遍历从2开始遍历");
        g.BFS(2);
        System.out.println("广度优先遍历从3开始遍历");
        g.BFS(3);
    }

}

image.png

3.深度优先遍历（Depath-First-Search，DFS）

深度优先遍历类似于树的先序遍历。DFS算法是一个递归的算法，需要借助一个递归的工作栈，故它的空间复杂度为O(V)。总的时间复杂度为O(V+E)。

package com.zhoujian.solutions.dataStructure.graph;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;
/**
 * @author zhoujian123@hotmail.com 2018/4/25 21:19
 * 图的深度优先遍历：需要借助栈
 * 深度优先遍历类似于二叉树的先序遍历
 * 使用邻接表表示
 * 时间复杂度：当以领接表表示时，查找所有顶点的邻接点所需为O(V)，然后每条边至少访问一次所需时间为O(E),
 * 总的时间复杂度为O(V+E)
 *
 */
public class DepthFirstSearch {

    //顶点的数量
    private int V;
    //邻接表-数组类型的链表
    private LinkedList<Integer> adj[];

    //构造一个图
    DepthFirstSearch(int  v){
        V = v;
        //数组链表
        adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i]=new LinkedList();
        }
    }

    //加入与顶点v相连的边v-w
    void addEdge(int v,int w){
        adj[v].add(w);
    }
    /**
     * 从顶点v开始深度遍历
     * @param v 顶点v
     * @param visited 访问标识符
     */
    void DFSUtil(int v,boolean visited[]){

        //把当前节点设置为被访问并打印出来
        visited[v]=true;
        System.out.println(v+" ");

        ListIterator<Integer> i = adj[v].listIterator();
        while (i.hasNext()){
            //返回与v相邻的节点
            Integer n = i.next();
            if (!visited[n]){
                DFSUtil(n,visited);
            }
        }

    }

    void DFS(int v){
        //初始化所有顶点并默认为false（数组）
        boolean[] visited = new boolean[V];
        DFSUtil(v,visited);
    }

    public static void main(String[] args) {
        DepthFirstSearch g = new DepthFirstSearch(4);
        g.addEdge(0,1);
        g.addEdge(0,2);
        g.addEdge(1,2);
        g.addEdge(2,0);
        g.addEdge(2,3);
        g.addEdge(3,3);
        System.out.println("深度优先遍历从顶点2开始");
        g.DFS(2);
    }
}

image.png