【数据结构与算法】系列三十 - 图（广度/深度优先搜索）

邻接矩阵实现起来特别繁琐，而且没有通用性（适合稠密图），所以本章节以类似邻接表的方式（不是完全的邻接表，但比邻接表灵活）实现图（有向图可以表示无向图）。

一、图的实现

需要对HashMap和HashSet等数据结构有所了解，否则很难理解为什么使用这些数据结构实现对应的功能。

1.1. 思路

1. 顶点包含：存储的数据、出边集（HashSet）、入边集（HashSet）
   • 可以通过顶点知道该点包含哪些边，以及边的方向
2. 边包含：出发的顶点、到达的顶点、权值
   • 通过边可以知道连接的是哪两个顶点，以及边的权值
3. 图包含：顶点集、边集
   • 使用HashMap实现顶点集（存储方式：顶点存储的数据 : 顶点），目的是为了快速通过顶点存储的数据找到对应顶点
   • 使用HashSet实现边集，目的是能够快速找到对应的边（时间复杂度是O(1)，如果使用数组，时间复杂度是O(n)）
4. 添加顶点：只需要往图的顶点集添加即可
   • 如果顶级集中已经存在相同value的顶点，不需要重复添加
5. 添加边
   • 如果顶点不存在，就会创建对应顶点
   • 先删除之前存在的边，再添加新的边
6. 移除边
   • 只要有一个顶点不能存在就不需要做任何操作
   • 构建一条两个顶点之间的边，如果构建的边存在（利用HashSet的equals和hashCode方法进行判断），直接删除
7. 移除顶点
   • 删除顶点最主要的逻辑是删除和顶点相关的边（出边和入边）
   • 切记：大部分编程语言不能一边遍历一边删除（容易出bug），java中提供的迭代器可以安全删除迭代的元素

提示：java中HashSet的remove方法内部实现了contains逻辑。

1.2. 实现

虽然直接阅读代码有点枯燥，但还是很有必要的，下面的代码都已经加上了逻辑注释，顺着思路阅读会轻松很多。

// 公共方法
public abstract class Graph<V, E> {
  public Graph() {}

  // 边的数量
  public abstract int edgesSize();
  // 顶点数量
  public abstract int verticesSize();

  // 添加顶点
  public abstract void addVertex(V v);
  // 添加边
  public abstract void addEdge(V from, V to);
  // 添加边（有权值）
  public abstract void addEdge(V from, V to, E weight);

  // 移除顶点
  public abstract void removeVertex(V v);

  // 移除边
  public abstract void removeEdge(V from, V to);
}

// 具体实现
public class ListGraph<V, E> extends Graph<V, E> {
  public ListGraph() {
  }

  // 顶点
  private static class Vertex<V, E> {
    // 顶点存储的数据
    V value;
    // 指向当前顶点的边
    Set<Edge<V, E>> inEdges = new HashSet<>();
    // 指向其他顶点的边
    Set<Edge<V, E>> outEdges = new HashSet<>();

    Vertex(V value) {
      this.value = value;
    }

    // 两个顶点的value相同，就认为两个顶点相等
    @Override
    public boolean equals(Object obj) {
      return Objects.equals(value, ((Vertex<V, E>) obj).value);
    }

    @Override
    public int hashCode() {
      return value == null ? 0 : value.hashCode();
    }

    @Override
    public String toString() {
      return value == null ? "null" : value.toString();
    }
  }

  // 边
  private static class Edge<V, E> {
    // 从哪个顶点出发
    Vertex<V, E> from;
    // 到达哪个顶点
    Vertex<V, E> to;
    // 权值
    E weight;

    Edge(Vertex<V, E> from, Vertex<V, E> to) {
      this.from = from;
      this.to = to;
    }

    EdgeInfo<V, E> info() {
      return new EdgeInfo<>(from.value, to.value, weight);
    }

    // 两条边的起点和终点相同，就认为两条边相等
    @Override
    public boolean equals(Object obj) {
      Edge<V, E> edge = (Edge<V, E>) obj;
      return Objects.equals(from, edge.from) && Objects.equals(to, edge.to);
    }

    @Override
    public int hashCode() {
      return from.hashCode() * 31 + to.hashCode();
    }

    @Override
    public String toString() {
      return "Edge [from=" + from + ", to=" + to + ", weight=" + weight + "]";
    }
  }

  // 顶点集（使用Map是为了快速通过V找到对应顶点）
  private Map<V, Vertex<V, E>> vertices = new HashMap<>();
  // 边集（没有顺序，所以使用Set）
  private Set<Edge<V, E>> edges = new HashSet<>();

  // 打印图相关信息
  public void print() {
    System.out.println("[顶点]-------------------");
    vertices.forEach((V v, Vertex<V, E> vertex) -> {
      System.out.println(v);
      System.out.println("out-----------");
      System.out.println(vertex.outEdges);
      System.out.println("in-----------");
      System.out.println(vertex.inEdges);
    });

    System.out.println("[边]-------------------");
    edges.forEach((Edge<V, E> edge) -> {
      System.out.println(edge);
    });
  }

