应用连通分量算法。
对于无向图，只需选择一个节点并进行广度优先搜索。如果在第一个 BFS 之后还有剩余的节点，则选择一个剩余的节点并执行另一个 BFS。（每个 BFS 都有一个连接的组件。）
请注意，有向图需要稍强的算法来查找强连通分量。Kosaraju 的算法浮现在脑海中。
从 (1) 计算每个连接组件中的节点数。选择最大的一个。
选择一个起点，开始“步行”到其他节点，直到你筋疲力尽。执行此操作，直到找到所有组件。这将运行在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])
#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");
}