1.Tarjan
算法思想是基于DFS，对于每个顶点v，维护两个数组值dfn[v]和low[v]，分别表示以DFS访问该顶点的时间戳、该点通过它的子孙节点能回溯到的最早时间戳。
先看一个无向图的例子。
参考代码
class Solution {
public:
// 标记顶点是否访问过
vector<int>vis;
// 每个顶点被访问的时间戳
vector<int>dfn;
// 每个顶点能通过子孙节点追溯到的最早时间点
vector<int>low;
// 记录图结构
vector<vector<int>>graph;
// 时间戳
int time = 1;
// 返回值
vector<vector<int>>ans;
vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
vis.resize(n,0);
dfn.resize(n,0);
low.resize(n,0);
graph.resize(n);
for(auto v:connections){
graph[v[0]].push_back(v[1]);
graph[v[1]].push_back(v[0]);
}
// 时间戳变量
int time = 1;
// DFS 因为是无向图 传入父节点保证不往回走
tarjan(0,-1);
return ans;
}
void tarjan(int v,int parent){
vis[v] = 1;
dfn[v] = low[v] = time++;
for(auto t:graph[v]){
// 扫描到父节点 跳过
if(t==parent) continue;
// 该点没访问过
if(!vis[t]){
// 类比树的先序和后序访问
// DFS也可以有类似的“先序”和“后序”
// “先序”指先访问输出当前节点再对子节点DFS
// “后序”指先对所有子节点DFS访问再输出当前节点
// 这里显然采用的“后序”的思路
tarjan(t,v);
// 对所有的子孙节点访问完毕之后 看当前节点能不能通过子孙节点回溯到更早的时间戳
low[v] = min(low[v],low[t]);
// 这里的判断很关键
if(low[t]>dfn[v])
// t和v不属于一个强连通分量
ans.push_back(vector{v,t});
}
//访问过 直接看能不能利用子孙节点更新能回溯到的时间戳
else{
low[v] = min(low[v],low[t]);
}
}
}
};再看一个有向图例子。
求给定图中的所有强连通分量。
参考代码
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>>connections;
void init()
{
connections.push_back(vector<int> {0,1});
connections.push_back(vector<int> {1,2});
connections.push_back(vector<int> {2,3});
connections.push_back(vector<int> {2,4});
connections.push_back(vector<int> {4,3});
connections.push_back(vector<int> {4,1});
connections.push_back(vector<int> {0,5});
connections.push_back(vector<int> {5,6});
connections.push_back(vector<int> {6,0});
}
// 标记顶点是否访问过
vector<int>vis;
// 每个顶点被访问的时间戳
vector<int>dfn;
// 每个顶点能通过子孙节点追溯到的最早时间点
vector<int>low;
// 记录图结构
vector<vector<int>>graph;
// 时间戳变量
int times = 1;
// 存储待求的所有连通分量
vector<vector<int>>ans;
// 求连通分量将用到一个栈
stack<int>s;
// 记录节点是否还在栈内
vector<int>exsit;
void tarjan(int v)
{
// 入栈的同时标记已访问
vis[v] = 1;
exsit[v]=true;
s.push(v);
dfn[v] = low[v] = times++;
// 访问该点的孩子节点（邻接节点）
for(auto t:graph[v])
{
// 没访问过
if(!vis[t])
{
tarjan(t);
// 子孙节点处理完后 看是否能利用子孙节点更新当前节点能回溯到的最早时间戳
low[v] = min(low[v],low[t]);
}
// 如果访问过
// 看这个节点是否还在栈内 还在栈内的可以被利用
// 已经出栈的节点属于其他独立的连通分量 和栈内节点已经没有联系
else if(exsit[t])
low[v] = min(low[v],dfn[t]);
}
// 如果当前节点是某个强连通分量的根节点
// 则将这个连通分量出栈
if(dfn[v]==low[v])
{
vector<int>tmp;
// 构成一个强连通分量的几个顶点都能回溯到该连通分量根节点的时间戳
do
{
tmp.push_back(s.top());
// 节点出栈
exsit[s.top()] = false;
s.pop();
}
while(!s.empty()&&low[s.top()]==low[v]);
ans.push_back(tmp);
}
}
void print(vector<vector<int>>ans)
{
for(auto v:ans)
{
for(auto t:v)
{
cout<<t<<" ";
}
cout<<endl;
}
}
int main()
{
// 初始化给定的数据
init();
// for(auto v:connections)
// {
// cout<<v[0]<<" "<<v[1]<<endl;
// }
// 这里给定的有向图顶点数目是 7
int n = 7;
vis.resize(n);
dfn.resize(n);
low.resize(n);
graph.resize(n);
exsit.resize(n);
for(auto v:connections)
{
// 注意是有向图 存储单方向
graph[v[0]].push_back(v[1]);
}
// for(int i=0; i<n; ++i)
// {
// if(!graph[i].empty())
// cout<<graph[i].size()<<endl;
// }
tarjan(0);
// 打印输出所有的强连通分量
print(ans);
return 0;
}
2. Kosaraju算法
Kosaraju算法的思想：对有向图G先求得反向图，利用DFS求得在反向图上的逆后序排列(拓扑序)；利用上一步中求的逆序列在原图上再做DFS，进行了几次DFS搜索就有几个强连通分量。
还是上面那个有向图的例子。
参考代码:
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>>connections;
void init()
{
connections.push_back(vector<int> {0,1});
connections.push_back(vector<int> {1,2});
connections.push_back(vector<int> {2,3});
connections.push_back(vector<int> {2,4});
connections.push_back(vector<int> {4,3});
connections.push_back(vector<int> {4,1});
connections.push_back(vector<int> {0,5});
connections.push_back(vector<int> {5,6});
connections.push_back(vector<int> {6,0});
}
// 存储逆序数排序的顶点
stack<int>s;
// 标记顶点是否访问过
vector<int>vis;
//记录强连通分量结果
vector<vector<int>>ans;
void print(vector<vector<int>>ans)
{
for(auto v:ans)
{
for(auto t:v)
{
cout<<t<<" ";
}
cout<<endl;
}
}
void dfs(vector<vector<int>>& graph,int v){
vis[v] = 1;
for(auto i:graph[v]){
if(!vis[i]){
dfs(graph,i);
}
}
s.push(v);
}
void dfs2(vector<vector<int>>& graph,int v,vector<int>& tmp){
vis[v] = 1;
tmp.push_back(v);
for(auto i:graph[v]){
if(!vis[i]){
dfs2(graph,i,tmp);
}
}
}
int main()
{
// 给定图的顶点数目
int n = 7;
// 根据给定的数据信息构建图G
vector<vector<int>>G(n);
init();
for(auto v:connections){
G[v[0]].push_back(v[1]);
}
for(int i=0; i<n; ++i)
{
if(!G[i].empty())
cout<<G[i].size()<<endl;
}
// 构建原图的反向图R
vector<vector<int>>R(n);
for(int i=0;i<n;++i){
for(int j=0;j<G[i].size();++j){
R[G[i][j]].push_back(i);
}
}
for(int i=0; i<n; ++i)
{
if(!R[i].empty())
cout<<R[i].size()<<endl;
}
vis = vector<int>(n,0);
// 对反向图DFS求逆后序排列
for(int i=0;i<n;++i){
if(!vis[i])
dfs(R,i);
}
cout<<"stack size: "<<s.size()<<endl;
// 在原图中按上一步得到的逆后序顶点排序再做一次DFS 统计强连通分量
vis = vector<int>(n,0);
while(!s.empty()){
auto p = s.top();s.pop();
if(!vis[p]){
vector<int>tmp;
dfs2(G,p,tmp);
ans.push_back(tmp);
}
}
cout<<"connected components num: "<<ans.size()<<endl;
// 打印所有强连通分量
print(ans);
return 0;
}
京公网安备 11010502036488号