怎样做网站公司的销售,小程序推广计划怎么赚钱,互联网广告推广是什么,积极推进在线网站建设1. 连通图概念
连通图#xff1a;无向图任意两点之间存在通路。 强连通#xff1a;有向图#xff08;前提#xff09;中#xff0c;任意两点都有至少一条通路#xff0c;则此图为强连通图。 弱连通图#xff1a;将有向图的有向边换成无向边得到的图是连通图#xff0c…1. 连通图概念
连通图无向图任意两点之间存在通路。 强连通有向图前提中任意两点都有至少一条通路则此图为强连通图。 弱连通图将有向图的有向边换成无向边得到的图是连通图则此有向图是弱连通图。
1.1 连通图和强连通图区别
连通图和强连通图的主要区别在于它们处理无向图和有向图的方式。以下是详细介绍
连通图。 连通图的概念基于无向图其中如果任意两个顶点之间都存在一条路径那么整个图被称为连通图。这意味着从任何一个顶点出发都可以通过路径到达图中的任何其他顶点。 强连通图。 强连通图的概念则针对有向图其中不仅要求从顶点vi到顶点vj存在路径还要求从顶点vj到顶点vi也存在路径对于所有顶点对vi和vj。这意味着图中不存在方向性的障碍任意两个顶点之间可以相互到达。 简而言之连通图关注的是无向图中顶点的连接性而强连通图关注的是有向图中顶点的双向连接性。
2. Targan强连通分量算法
2.1 基本概念
强连通分量 在有向图G中如果两个顶点u,v间u-v有一条从u到v的有向路径同时还有一条从v到u的有向路径则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通称G是一个强连通图。有向图的极大强连通子图称为强连通分量。 α \alpha α、 β \beta β、 γ \gamma γ 是三个强连通分量。
2.1 DFS遍历 方式1可以看作前序遍历 方式2可以看作后序遍历
3. 举例 回溯更新$j$ 相同 j j j出栈 a a a也出栈单独连通分量。
4. 代码实现 #include bits/stdc.husing namespace std;#define M (INT_MAX)
#define PRINT_ARRAY(a,n) do{for(int i 0; i n; i) couta[i]|; coutendl;}while(0)/**********************************************1 → 0 → 3↑ ↙ ↓2 43 → 4 ← 6 → 2↑↓ ↓ ↗ ↓ ↙↑7 → 5 → 0 → 1
**********************************************/
// #define V (5)
// int g[V][V]
// {
// {0,0,1,1,0},
// {1,0,0,0,0},
// {0,1,0,0,0},
// {0,0,0,0,1},
// {0,0,0,0,0}
// };#define V (8)
int g[V][V]
{ // 0 1 2 3 4 5 6 7 {0,1,0,0,0,0,0,0},{0,0,1,0,0,0,0,0},{1,0,0,0,0,0,0,0},{0,0,0,0,1,0,0,1},{0,0,0,0,0,1,0,0},{1,0,0,0,0,0,1,0},{1,0,1,0,1,0,0,0},{0,0,0,1,0,1,0,0}
};/**********************************************强连通分量 strongly connected component
**********************************************/void tarjan_dfs(int x, int dfn[], int low[], stackint s, bool in_stack[])
{static int time 1;dfn[x] low[x] time;s.push(x);in_stack[x] true;for(int y 0; y V; y){if(g[x][y]){if(0 dfn[y]){tarjan_dfs(y, dfn, low, s, in_stack);low[x] min(low[x], low[y]);}else if(in_stack[y])low[x] min(low[x], dfn[y]);}}if(dfn[x] low[x]){int tmp;do{tmp s.top(); s.pop();in_stack[tmp] false;couttmp-;}while(tmp ! x);coutendl;}
}void scc_tarjan()
{int dfn[V] {0}, low[V] {0};bool in_stack[V] {false};stackint s;for(int i 0; i V; i)if(!dfn[i])tarjan_dfs(i, dfn, low, s, in_stack);
}int main()
{scc_tarjan();return 0;
}参考资料 https://www.bilibili.com/video/BV19J411J7AZ?p1vd_source63c3682e66febb42e6a271165dd5a13e https://github.com/xiaoyazi333/data-structure-and-algorithm/
