Reputation: 3750

Finding the largest connected component in an adj matrix graph?

I'm trying to find out it there is a way of finding the largest connected component in a adj matrix graph. Such as this:

I've Google'd the problem and am struggling to find anything, I've also read though the wiki article on graph theory and no joy. I assume their must be an algorithm out there to solve this problem. Can anybody point me in the right direction and give me some pointers on what I should be doing to solve this myself?

Upvotes: 8

Answers (3)

Priyam ExtinctBird Dhanuka

Reputation: 11

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

Upvotes: 1

bossylobster

Reputation: 10163

Pick a starting point and start "walking" to other nodes until you have exhausted. Do this until you have found all components. This will run in O(n) where n is the size of the graph.

A skeleton of a solution in 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])

Upvotes: 6

Li-aung Yip

Reputation: 12486

Apply a connected components algorithm.

For an undirected graph, just pick a node and do a breadth-first search. If there are any nodes left over after the first BFS, pick one of the left-overs and do another BFS. (You get one connected component per BFS.)

Note that directed graphs require a slightly stronger algorithm to find the strongly connected components. Kosaraju's algorithm springs to mind.
Count the number of nodes in each of the connected components from (1). Pick the largest one.

Upvotes: 7

Finding the largest connected component in an adj matrix graph?

Answers (3)

Related Questions