Нахождение связных компонент графа матрицы смежности - PullRequest
Новая
       13

Нахождение связных компонент графа матрицы смежности

14 голосов
/ 14 ноября 2011

У меня есть случайный граф, представленный матрицей смежности в Java, как я могу найти связанные компоненты (подграфы) в этом графе?

Я нашел BFS и DFS, но не уверен, что они подходят, и я не могу понять, как реализовать их для матрицы смежности.

Есть идеи?

Ответы [ 3 ]

22 голосов
/ 14 ноября 2011

Вам нужно выделить метки - массив int длины n, где 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 метки [i] будут представлять индекс связанного компонента, к которому принадлежит i.

Оба завершены за время O (n), используя память O (n), где nразмер матрицыНо я предлагаю вам BFS, поскольку он не страдает от проблемы переполнения стека и не тратит время на рекурсивные вызовы.

Код BFS в 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]);
}
3 голосов
/ 22 июля 2012

Вы можете реализовать DFS итеративно со стеком, чтобы устранить проблемы рекурсивных вызовов и переполнения стека вызовов.Реализация очень похожа на BFS с очередью - нужно просто помечать вершины, когда вы их извлекаете, а не когда вы помещаете их в стек.

2 голосов
/ 20 апреля 2017

Используя редкий модуль Сципи,

Предполагая, что вы вводите словарь от (label_1,label_2) до weight Вы можете запустить этот код: 

vertices, edges = dict2graph(cooccur_matrix, edge_threshold)
n, components = sparse.csgraph.connected_components(edges, directed=False)
print ('Found {n} components'.format(n=n))
components = collect_components(components,vertices)
components = [c for c in components if len(c)>=component_threshold]
print ('removed {k} small components'.format(k=n-len(components)))
print ('component sizes: '+ repr([len(c) for c in components]))

Смотрите полный текст на github здесь

...