एक एडी मैट्रिक्स ग्राफ में सबसे बड़ा कनेक्टेड घटक ढूँढना?

Question

मैं यह पता लगाने की कोशिश कर रहा हूं कि एडी मैट्रिक्स ग्राफ में सबसे बड़ा कनेक्टेड घटक ढूंढने का एक तरीका है। इस जैसे:

0000000110 
0001100000 
0000000000 
0100000010 
0100000100 
0000000100 
0000000000 
1000110000 
1001000000 
0000000000 

मैं इस समस्या Google'd है और कुछ भी खोजने के लिए संघर्ष कर रहा हूँ, मैं भी हालांकि ग्राफ सिद्धांत और कोई खुशी पर विकी लेख पढ़ा है। मुझे लगता है कि इस समस्या को हल करने के लिए उन्हें एक एल्गोरिदम होना चाहिए। क्या कोई मुझे सही दिशा में इंगित कर सकता है और मुझे कुछ संकेत दे सकता है कि मुझे इसे हल करने के लिए क्या करना चाहिए?

Answer 1

एक शुरुआती बिंदु चुनें और जब तक आप थक गए हों तब तक अन्य नोड्स पर "चलना" शुरू करें। ऐसा तब तक करें जब तक आपको सभी घटकों को नहीं मिला। यह O(n) में चलाएगा जहां n ग्राफ का आकार है।

पायथन में एक समाधान का एक कंकाल:

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. एक जुड़ा घटक एल्गोरिथ्म लागू करें।

   एक अप्रत्यक्ष ग्राफ के लिए, बस एक नोड चुनें और एक चौड़ाई पहली खोज करें। यदि पहले बीएफएस के बाद कोई भी नोड छोड़ दिया गया है, तो बाएं ओवर में से एक चुनें और दूसरा बीएफएस करें। (आपको प्रति बीएफएस में एक कनेक्टेड घटक मिलता है।)

   ध्यान दें कि निर्देशित ग्राफ को दृढ़ता से जुड़े घटकों को खोजने के लिए थोड़ा मजबूत एल्गोरिदम की आवश्यकता होती है। कोसारजु के एल्गोरिदम स्प्रिंग्स को ध्यान में रखते हैं।

2. (1) से जुड़े प्रत्येक घटकों में नोड्स की संख्या की गणना करें। सबसे बड़ा उठाओ।

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