¿Encontrando el componente conectado más grande en un gráfico de matriz adj?

Question

Estoy tratando de descubrir que hay una manera de encontrar el componente conectado más grande en un gráfico de matriz adj. Como este:

0000000110 
0001100000 
0000000000 
0100000010 
0100000100 
0000000100 
0000000000 
1000110000 
1001000000 
0000000000 

He Google'd el problema y estoy luchando para encontrar nada, también he leído aunque el artículo de wiki en la teoría de grafos y sin alegría. Supongo que deben ser un algoritmo para resolver este problema. ¿Alguien puede señalarme en la dirección correcta y darme algunos consejos sobre lo que debería hacer para resolver esto yo mismo?

Answer 1

Elija un punto de partida y comience a "caminar" hacia otros nodos hasta que se haya agotado. Haga esto hasta que haya encontrado todos los componentes. Esto se ejecutará en O(n) donde n es el tamaño del gráfico.

Un esqueleto de una solución en Python:

class Node(object): 
    def __init__(self, index, neighbors): 
     self.index = index 
     # A set of indices (integers, not Nodes) 
     self.neighbors = set(neighbors) 

    def add_neighbor(self, neighbor): 
     self.neighbors.add(neighbor) 


class Component(object): 
    def __init__(self, nodes): 
     self.nodes = nodes 
     self.adjacent_nodes = set() 
     for node in nodes: 
      self.adjacent_nodes.add(node.index) 
      self.adjacent_nodes.update(node.neighbors) 

    @property 
    def size(self): 
     return len(self.nodes) 

    @property 
    def node_indices(self): 
     return set(node.index for node in self.nodes) 

    @property 
    def is_saturated(self): 
     return self.node_indices == self.adjacent_nodes 

    def add_node(self, node): 
     self.nodes.append(node) 
     self.adjacent_nodes.update(node.neighbors) 


adj_matrix = [[0, 0, 0, 0, 0, 0, 0, 1, 1, 0], 
       [0, 0, 0, 1, 1, 0, 0, 0, 0, 0], 
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
       [0, 1, 0, 0, 0, 0, 0, 0, 1, 0], 
       [0, 1, 0, 0, 0, 0, 0, 1, 0, 0], 
       [0, 0, 0, 0, 0, 0, 0, 1, 0, 0], 
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
       [1, 0, 0, 0, 1, 1, 0, 0, 0, 0], 
       [1, 0, 0, 1, 0, 0, 0, 0, 0, 0], 
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] 
matrix_size = len(adj_matrix) 

nodes = {} 
for index in range(matrix_size): 
    neighbors = [neighbor for neighbor, value in enumerate(adj_matrix[index]) 
       if value == 1] 
    nodes[index] = Node(index, neighbors) 

components = [] 
index, node = nodes.popitem() 
component = Component([node]) 
while nodes: 
    if not component.is_saturated: 
     missing_node_index = component.adjacent_nodes.difference(component.node_indices).pop() 
     missing_node = nodes.pop(missing_node_index) 
     component.add_node(missing_node) 
    else: 
     components.append(component) 

     index, node = nodes.popitem() 
     component = Component([node]) 

# Final component needs to be appended as well 
components.append(component) 

print max([component.size for component in components]) 

Answer 2

1. Aplicar un algoritmo de componentes conectados.

   Para un gráfico no dirigido, simplemente elija un nodo y realice una búsqueda amplia. Si quedan nodos después del primer BFS, elija uno de los sobrantes y haga otro BFS. (Obtiene un componente conectado por BFS).

   Tenga en cuenta que los gráficos dirigidos requieren un algoritmo ligeramente más fuerte para encontrar los componentes fuertemente conectados. El algoritmo de Kosaraju viene a la mente.

2. Cuente la cantidad de nodos en cada uno de los componentes conectados desde (1). Elija el más grande.

Answer 3

#include<iostream> 
#include<cstdlib> 
#include<list> 
using namespace std; 
class GraphDfs 
{ 
    private: 
     int v; 
     list<int> *adj; 
     int *label; 
     int DFS(int v,int size_connected) 
     { 

      size_connected++; 
      cout<<(v+1)<<" "; 
      label[v]=1; 
      list<int>::iterator i; 
      for(i=adj[v].begin();i!=adj[v].end();++i) 
      { 
       if(label[*i]==0) 
       { 
        size_connected=DFS(*i,size_connected); 

       } 

      } 
      return size_connected; 
     } 
    public: 
     GraphDfs(int k) 
     { 
      v=k; 
      adj=new list<int>[v]; 
      label=new int[v]; 
      for(int i=0;i<v;i++) 
      { 
       label[i]=0; 
      } 
     } 
     void DFS() 
     { 
      int flag=0; 
      int size_connected=0; 
      int max=0; 
      for(int i=0;i<v;i++) 
      { 
       size_connected=0; 
       if(label[i]==0) 
       { 
        size_connected=DFS(i,size_connected); 
        max=size_connected>max?size_connected:max; 
        cout<<size_connected<<endl; 
        flag++; 
       } 
      } 
      cout<<endl<<"The number of connected compnenets are "<<flag<<endl; 
      cout<<endl<<"The size of largest connected component is "<<max<<endl; 
      //cout<<cycle; 
     } 

     void insert() 
     { 
      int u=0;int a=0;int flag=1; 
      while(flag==1) 
      { cout<<"Enter the edges in (u,v) form"<<endl; 

       cin>>u>>a; 
       adj[a-1].push_back(u-1); 
       adj[u-1].push_back(a-1); 
       cout<<"Do you want to enter more??1/0 "<<endl; 
       cin>>flag; 

      } 
     }  
}; 
int main() 
{ 
    cout<<"Enter the number of vertices"<<endl; 
    int v=0; 
    cin>>v; 
    GraphDfs g(v); 
    g.insert(); 
    g.DFS(); 
    system("Pause");  
}