图和图的BFS与DFS

图的基本介绍

图和树一样，也是一种数据结构，不过这种数据结构恐怕是来得复杂了那么一点点。图一般由节点(Vertex) 与 边（Edge）来组成，

其中边是否是有方向的又将图分为有向图和无向图。有时边还是带有权值的，这时图被称为带权图。

图的表示的方式也有很多样，这里我们采用的是最简单的邻接矩阵来表示图。不要看到矩阵就嗷嗷嗷的~其实这里就是一个二维的数组而已，和线代没关系的，不要慌嘛。

图的创建

看其实图和树还是有一点儿像的，但如果使用树的方式去构建图的话，效率就会变得特别的低下，所以我们要考虑其他的表示图的方案。

表示顶点

创建图类的第一步是要创建一个Vertex类保存顶点和边。这个类的作用与链表和二叉搜索树的Node类一样。Vertex类有两个数据成员： 一个用于标识顶点，另一个是表示这个顶点是否被访问过的布尔值。分别命名为label 和 wasVisited.这个类只需要一个函数，那就是为顶点的数据成员设定值的构造函数。

class Vertex<E>{
    private E label;
    private boolean isVisited;

    public Vertex(E label){
        this.label = label;
    }

    public E getLabel() {
        return label;
    }
    public void setLabel(E label) {
        this.label = label;
    }
    public boolean isVisited() {
        return isVisited;
    }
    public void setVisited(boolean isVisited) {
        this.isVisited = isVisited;
    }

}

表示边

图的实际信息都保存在边上，因为它们描述了图的结构。我们容易像之前提到的那样用二叉树的方式去表示图，这是不对的。二叉树的表现形式相当固定，一个父节点只能有两个子节点，而图结构却要灵活的多，一个顶点既可以有一条边，也可以有多条边与它相连。

我们是用邻接矩阵的方式来表示顶点是否是相邻的，如果是相邻的权值又是多少。

上图就是一个邻接矩阵，可以看到这个是一个实对称矩阵（求出对应的二次型的标准型，并判断是否正定，跑偏了，和线性代数没有关系的）。第一行的那个2就表示第一个节点和第二个节点是相连的，而且权值为2，这个又是一个无向图，所以一定是对称的。

表示图

根据上面的思路就可以轻松的写出图的结构，还有一些简单的函数。

使用集合来存放节点，是用二维数组来存放邻接矩阵。so easy

class Graph2<E> {
    private ArrayList<Vertex<E>> vertexList;
    private int[][] edges;
    private int numOfEdges;

    public Graph2(int n) {
        this.edges = new int[n][n];
        this.vertexList = new ArrayList<Vertex<E>>(n);
        this.numOfEdges = 0;
    }

    public int getNumOfVerter() {
        return vertexList.size();
    }

    public int getNumOfEdges() {
        return numOfEdges;
    }

    public E getValueByIndex(int index) {
        return vertexList.get(index).getLabel();
    }

    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }

    public void showGraph() {
        for (int[] val : edges) {
            System.out.println(Arrays.toString(val));
        }
    }

    public void insertVertex(Vertex<E> vertex) {
        vertexList.add(vertex);
    }

    public void insertEdge(int v1, int v2) {
        insertEdge(v1, v2, 1);
    }

    public void insertEdge(int v1, int v2, int weight) {
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        ++numOfEdges;
    }
}

下面我们去主方法进行一次测试，看看代码是否存在一些问题。

public static void main(String[] args) {
    int n = 5;
    Graph2<String> graph = new Graph2<String>(n);

    String[] vertexValues = {"A","B","C","D","E"};
    for (int i = 0; i < vertexValues.length; i++) {
        graph.insertVertex(new Vertex<String>(vertexValues[i]));
    }

    graph.insertEdge(0, 1);
    graph.insertEdge(0, 2);
    graph.insertEdge(1, 2);
    graph.insertEdge(1, 3);
    graph.insertEdge(1, 4);

    graph.showGraph();
}

