数据结构系列之图（Java）

leetcode图专题

广度优先搜索（Breadth-First-Search、BFS）

BFS与树的层次遍历有点类似，可以用于树或者图的遍历，其具体过程如下：

访问起始顶点vertex;
由顶点依次访问vertex的各个未被访问过的邻接顶点W1、W2、W3、…Wn;
然后依次访问W1、W2、W3、… Wn;的所有未被访问过的邻接顶点;
如果所在顶点没有未被访问过的领接顶点，则退回到上一层顶点；
继续从第二步开始重复，以此类推。

如果仅仅是树的层次遍历来实现BFS的话，无法满足只访问未被访问过的这一约束，比如如下的图：

因此其实现原理需要额外的一个队列和一个辅助性的数组。

BOILERPLATE:

private class Graph {
    int val;
    int index;
    Graph[] neighbors;
    int currentVisitNeighborIndex;// getFristNeighbor时为0, getNextNeighbor每次+1
}

private boolean[] visitedRecord = new boolean[MAX];
private Queue<Graph> queue;
private void BFS(Graph g){
    peek(g); // 具体的访问代码逻辑
    visitedRecord[g.index] = true; // 代表已经访问过
    queue.push(g);
    while(!queue.isEmpty()){
        Graph temp = intqueue.pop();
        for(Graph next = getFristNeighbor(temp); next != null ; next = getNextNeighbor(temp)){
            if(!visitedRecord[next.index]){
                peek(next);
                visitedRecord[next.index] = true; // 代表已经访问过
                queue.push(next);
            }
        }
    }
}

private void mutilGraphVetex(Graph... gs){
    // 如果存在多个顶点的图
    gs.forEach(this::BFS);
}

深度优先搜索（Depth-First-Search、DFS）

DFS与树的先序遍历比较类似，可以用于树或者图的遍历，其具体过程如下：

访问起始顶点vertex;
由顶点依次访问vertex的任意一个未被访问过的邻接顶点W;
然后再访问W的任意一个未被访问过的邻接顶点Y;
如果W没有未被访问过的领接顶点，则退回到上一层顶点；
继续从第二步开始重复，以此类推。

其实现原理可以采用递归思维，加额外的一个辅助性的数组。

BOILERPLATE:

private class Graph {
    int val;
    int index;
    Graph[] neighbors;
    int currentVisitNeighborIndex;
}

private boolean[] visitedRecord = new boolean[MAX];

private void DFS(Graph g){
    peek(g); // 具体的访问代码逻辑
    visitedRecord[g.index] = true; // 代表已经访问过
    for(Graph next = getFristNeighbor(g); next != null ; next = getNextNeighbor(g)){
        if(!visitedRecord[next.index]){
            (next);
        }
    }
}

private void mutilGraphVetex(Graph... gs){
    // 如果存在多个顶点的图
    gs.forEach(this::DFS);
}

这是一种多顶点的图

其DFS序列为：ACDEB。

拓扑排序（Topological sorting）

参考来源：王道考研

对DAG所有顶点的一种排序，使若存在一条从顶点A到顶点B的路径，在排序中B排在A的后面。
有环无向图不存在拓扑排序。

有向无环图（DAG，Directed Acyclic Graph）

在图论中，如果一个有向图从任意顶点出发无法经过若干条边回到该点，则这个图是一个有向无环图。

算法思维

从DAG图中选择一个没有前驱的顶点并输出；
从图中删除该顶点和所有以它为起点的有向边；
重复1、2步直到当前的DAG图为空或当前图中不存在无前驱的顶点为止，后一种情况说明图中有环。

DAG其拓扑排序的过程如下：

非DAG图：

算法结束时没有访问所有顶点，则存在以剩下顶点组成的环。

出现多个没有入边的顶点（入度不为0）的情况：

拓扑排序的结果不一定唯一。

BOILERPLATE:

private class Graph {
    int val;
    int index;
    Graph[] neighbors;
    int currentVisitNeighborIndex = 0;

    public Graph firstNeighbor() {
        if (neighbors == null || neighbors.length == 0) {
            return null;
        }
        return neighbors[currentVisitNeighborIndex++];
    }

    public Graph nextNeighbor() {
        if (neighbors != null && currentVisitNeighborIndex < neighbors.length) {
            return neighbors[currentVisitNeighborIndex++];
        }
        return null;
    }
}

private Graph getGraph(int index) {
    // dosomething
    return null;
}

boolean topologicalSort(int[] indegrees) {
    // 当前顶点
    Graph g = null;
    Stack<Integer> stack = new Stack<>();
    // 找出入度为0的顶点
    for (int i : indegrees) {
        if (i == 0) {
            stack.push(i);
            // 顶点入队之后，其入度已经不存在，也就是删除顶点与其出边
            --indegrees[i];
            g = getGraph(i);
        }
    }
    // 记录当前访问顶点的个数
    int count = 0;
    // 用一个数组来记录排序的序列
    int[] print = new int[indegrees.length];
    while (!stack.isEmpty()) {
        // 记录当前的额顶点下标（排序）
        print[count++] = stack.pop();
        for (Graph tmp = g.firstNeighbor(); tmp != null; tmp = g.nextNeighbor()) {
            // 删除入度，如果此时入度为0，代表又是一个顶点
            if (--indegrees[tmp.index] == 0) {
                // 顶点入队
                stack.push(tmp.index);
                // 删除顶点与其出边
                --indegrees[tmp.index];
                g = getGraph(tmp.index);
            }
        }
    }
    if (count < indegrees.length) {
        // 如果有顶点没有被访问到，不是DAG，剩下的是环状结构
        return false;
    } else {
        // 拓扑排序成功，输出print
        return true;
    }
}