java 在 adj 矩阵图中找到最大的连通分量？

Finding the largest connected component in an adj matrix graph?

提问by JasonMortonNZ

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:

我试图找出有一种方法可以在 adj 矩阵图中找到最大的连通分量。比如这个：

0000000110
0001100000
0000000000
0100000010
0100000100
0000000100
0000000000
1000110000
1001000000
0000000000

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?

我已经谷歌了这个问题并且正在努力寻找任何东西，我还阅读了关于图论的维基文章，但没有任何乐趣。我认为他们必须是一种算法来解决这个问题。任何人都可以指出我正确的方向，并就我应该如何自己解决这个问题给我一些指示吗？

采纳答案by bossylobster

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 nis the size of the graph.

选择一个起点并开始“步行”到其他节点，直到您筋疲力尽。这样做直到找到所有组件。这将在运行O(n)，其中n是图的大小。

A skeleton of a solution in Python:

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])

回答by Li-aung Yip

1. 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 connectedcomponents. Kosaraju's algorithm springs to mind.

2. Count the number of nodes in each of the connected components from (1). Pick the largest one.

1. 应用连通分量算法。

   对于无向图，只需选择一个节点并进行广度优先搜索。如果在第一个 BFS 之后还有任何节点，请选择一个剩余的节点并进行另一个 BFS。（每个 BFS 获得一个连接组件。）

   请注意，有向图需要稍微强一些的算法来找到强连通分量。Kosaraju 的算法浮现在脑海中。

2. 从（1）计算每个连接组件中的节点数。选择最大的一个。

回答by Priyam ExtinctBird Dhanuka

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