DS09.2:图的遍历及应用

图的遍历思想是解决很多算法问题的关键，其中深度优先遍历可以使用栈（递归）进行实现，广度优先搜索可以使用队列进行实现。

图的遍历的实现其实和树基本一致，深度优先对应前序遍历，广度优先对应层序遍历

遍历实现

深度优先遍历（DFS）

import java.util.ArrayList;

public class GraphDFS {

    private Graph G;	// 使用邻接表实现的图结构，参考图的概念与存储结构中的实现
    private boolean[] visited;	// 记录是否访问过
    private ArrayList<Integer> order = new ArrayList<>();	// 存储遍历结果

    public GraphDFS(Graph G) {
        this.G = G;
        visited = new boolean[G.getVertex()];
        // 超过一个连通分量时，进行完全遍历
        for (int v=0; v<G.getVertex(); v++) {
            if(!visited[v]) {
                dfs(v);
            }
        }
    }

    private void dfs(int v) {
        visited[v] = true;
        order.add(v);
        for (int w : G.adj(v)) {
            if (!visited[w]) {
                dfs(w);
            }
        }
    }

    public Iterable<Integer> order() {
        return order;
    }
}

广度优先遍历（BFS）

广度优先遍历在图中有一条很重要的性质，即广度优先搜索能够直接得到无权图的最短路径

public class GraphBFS {

    private Graph G;
    private boolean[] visited;
    private ArrayList<Integer> order = new ArrayList<>();

    public GraphBFS(Graph G) {
        this.G = G;
        visited = new boolean[G.getVertex()];

        for (int v = 0; v<G.getVertex(); v++) {
            if(!visited[v])
                bfs(v);
        }
    }

    private void bfs(int s) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(s);
        visited[s] = true;
        while (!queue.isEmpty()) {
            int v = queue.remove();
            order.add(v);
            for (int w : G.adj(v)) {
                if (!visited[w]) {
                    queue.add(w);
                    visited[w] = true;
                }
            }
        }
    }

    public Iterable<Integer> order() {
        return order;
    }
}

利用遍历可以实现的简单操作

利用遍历可以解决图结构中包括连通性等诸多问题，这些问题使用bfs和dfs都能够得到解决，以dfs为例。

求图的连通分量

在遍历代码的基础上使用一个整型记录主函数调用dfs的次数即可（该类问题与常见的海岛个数问题<floodfill算法>思路完全一致）。思路如下

int count = 0
for (int v=0; v<G.getVertex(); v++) {
    if(!visited[v]) {
        dfs(v);
        count++;
    }
}

记录图中每个节点所属的连通分量

将记录是否访问过节点的boolean型数组visited改为整型数组，在不同连通分量递归时使用不同的值进行记录即可。大致思路如下半伪码。

int[] visited;
// 遍历将visited的值全部设置为-1，表示没有进行访问
int record = 0;
for (int v=0; v<G.getVertex(); v++) {
    if(!visited[v]) {
        dfs(v, record);	// 将record值用于标记已访问该节点
        record++;
    }
}
// 此时visited中就已经记录了每个节点所属连通分量的信息

求两点间是否可达

若两点在同一个连通分量，则代表可达，在上一个问题的基础上进行一下判断就行了。

求两点间的任意一条路径

使用一个数组存储当前节点前面一个节点，之后根据数组信息即可得到两点间的一条路径，伪码如下：

int[] pre;
int target;
dfs(v, v);	// 求从v到target的任一路径

// v的上一个节点是parent
void dfs(v, parent) {
	if(v == target) return;
	visited[v] = true;
	pre[v] = parent;
	for(w : G.adj(v))
		if(!visited[w])
		dfs(w, v)
}

检查是否有环

利用深度优先遍历，若访问到了一个已访问过的点，则有环，若遍历结束都没访问到，则无环。

二分图检测

二分图就是顶点V可以分成不相交的两部分，且所有边的两个端点隶属于不同的部分的一种特殊图结构

二分图的检测也可以使用深度优先遍历进行检测，每遍历到一个点则对其进行染色操作，若相应点已染色，则检查其与其相邻顶点颜色是否匹配，若不匹配则直接返回false

Donate