  // 边数量
  @Override
  public int edgesSize() {
    return edges.size();
  }

  // 顶点数量
  @Override
  public int verticesSize() {
    return vertices.size();
  }

  // 添加顶点
  @Override
  public void addVertex(V v) {
    if (vertices.containsKey(v))
      return;
    vertices.put(v, new Vertex<>(v));
  }

  // 添加边
  @Override
  public void addEdge(V from, V to) {
    addEdge(from, to, null);
  }

  // 添加边（含权值）
  @Override
  public void addEdge(V from, V to, E weight) {
    // 如果顶点不存在，就会创建对应顶点
    Vertex<V, E> fromVertex = vertices.get(from);
    if (fromVertex == null) {
      fromVertex = new Vertex<>(from);
      vertices.put(from, fromVertex);
    }

    Vertex<V, E> toVertex = vertices.get(to);
    if (toVertex == null) {
      toVertex = new Vertex<>(to);
      vertices.put(to, toVertex);
    }

    Edge<V, E> edge = new Edge<>(fromVertex, toVertex);
    edge.weight = weight;
    // 不要认为edge是新创建的就无法删除，Edge对象存放在HashSet中（判断两个对象是否相等，需要看自定义的equals和hashCode方法）如果两个对象相等就可以删除（这里删除的不是上面新建的edge对象，而是存放在HashSet中和edge相等的（equals）那个对象）。
    // remove内部会判断是否包含edge（可阅读源码）
    if (fromVertex.outEdges.remove(edge)) {
      toVertex.inEdges.remove(edge);
      edges.remove(edge);
    }
    fromVertex.outEdges.add(edge);
    toVertex.inEdges.add(edge);
    edges.add(edge);
  }

  // 移除边
  @Override
  public void removeEdge(V from, V to) {
    // from或to不存在直接返回
    Vertex<V, E> fromVertex = vertices.get(from);
    if (fromVertex == null)
      return;

    Vertex<V, E> toVertex = vertices.get(to);
    if (toVertex == null)
      return;

    // 构建一条从from到to的边，如果从from顶点出发的边有一条和构建的边相等，就能够从其中删除（remove前HashSet内部会判断是否包含和edge相等的边），继而删除顶点to和边集合中的edge（注意：这里删除的不是新构建的edge对象，而是和edge对象相等的另外一个对象）
    Edge<V, E> edge = new Edge<>(fromVertex, toVertex);
    if (fromVertex.outEdges.remove(edge)) {
      toVertex.inEdges.remove(edge);
      edges.remove(edge);
    }
  }

  // 移除顶点
  // 顶点被移除后，还要移除和顶点相关的所有边
  @Override
  public void removeVertex(V v) {
    // remove成功后，会返回v对应的value（value就是顶点）
    Vertex<V, E> vertex = vertices.remove(v);
    if (vertex == null)
      return;

    // 删除从顶点出发的边
    for (Iterator<Edge<V, E>> iterator = vertex.outEdges.iterator(); iterator.hasNext();) {
      Edge<V, E> edge = iterator.next();
      // 删除to顶点和edge相等的入边
      edge.to.inEdges.remove(edge);
      // 将当前遍历到的元素edge从集合vertex.outEdges中删掉（java语法）
      iterator.remove();
      // 删除边集中的edge
      edges.remove(edge);
    }

    // 删除到达顶点的边
    for (Iterator<Edge<V, E>> iterator = vertex.inEdges.iterator(); iterator.hasNext();) {
      Edge<V, E> edge = iterator.next();
      // 删除from顶点和edge相等的出边
      edge.from.outEdges.remove(edge);
      // 将当前遍历到的元素edge从集合vertex.inEdges中删掉
      iterator.remove();
      edges.remove(edge);
    }
  }
}

二、遍历

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

提示：遍历图时，需要指定遍历入口（从哪个顶点开始遍历）。

图有2种常见的遍历方式（有向图、无向图都适用）：

• 广度优先搜索（Breadth First Search，BFS）：又称为宽度优先搜索、横向优先搜索。

• 深度优先搜索（Depth First Search，DFS）

  • 发明该算法的2位科学家在1986年共同获得计算机领域的最高奖:图灵奖

2.1. 广度优先搜索

之前所学的二叉树层序遍历就是一种广度优先搜索。

二叉树层序遍历是从根节点开始每一层依次往下进行遍历。优先访问根节点那一层（第1层），然后依次访问距离根节点最近的一层（第2层、第3层、…）。图的遍历也是这样，优先访问入口顶点，然后依次访问距离入口顶点最近的一层（顶点到入口顶点只需要一条线（有向图需要考虑方向）就能访问到的属于同一层，同一层顶点没有访问顺序，已访问顶点不再访问）。

无向图，入口顶点是A：

有向图，入口顶点是0：

无向图，入口顶点是0：

有向图，入口顶点是5：

上图中，如果0是入口，只会遍历0；如果2是入口，只会遍历2、0。所以使用广度优先搜索遍历有向图，入口不同遍历的结果也不同。

2.1.1. 思路

