graph——图的遍历：bfs与dfs

摘要：图的遍历两种方式：深度优先搜索和广度优先搜索。

图的遍历

从图的某一顶点出发访问图中其余顶点，且每一个顶点仅被访问一次

• 广度优先搜索（Breadth First Search，BFS），又称为宽度优先搜索，横向优先搜索
• 深度优先搜索（Depth First Search，DFS）

广度优先搜索

广度优先搜索与二叉树的层序遍历类似，优先访问当前顶点的所有相邻顶点。

实现：使用队列

• 给定一个开始的顶点，加入队列，然后弹出
• 每弹出一个顶点，把该顶点所有没有入队的顶点加入队列，为了记录哪些顶点未入队，可以使用一个Set，当顶点入队时加入Set中
• 直到队列为空

public void bfs(K begin) {
    Vertex<K, E> vertex = vertices.get(begin);
    if (vertex == null) throw new IllegalArgumentException("不存在该节点");

    Queue<Vertex<K, E>> queue = new LinkedList<>();
    Set<K> visited = new HashSet<>(); // 使用一个Set用来记录哪些顶点已经入队
    queue.offer(vertex);
    visited.add(vertex.key);
    while (!queue.isEmpty()) {
        vertex = queue.poll();
        System.out.println(vertex);
        vertex.outEdges.forEach(edge -> {
            if (!visited.contains(edge.to.key)) {
                queue.offer(edge.to);
                visited.add(edge.to.key);
            }
        });
    }
}

深度优先搜索

深度优先遍历，是对先序遍历的推广，从某个顶点v开始处理，然后递归地便利所有与v邻接的顶点。

实现：使用栈

1. 给定一个开始的顶点，压入栈中，然后弹出
2. 没弹出一个顶点，把该顶点下一个没有入栈的邻接顶点压入栈中
3. 直到栈为空

public void dfs(K begin) {
    Vertex<K, E> vertex = vertices.get(begin);
    if (vertex == null) throw new IllegalArgumentException("不存在该节点");

    Stack<Vertex<K, E>> stack = new Stack<>();
    Set<K> visited = new HashSet<>(); // 使用一个Set用来记录哪些顶点已经入栈
    stack.push(vertex);
    System.out.println(vertex);
    visited.add(vertex.key);
    while (!stack.isEmpty()) {
        vertex = stack.pop();
        for (Edge<K, E> edge : vertex.outEdges) {
            if (!visited.contains(edge.to.key)) {
                stack.push(vertex);
                stack.push(edge.to);
                visited.add(edge.to.key);
                System.out.println(edge.to);
                break;
            }
        }
    }
}

遍历的访问器

以上的遍历实现，都是直接打印顶点信息，但是有时候，遍历图可能需要进行其他操作，这就需要定义一个接口，具体执行怎样的操作，可以实现该接口中的方法。

1. 定义一个访问器接口

package com.shg.graph;

/**
 * @author: shg
 * @create: 2022-05-18 11:50 上午
 */

/**
 * 图访问器
 */
@FunctionalInterface
public interface GraphVisitor<K> {
    /**
     * 图的顶点的key
     * @param k
     */
    void visit(K k);
}

2. 重载bfs和dfs方法

public void bfs(K begin, GraphVisitor<K> visitor) {
    Vertex<K, E> vertex = vertices.get(begin);
    if (vertex == null) throw new IllegalArgumentException("不存在该节点");

    Queue<Vertex<K, E>> queue = new LinkedList<>();
    Set<K> visited = new HashSet<>(); // 使用一个Set用来记录哪些顶点已经入队
    queue.offer(vertex);
    visited.add(vertex.key);
    while (!queue.isEmpty()) {
        vertex = queue.poll();
        visitor.visit(vertex.key);
        vertex.outEdges.forEach(edge -> {
            if (!visited.contains(edge.to.key)) {
                queue.offer(edge.to);
                visited.add(edge.to.key);
            }
        });
    }
}

public void dfs(K begin, GraphVisitor<K> visitor) {
    Vertex<K, E> vertex = vertices.get(begin);
    if (vertex == null) throw new IllegalArgumentException("不存在该节点");

    Stack<Vertex<K, E>> stack = new Stack<>();
    Set<K> visited = new HashSet<>(); // 使用一个Set用来记录哪些顶点已经入栈
    stack.push(vertex);
    visitor.visit(vertex.key);
    visited.add(vertex.key);
    while (!stack.isEmpty()) {
        vertex = stack.pop();
        for (Edge<K, E> edge : vertex.outEdges) {
            if (!visited.contains(edge.to.key)) {
                stack.push(vertex);
                stack.push(edge.to);
                visited.add(edge.to.key);
                visitor.visit(edge.to.key);
                break;
            }
        }
    }
}

---

图数据结构与算法汇总