相关概念:
连通图:在无向图中,如果图G中任意两个节点都是连通的,则称图G为连通图。
连通分量:无向图G的极大连通子图称为图的连通分量。连通分量可能不止一个,对每个连通分量,如果再向其中加入一个节点,这个子图就不连通。
下图中有几个连通分量? 答案:
|
强连通图:在有向图中,如果图中任意两个节点从u
到v
都有路径,且从v
到u
也有路径,则称图G为强连通图。
强连通分量:有向图G的极大强连通子图被称为图G的强连通分量。强连通分量也不止一个,对每个强连通分量,如果再向其中加入一个节点,这个子图就不是强连通图。
下图中有几个强连通分量? 答案:
|
强连通分量求解算法-Tarjan算法模板:
#define MAXN 1005 int G[MAXN][MAXN]; // 邻接矩阵 int n; // 顶点数,顶点编号从0开始 int timestamp; // 时间戳 int dfn[MAXN]; // 第一次遍历到达u的时间戳,至少为1,为0表示u还未被访问过 int low[MAXN]; // 从顶点u开始的DFS遍历能到达的最小时间戳 stack<int> stk; bool in_stk[MAXN]; // 记录顶点u是否在栈中 int scc_cnt; // 记录强连通分量的个数,也用于给强连通分量编号 int id[MAXN]; // 记录顶点所属的强连通分量编号 void tarjan_dfs(int u) { dfn[u] = low[u] = ++timestamp; // 第一次遍历到u,初始化当前点的时间戳 stk.push(u); in_stk[u] = true; for(int i = 0; i < n; i++) { // 遍历所有u能到的邻接点 if(G[u][i]) { if(dfn[i] == 0) { // 如果这个点还没被访问过 tarjan_dfs(i); // 遍历邻接点 low[u] = min(low[u], low[i]); // 子结点能到的最小时间戳u能也到 } else if(in_stk[i]) { // 如果这个点还在栈中,说明这个点比u点先访问到,它的时间戳也应该更早 low[u] = min(low[u], dfn[i]); // 用层级更高的点的时间戳更新u的low值 } } } if(dfn[u] = low[u]) { // 如果u为某个强连通分量的最高点,则可以输出这个强连通分量 scc_cnt++; // 连通分量数加1 int tmp; do { tmp = stk.top(); stk.pop(); in_stk[tmp] = false; id[tmp] = scc_cnt; // 标记这个点属于哪个强连通分量 } while(tmp != u); } } void tarjan() { for(int i = 0; i < n; i++) { // 对所有点进行强连通分量计算 if(dfn[i] == 0) { tarjan_dfs(i); } } } |
算法大概思路:
dfn[u]
。每次访问完一个节点的全部邻接点后,记录从这个节点开始DFS遍历能找到的最小时间戳,记为low[u]
。
|
dfn[u] == low[u]
,则说明u
是所在强连通分量的最高点,可以把这个强连通分量找出来。参考链接:
相关概念:
桥:在无向图中,如果去掉图G中的一条边e
,图G分裂为两个不相连的子图,那么e
就是图G的桥或割边。
割点:在无向图中,如果去掉图G中的一个点v
及v
关联的所有边,图G分裂为两个或以上不相连的子图,那么v
为图的割点。
桥与割点示例:
桥与割点的判断:
x
是割点case1:x
非root节点 && 有子节点 && low[x的子节点] >= dfn[x]
。x
是割点case2:x
是root节点 && 有>=2个子节点。x->y
是桥:low[y] >= dfn[x]
。了解low[y] >= dfn[x]
的含义,如果y
是x
的子节点,low[y] >= dfn[x]
表示从子节点y
无法回溯到比x
更早的结点,那么从x
点断开,子节点y
就和x
的祖先节点断开了,这就表示x
是一个割点,且边x->y
是桥。
求桥与割点代码模板:
#define MAXN 1005 int G[MAXN][MAXN]; // 邻接矩阵 int n; // 顶点数,顶点编号从0开始 int timestamp; // 时间戳 int dfn[MAXN]; // 第一次遍历到达u的时间戳,至少为1,为0表示u还未被访问过 int low[MAXN]; // 从顶点u开始的DFS遍历能到达的最小时间戳 int fa[MAXN]; // 记录顶点的父节点 bool iscut[MAXN]; // 记录节点是否为割点 bool isbridge[MAXN][MAXN]; // 记录边是否为桥 void tarjan_cut_bridge_dfs(int x) { dfn[x] = low[x] = ++timestamp; int child = 0; for(int y = 0; y < n; y++) { if(G[x][y]) { if(!dfn[y]) { // y未被访问过 child++; // x的子结点数加1 fa[y] = x; // 记录y的父结点为x tarjan_cut_bridge_dfs(y); if(fa[x] == -1 && child >= 2) { // x是root且有>=2个子结点 iscut[x] = true; } if(fa[x] != -1 && low[y] >= dfn[x]) { // x不是root && x有子结点 && low[y] >= dfn[x] iscut[x] = true; } if(low[y] >= dfn[x]) { // low[y] >= dfn[x] isbridge[x][y] = true; } low[x] = min(low[x], low[y]); } else if(y != fa[x]) { // y被访问过,且不是x的父结点 low[x] = min(low[x], low[y]); } } } } void tarjan_cut_bridge() { for(int i = 0; i < n; i++) { // 初始化全部的顶点的父结点为-1 fa[i] = -1; } for(int i = 0; i < n; i++) { if(dfn[i] == 0) { tarjan_cut_bridge_dfs(i); } } } |
参考链接: