我有一个随机图再通过Java中的邻接矩阵psented $ P $，我怎么能找到此图中的连接组件（子图）？

I have a random graph represented by an adjacency matrix in Java, how can I find the connected components (sub-graphs) within this graph?

我发现BFS和DFS，但不知道他们是合适的，也不是我能工作，如何实现它们的邻接矩阵。

I have found BFS and DFS but not sure they are suitable, nor could I work out how to implement them for an adjacency matrix.

任何想法？

推荐答案

您需要分配马克 - 长度为n，其中n是顶点图中的一些int数组，并用零填充它。然后：

You need to allocate marks - int array of length n, where n is the number of vertex in graph and fill it with zeros. Then:

1）对于BFS做到以下几点：

1) For BFS do the following:

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做到以下几点。

2) For DFS do the following.

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]将重新连接组件属于我的present指数。

After performing any of this procedures, Components will have number of connected components, and for each vertex i, marks[i] will represent index of connected component i belongs.

两个完整的O（n）时间，使用O（n）的内存，其中n为矩阵大小。但我建议你BFS只要它不会从堆栈溢出问题的影响，而且它不会花时间在递归调用。

Both complete on O(n) time, using O(n) memory, where n is matrix size. But I suggest you BFS as far as it doesn't suffer from stack overflow problem, and it doesn't spend time on recursive calls.

BFS code在Java中：

BFS code in Java:

  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]);

}