Odnajdywanie największego podłączonego komponentu na wykresie macierzy ADJ?

Question

Próbuję się przekonać, że istnieje sposób na znalezienie największego połączonego komponentu na wykresie macierzy adj. Takie jak ten:

0000000110 
0001100000 
0000000000 
0100000010 
0100000100 
0000000100 
0000000000 
1000110000 
1001000000 
0000000000 

Mam Google'd problem i jestem stara się znaleźć coś, ja również czytać chociaż artykule wiki na teorii grafów i bez radości. Zakładam, że muszą być algorytmem, który rozwiązuje ten problem. Czy ktoś może wskazać mi właściwy kierunek i dać mi wskazówki, co powinienem zrobić, aby samemu rozwiązać ten problem?

Answer 1

Wybierz punkt początkowy i rozpocznij "chodzenie" do innych węzłów, aż się wyczerpiesz. Rób to, dopóki nie znajdziesz wszystkich składników. To będzie działać w O(n), gdzie n jest wielkością wykresu.

szkieletu roztworze Pythonie

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. Zastosować algorytm podłączone części.

   Dla nieukierunkowanego wykresu wystarczy wybrać węzeł i wykonać pierwsze wyszukiwanie. Jeśli po pierwszym BFS pozostały jakieś węzły, wybierz jedno z pozostałych i wykonaj kolejny BFS. (Dostajesz jeden podłączony komponent na BFS.)

   Należy zauważyć, że ukierunkowane wykresy wymagają nieco silniejszego algorytmu do znalezienia silnie połączonych komponentów. Algorytm Kosaraju ma znaczenie.

2. Policz liczbę węzłów w każdym z podłączonych komponentów od (1). Wybierz największy.

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");  
}