在邻接矩阵图中查找最大连通组件？

Question

在邻接矩阵图中查找最大连通组件？

8

我正在尝试找出在邻接矩阵图中寻找最大联通组件的方法。就像这样：

我已经在Google上搜索了这个问题，但是很难找到有用的信息。我也阅读了图论的维基百科文章，但是还是没有收获。我觉得肯定有一个算法可以解决这个问题。请问有人能指点我正确的方向并给我一些提示吗？我应该怎么做才能解决这个问题呢？

- JasonMortonNZ

3个回答

6

选择起始点并开始“走”到其他节点，直到你用尽。重复这个过程，直到找到所有的组件。这将在O(n)运行，其中n是图的大小。

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

- bossylobster

那么类似深度优先搜索的算法可以用来解决这个问题吗？ - JasonMortonNZ

2

是的。我会尝试用Python为您概述一个解决方案，因为这是一个有趣的问题。我心中的解决方案更偏向广度优先。 - bossylobster

2

DFS和BFS在这个特定的目的上是等效的。我会选择BFS，因为它稍微容易实现一些（使用队列而不是栈），但是任何值得自己的计算机科学专业人士都应该能够编写两者。如果你遇到困难，请参考圣经（CLRS 算法导论）。 - Li-aung Yip

感谢 @bossylobster 的 Python 解释。这真的帮了我很多。 - JasonMortonNZ

1

这是O(n^2)的，因为你必须为每个节点迭代大小为n的数组。由于您必须检查邻接矩阵上的每个位置，即使有些可能是1，有些可能是0。 - Joshua Anderson

1

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

- Priyam ExtinctBird Dhanuka

我已经用列表完成了它...只需将类似的逻辑应用于矩阵即可。 - Priyam ExtinctBird Dhanuka

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Li-aung Yip · Accepted Answer

应用连通分量算法。

对于无向图，选择一个节点并执行广度优先搜索。如果第一次BFS后仍有未访问的节点，则选择其中一个进行另一次BFS。（每个BFS得到一个连通分量）

需要注意的是，针对有向图需要使用稍微更强的算法来查找强连通分量。可采用Kosaraju算法。
计算从（1）中得到的每个连通分量的节点数量，选择最大的那一个。