algorithm - 查找邻接矩阵图的连通分量

Question

我有一个由 Java 中的邻接矩阵表示的随机图，如何找到该图中的连通分量(子图)？

我找到了 BFS 和 DFS，但不确定它们是否合适，也不知道如何为邻接矩阵实现它们。

有什么想法吗？

Answer 1

您需要分配 marks - 长度为 n 的 int 数组，其中 n 是图中顶点的数量，并用零填充。然后:

1) 对于 BFS，请执行以下操作:

Components = 0;

Enumerate all vertices, if for vertex number i, marks[i] == 0 then

    ++Components;

    Put this vertex into queue, and 

    while queue is not empty, 

        pop vertex v from q

        marks[v] = Components;

        Put all adjacent vertices with marks equal to zero into queue.

2) 对于 DFS，请执行以下操作。

Components = 0;

Enumerate all vertices, if for vertex number i, marks[i] == 0 then

    ++Components;

    Call DFS(i, Components), where DFS is

    DFS(vertex, Components)
    {
        marks[vertex] = Components;
        Enumerate all vertices adjacent to vertex and 
        for all vertex j for which marks[j] == 0
            call DFS(j, Components);
    }

执行任何此过程后，组件将具有多个连接组件，对于每个顶点 i，marks[i] 将表示 i 所属的连通分量的索引。

两者都在 O(n) 时间内完成，使用 O(n) 内存，其中 n 是矩阵大小。但我建议你 BFS，只要它不会遇到堆栈溢出问题，并且不会在递归调用上花费时间。

Java 中的 BFS 代码:

  public static boolean[] BFS(boolean[][] adjacencyMatrix, int vertexCount, int givenVertex){
      // Result array.
      boolean[] mark = new boolean[vertexCount];

      Queue<Integer> queue = new LinkedList<Integer>();
      queue.add(givenVertex);
      mark[givenVertex] = true;

      while (!queue.isEmpty())
      {
        Integer current = queue.remove();

        for (int i = 0; i < vertexCount; ++i)
            if (adjacencyMatrix[current][i] && !mark[i])
            {
                mark[i] = true;
                queue.add(i);
            }
      }

      return mark;
  }


  public static void main(String[] args) {
      // Given adjacencyMatrix[x][y] if and only if there is a path between x and y.
      boolean[][] adjacencyMatrix = new boolean[][]
              {
                      {false,true,false,false,false},
                      {true,false,false,true,true},
                      {false,false,false,false,false},
                      {true,false,false,false,false},
                      {true,false,false,false,false}
              };
      // Mark[i] is true if and only if i belongs to the same connected component as givenVertex vertex does.
      boolean[] mark = BFS(adjacencyMatrix, 5, 0);

      for (int i = 0; i < 5; ++i)
          System.out.println(mark[i]);
}