输出的结果：

[0, 1, 1, 0, 0]
[1, 0, 1, 1, 1]
[1, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
[0, 1, 0, 0, 0]

到此为止，一个图就已经创建完成了。下面我们开始研究图的遍历的问题。

图的遍历

图的遍历和树的遍历一样，也有两种。一个广度优先遍历，一个是深度优先遍历。之前在将树的遍历的时候就讲了这个是如何实现的了。不过图的遍历和树的遍历又是不一样的了，图中是没有指针来连接各个节点的。所以说只是遍历的思路是一样的，算法还是完全不同的。树的遍历用到了队列和栈，不过图是不需要的。

深度优先遍历

深度优先遍历的思路

深度优先搜索DFS遍历类似于树的前序遍历。其基本思路是：

1. 假设初始状态是图中所有顶点都未曾访问过，则可从图G中任意一顶点v为初始出发点，首先访问出发点v，并将其标记为已访问过。

2. 然后依次从v出发搜索v的每个邻接点w，若w未曾访问过，则以w作为新的出发点出发，继续进行深度优先遍历，直到图中所有和v有路径相通的顶点都被访问到。

3. 若此时图中仍有顶点未被访问，则另选一个未曾访问的顶点作为起点，重复上述步骤，直到图中所有顶点都被访问到为止。

简单的来说，深度优先搜索包括从一条路径的起始点开始追溯，直到到达最后一个顶点，然后回溯，继续追溯下一条路径，直到到达最后的顶点，如此往复，直到没有路径为止

这不是在搜索特定的路径，而是通过搜索来查看在图中有哪些路径可以选择。

如图所示：

深度优先搜索的算法比较简单： 访问一个没有访问过的顶点，将它标记为已访问，再递归地去访问在起始点的邻接表中其他没有访问过的顶点。

代码实现

首先我们要写找到临近节点的函数

public int getFirstNeighbor(int index) {
    for (int j = 0; j < getNumOfVerter(); j++) {
        if (edges[index][j] > 0) {// 表示两个节点是相通的。
            return j;
        }
    }
    return -1;
}

public int getNextNeighbor(int v1, int v2) {
    for (int j = v2+1; j < getNumOfVerter(); j++) {
        if (edges[v1][j] > 0) {
            return j;
        }
    }
    return -1;
}

然后就可以写深度优先遍历的代码了

// 图的深度优先遍历(DFS)
private void depthFirstSearch(int i) {
    System.out.print(getValueByIndex(i) + "->");
    vertexList.get(i).setVisited(true);

    int w = getFirstNeighbor(i);

    while (w != -1) {
        // 如果第一个邻近顶点w没有被访问过，就直接以他作为开始继续深度优先
        if (!vertexList.get(w).isVisited()) {
            depthFirstSearch(w);
        }else {
            // 如果已经被方位过了，就继续寻找下一个w，如果等于-1的话就说明，没有邻近定点了，退出循环即可。
            w = getNextNeighbor(i, w);
        }
    }
}

public void depthFirstSearch() {
    initVisit();
    // 图并不一定是连通的，我们要对每一个顶点都作为开始判断一下，是否有没有被访问过的节点。
    for (int i = 0; i < getNumOfVerter(); i++) {
        if (!vertexList.get(i).isVisited()) {
            depthFirstSearch(i);
        }
    }
}
// 初始化visit，防止之前已经进行过什么遍历了，再次遍历就会出问题。
public void initVisit() {
    for (Vertex<E> val : vertexList) {
        val.setVisited(false);
    }
}

代码说明：

大部分的内容我都在上面的注释中进行过说明了，而且这个图的深度优先的遍历确实是有一点儿简单，所以没什么说的也是很正常的，看懂我注释基本上的明白了图的深度优先遍历的。

输出结果：

[0, 1, 1, 0, 0]
[1, 0, 1, 1, 1]
[1, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
A->B->C->D->E->

广度优先遍历

广度优先遍历的思路

广度优先搜索遍历BFS类似于树的按层次遍历。其基本思路是：

1. 首先访问出发点Vi

2. 接着依次访问Vi的所有未被访问过的邻接点Vi1，Vi2，Vi3，…，Vit并均标记为已访问过。

3. 然后再按照Vi1，Vi2，… ，Vit的次序，访问每一个顶点的所有未曾访问过的顶点并均标记为已访问过，依此类推，直到图中所有和初始出发点Vi有路径相通的顶点都被访问过为止。

如图所示：

简单的来说，广度优先搜索从一个顶点开始，尝试访问尽可能靠近它的顶点。本质上这种搜索在图上是逐层移动的，首先检查最靠近第一个顶点的层，再逐渐向下移动到离起始顶点最远的层

广度优先搜索算法使用了抽象的队列而不是数组来对已经访问过的顶点进行排序。算法工作原理如下：

1. 查找与当前顶点相邻的未访问顶点，将其添加到已访问顶点列表及队列中;
2. 从图中取下一个顶点v，添加到已访问的顶点列表
3. 将所有与v相邻的未访问顶点添加到队列。

可见这个图的广度优先遍历和树的广度优先遍历还是有点儿相似的，都是使用队列这个数据结构来实现的。深度优先遍历不一样，树使用的是栈这个数据结构。

代码实现

// 广度优先遍历(BFS)
private void broadFirstSearch(int i) {
    int u; // 队列的头节点对应的下标
    int w;
    // LinkedList实现了队列的接口，所以说可以拿来当队列来使用
    LinkedList<Integer> queue = new LinkedList<Integer>();
    System.out.print(getValueByIndex(i) + "->");

    vertexList.get(i).setVisited(true);
    queue.addLast(i);// 入队列

    while (!queue.isEmpty()) {
        u = queue.removeFirst();// 出队列
        w = getFirstNeighbor(u);

        while (w != -1) {
            if (!vertexList.get(w).isVisited()) {
                System.out.print(getValueByIndex(w) + "->");
                vertexList.get(w).setVisited(true);
                queue.addLast(w);
            }else {
                w = getNextNeighbor(u, w);
            }
        }
    }
}

public void broadFirstSearch() {
    initVisit();
    for (int i = 0; i < getNumOfVerter(); i++) {
        if (!vertexList.get(i).isVisited()) {
            broadFirstSearch(i);
        }
    }
}

代码说明：

1. u和w是什么含义？

   u表示的是队列中的第一个顶点，也就是说出队列的那个顶点。w和上面的深度优先是一样的，都是表示的是当前顶点的下一个邻接顶点。

2. 两个while循环？

   先看第二个while循环，如果这个邻接顶点w没有被访问过，那么我们就方位，不然我们就找u的下一个邻接顶点。其实这个也是很好理解的。如果这个while循环结束的话，那么也就是以为着u的所有的邻接顶点都被访问过了。那么我们就访问u的邻接顶点的所有的邻接顶点。刚才的u的所有的邻接顶点都已经入队列了。我们只需要按顺序让他们出队列就行了。如果第一个while循环也结束了，那就说明u的所有的可以连通的顶点都通过广度优先遍历访问玩了。但是这并不意味着图就遍历完了。上面也说过了，图可能不是连通的。所以就有了下面的那个函数来做保证

输出结果：

[0, 1, 1, 0, 0]
[1, 0, 1, 1, 1]
[1, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
A->B->C->D->E->

和深度优先遍历输出的结果竟然是一样的，不过这个例子是纯属巧合而已

总结

上面我表示图是用的邻接矩阵的方式，还可以使用邻接表的方式来表示这个图结构，而且效率也是有点儿小高。不过这里我就不瞎掰了，就先介绍一个邻接矩阵就完事了。感觉图的 BFS和DFS比树的真的是差不多，至少理解其实都不是很难。

参考文章：数据结构与算法：图和图算法(一)

扩展文章：数据结构与算法 - 图论