二叉树层序遍历使用的是队列，图也可以使用队列实现广度优先搜索。

1. 先把入口顶点入队；
2. 取出队列中的顶点并访问，然后遍历顶点的outEdges，找出顶点每一条边的终点（Edge中包含起始点和终点信息）并入队；
3. 重复2，直到队列为空。

注意：入队时要记录已入队的顶点，防止已访问的顶点会被再次访问。

2.1.2. 实现

public void bfs(V begin) {
  // 入口顶点
  Vertex<V, E> beginVertex = vertices.get(begin);
  if (beginVertex == null)
    return;

  Set<Vertex<V, E>> visitedVertices = new HashSet<>();
  Queue<Vertex<V, E>> queue = new LinkedList<>();
  // 入口顶点入队
  queue.offer(beginVertex);
  // 记录已入队的顶点
  visitedVertices.add(beginVertex);

  while (!queue.isEmpty()) {
    // 入队并访问
    Vertex<V, E> vertex = queue.poll();
    System.out.println(vertex.value);

    // 遍历出队顶点连接的终点
    for (Edge<V, E> edge : vertex.outEdges) {
      // 如果顶点被访问过，不用再次访问
      if (visitedVertices.contains(edge.to)) continue;
      // 如果顶点未访问过，入队并记录
      queue.offer(edge.to);
      visitedVertices.add(edge.to);
    }
  }
}

注意：记录已访问顶点的时机很重要，不要只在出队时记录，因为同层顶点是连通时会有重复记录的情况发生。

2.2. 深度优先搜索

深度优先搜索，理解起来很简单，就是一条路径走到黑，当没有路的时候开始折返，折返过程中遇到路口就看是否有其他未走过的路，如此反复，直到把所有路都走一遍。

之前所学的二叉树前序遍历就是一种深度优先搜索。

深度优先搜索能够保证让每一个连通的节点都能被访问到。

如下，无向图，如果入口顶点是1，深度优先搜索的顺序（会有多种结果）：

如下，有向图，如果入口顶点是a，深度优先搜索的顺序（会有多种结果）：

如下，无向图，如果入口顶点是e，深度优先搜索的顺序（会有多种结果）：

2.2.1. 利用递归实现

使用递归实现深度优先搜索是非常简单的。为了避免有环情况下死循环，可以把访问过的节点记录下来。

public void dfs(V begin) {
  // 找到入口顶点
  Vertex<V, E> beginVertex = vertices.get(begin);
  if (beginVertex == null) return;
  // 用来记录已访问顶点
  Set<Vertex<V, E>> visitedVertices = new HashSet<>();
  // 开始遍历
  dfs(beginVertex, visitedVertices);
}

private void dfs(Vertex<V, E> vertex, Set<Vertex<V, E>> visitedVertices) {
  // 访问顶点
  System.out.println(vertex.value);
  // 记录已访问顶点
  visitedVertices.add(vertex);

  // 访问从顶点出发的边的另外一个顶点
  for (Edge<V, E> edge : vertex.outEdges) {
    // 如果顶点被访问过，跳过
    if (visitedVertices.contains(edge.to)) continue;
    // 如果顶点未访问过，递归访问
    dfs(edge.to, visitedVertices);
  }
}

2.2.2. 利用栈实现

2.2.2.1. 思路

和二叉树前序遍历一样，可以使用栈实现深度优先搜索。

如下图，顶点入栈和出栈的流程：

1. 先把入口顶点入栈并访问（记录已入栈的顶点到已访问集合中）；
2. 弹出栈顶顶点并在顶点的outEdges中任意选择一条边edge（如果edge.to已经被访问，这条边不需要做任何处理，直接返回）；
3. 把选中edge的开始顶点和结束顶点依次入栈（记录已入栈的结束顶点并访问它。开始顶点已经在栈顶弹出，但是必须再次入栈，因为这个顶点可能还有其他边）；
4. 重复2、3，直到栈顶为空。

2.2.2.1. 实现

public void dfs(V begin) {
  // 找到入口顶点
  Vertex<V, E> beginVertex = vertices.get(begin);
  if (beginVertex == null) return;

  // 用来记录已访问顶点
  Set<Vertex<V, E>> visitedVertices = new HashSet<>();
  // 放入待访问的顶点
  Stack<Vertex<V, E>> stack = new Stack<>();

  // 入口顶点入栈并记录
  stack.push(beginVertex);
  visitedVertices.add(beginVertex);
  System.out.println(begin);
  
  while (!stack.isEmpty()) {
    // 栈顶顶点出栈
    Vertex<V, E> vertex = stack.pop();

    // 把栈顶顶点出边的另一端顶点入栈
    for (Edge<V, E> edge : vertex.outEdges) {
      if (visitedVertices.contains(edge.to)) continue;

      // 一个顶点可能会有多条边，所以from也要入栈（不需要考虑是否会重复，因为上面一行代码已经起到了过滤作用）
      stack.push(edge.from);
      stack.push(edge.to);
      visitedVertices.add(edge.to);
      System.out.println(edge.to.value);
      
      break;
    }
  }
}