2021-1 计算强连通分量的个数 Kosaraju算法 c++
强连通分量的API理论准备点这里实现#pragma once#include"Digraph.h"#include"DepthFirstOrder.h"class KoarajuSCC{public:KoarajuSCC(Digraph& G);int count() { return m_count; }bool stronglyConnected(int v, int w) {retu
·
强连通分量的API
理论准备点这里
实现
#pragma once
#include"Digraph.h"
#include"DepthFirstOrder.h"
class KoarajuSCC
{
public:
KoarajuSCC(Digraph& G);
int count() { return m_count; }
bool stronglyConnected(int v, int w) {
return (*m_id)[v] == (*m_id)[w];
}
int id(int v) {
return (*m_id)[v];
}
private:
vector<bool>* m_marked = nullptr;
vector<int>* m_id = nullptr;//几号强连通分量,0-m_count-1
int m_count = 0;//强连通分量个数
void dfs(Digraph& G, int v);
};
void testForKoarajuSCC();
#include "KoarajuSCC.h"
KoarajuSCC::KoarajuSCC(Digraph& G)
{
m_marked = new vector<bool>(G.V(), false);
m_id = new vector<int>(G.V(), 0);
DepthFirstOrder* order = new DepthFirstOrder(G.reverse());
stack<int>* stk = order->getRePost();
while (!stk->empty()) {
int s = stk->top(); stk->pop();
if (!m_marked->at(s)) {
dfs(G, s);
m_count++;//完成一次dfs,强联通分量数目加一
}
}
}
void KoarajuSCC::dfs(Digraph& G, int v)
{
m_marked->at(v) = true;
m_id->at(v) = m_count;//同一次dfs访问到的都是同一个联通分量
forIt(G.adj(v)) {
int w = *it;
if (!m_marked->at(w)) {
dfs(G, w);
}
}
}
void testForKoarajuSCC()
{
Digraph G("tinyDG.txt");
KoarajuSCC scc(G);
out("strongly connected componentTarjan has ");
out(scc.count()), hh;
out("9 belongs to id_"), out(scc.id(9)),hh;
out("0 belongs to id_"), out(scc.id(0)),hh;
out("9 0 is strongly connected ? ");
out(scc.stronglyConnected(0, 9)),hh;
}
测试图
下载文件 tinyDG.txt
头文件见 DepthFirstOrder.h
更多推荐
已为社区贡献6条内容
所有评论(0)