寻找有向图中的弱连通分量

在探索图论的奥秘时，我们经常需要处理有向图。今天，让我们一起深入了解有向图中的一个重要概念：弱连通图。

弱连通图

如果一个有向图 ‘G = (V, E)‘ 的底层无向图（Underlying Undirected Graph）Ĝ 是连通的，那么我们就称这个有向图是弱连通的。

> 底层无向图是指图 Ĝ = (V, Ê)，其中 Ê 代表无向边集合。它是通过将有向图 G 中的有向边去掉箭头（即忽略方向），使其变为双向边而得到的。

示例：

> !image

>

> 上面的有向图 G 是弱连通的，因为它的底层无向图 Ĝ 是连通的。

给定一个有向图，弱连通分量 (WCC) 是原图的一个子图，其中所有顶点都通过某条路径相互连接，且我们在判断连接时忽略了边的方向。

> 示例：

>

> !image

>

> 在上面的有向图中，有两个弱连通分量：

>

> – [0, 1, 2, 3]

> – [4, 5]

寻找弱连通分量的算法

为了找到弱连通分量，我们可以利用寻找无向图中连通分量的算法。步骤非常直观：

• 构建给定有向图的底层无向图。
• 找出该无向图的所有连通分量。
• 无向图的这些连通分量，就是原有所向图的弱连通分量。

代码实现

下面是寻找弱连通分量的代码。它接受一个有向图 DG 作为输入，并返回输入图的所有弱连通分量 WCC。

C++

#include 
#include 
#include 
using namespace std;

class Graph {
  public:
  int vertices;
  vector<vector > adjacencyList;

  Graph(int vertices) {
    this->vertices = vertices;
    adjacencyList.resize(vertices);
  }

  void addEdge(int u, int v) {

    // 使用 noEdge(int, int) 方法
    // 可以防止边的重复添加
    if (noEdge(u, v)) {
      adjacencyList[u].push_back(v);
    }
  }

  // 如果不存在
  // 从 u 到 v 的边，则返回 true
  bool noEdge(int u, int v) {
    for (int destination : adjacencyList[u]) {
      if (destination == v) {
        return false;
      }
    }
    return true;
  }
};

class WCC {
  private:
  Graph directedGraph;

  public:
  WCC(Graph directedGraph) : directedGraph(directedGraph) {
    this->directedGraph = directedGraph;
  }

  // 查找给定无向图的
  // 所有连通分量
  vector<vector > connectedComponents(Graph undirectedGraph) {
    vector<vector > connectedComponents;
    vector isVisited(undirectedGraph.vertices, false);

    for (int i = 0; i < undirectedGraph.vertices; i++) {
      if (!isVisited[i]) {
        vector component;
        findConnectedComponent(i, isVisited, component, undirectedGraph);
        connectedComponents.push_back(component);
      }
    }

    return connectedComponents;
  }

  // 使用深度优先搜索 (DFS)
  // 查找从源点开始的一个连通分量
  void findConnectedComponent(int src, vector& isVisited, vector& component, Graph undirectedGraph) {
    isVisited[src] = true;
    component.push_back(src);

    for (int v : undirectedGraph.adjacencyList[src]) {
      if (!isVisited[v]) {
        findConnectedComponent(v, isVisited, component, undirectedGraph);
      }
    }
  }

  // 步骤 1：构建
  // 底层无向图
  vector<vector > weaklyConnectedComponents() {
    Graph undirectedGraph(directedGraph.vertices);
    for (int u = 0; u < directedGraph.vertices; u++) {
      for (int v : directedGraph.adjacencyList[u]) {
        undirectedGraph.addEdge(u, v);
        undirectedGraph.addEdge(v, u);
      }
    }

    // 步骤 2：找出无向图的
    // 连通分量
    return connectedComponents(undirectedGraph);
  }
};

// 主驱动代码
int main() {
  Graph directedGraph(6);

  directedGraph.addEdge(0, 1);
  directedGraph.addEdge(0, 2);
  directedGraph.addEdge(3, 1);
  directedGraph.addEdge(3, 2);
  directedGraph.addEdge(4, 5);

  WCC wcc(directedGraph);
  vector<vector > weaklyConnectedComponents = wcc.weaklyConnectedComponents();

  int index = 1;
  for (vector component : weaklyConnectedComponents) {
    cout << "Component " << index++ << ": ";
    for (int i : component) {
      cout << i << " ";
    }
    cout << endl;
  }

  return 0;
}

“`java

// 上述算法的 Java 代码实现

import java.util.ArrayList;

class Graph {

int vertices;

ArrayList<ArrayList > adjacencyList;

public Graph(int vertices)

{

this.