连通分量
无向图G的极大连通子图称为G的连通分量（Connected component）。任何连通图（任意两个顶点之间可达的图）都只有一个连通分量，即自身，非连通图有多个连通分量。
深度优先搜索的特点非常适合用于求解图的连通分量，每一次深度优先遍历所经过的顶点就是一个连通分量。因此只需要对图的每一个顶点调用一次深度优先遍历（注意标记访问过的顶点），就可以求得所有的连通分量。
/*
struct UndirectedGraph
{
size_t V, E; //V表示顶点数，E表示边数
map<int, forward_list<int>> adj;
};
*/
void dfs(UndirectedGraph &graph, vector<int> &visited, vector<pair<int, int>> &cc, int v)
{
visited.at(v) = 1;
cc.push_back(v);
for (const int &i : graph.adj.at(v))
{
if (visited.at(i) == 0)
{
cc.push_back(make_pair(v, i));
dfs(graph, visited, i);
}
}
}
vector<vector<pair<int, int>>> FindConnectedComponent(UndirectedGraph &g)
{
vector<vector<pair<int, int>>> ans;
vector<int> visited(g.V);
for (auto ite = g.adj.cbegin(); ite != g.adj.cend(); ++ite)
{
vector<int> cc;
for (auto &i : ite->second)
{
if (visited.at(i) == 0)
{
dfs(g, visited, cc, i);
ans.push_back(move(cc));
}
}
}
return ans;
}
用广度优先搜索 也可以得到连通分量：
/*
struct UndirectedGraph
{
size_t V, E; //V表示顶点数，E表示边数
map<int, forward_list<int>> adj;
};
*/
vector<vector<pair<int, int>>> FindConnectedComponent(UndirectedGraph &g)
{
vector<vector<pair<int, int>>> ans;
vector<int> visited(g.V);
queue<int> qu;
for (auto ite = g.adj.cbegin(); ite != g.adj.cend(); ++ite)
{
vector<pair<int, int>> cc;
if (visited.at(ite->first) == 1)
{
continue;
}
qu.clear();
qu.push((ite->first);
while (!qu.empty())
{
int tmp = qu.front();
qu.pop();
if (visited.at(tmp) == 1)
{
continue;
}
visited.at(tmp) = 1;
for (const int &i : ite->second)
{
if (visited.at(i) == 0)
{
cc.push_back(make_pair(tmp, i));
qu.push(i);
}
}
}
ans.push_back(move(cc));
}
return ans;
}
相关阅读
引言 深度优先搜索的一个直接应用就是找出一幅图的所有连通分量。在深度优先搜索的递归调用期间，只要是某个顶点的可达顶点都能在
1.连通图1.1 顶点的连通性在无向图G中，若从顶点vi到顶点vj有路径(当然从vj到vi也一定有路径)，则称vi和vj是连通的。1.2 连通图在无
题目描述从键盘接收图的顶点集，关系集，创建无向图。第一行依次输入图的顶点个数n，关系个数k，以空格隔开。顶点个数<=20第二行依次输入
求图的连通分量 什么是连通分量 无向图G的一个极大连通子图称为G的一个连通分量（或连通分支）。连通图只有一个连通分量，即其自身
这里有必要说明几个概念。 （1）在无向图中，如果顶点Vi到顶点Vj有路径，则称顶点Vi和Vj连通。 （2）如果无向图中任意两个顶点之间都连通，则称