标签：js，JavaScript，tarjan，代码，图算法，求强连通分量，开箱即用，带输入输出的例程，2020网易提前批笔试8月8日前端/客户端/算法第四题
首先要理解tarjan算法，资源如下
- 百度百科的注释比较多，也提供了几种编程语言的代码
- b站很多视频资源，搜tarjan，即出现.
-
SHHHS的配图对理解tarjan算法的深搜流程很有帮助，下方图片来源于该资源
本代码所用的例子
从结点1开始dfs，dfs构成dfs树，每新到达一个结点，就将它添加到dfs树中。每完成一个强连通分量，就将该强连通分量中的所有结点从dfs树中删除。每个结点所在强连通分量一定是某个dfs树的一个子树。
定义强连通分量的根节点root_x：强连通分量的所有结点中最先被深搜访问到的结点称为该强连通分量的根节点。
深搜中，发现next结点被访问过，且属于当前dfs树，那么curr与next构成强连通，就判断当前的root_x和next结点哪个更靠近dfs树的根，取为新的root_x。
为了判断哪个结点更靠近dfs树的根，增加辅助数组dfn，记录结点x是深搜中第几个被访问到的；增加辅助数组low，记录元素x所在强连通分量的根节点root_x，记录方式是low[x]=dfn[root_x]。
合并强连通分量时（dfs回退时合并，dfs子树合并父亲），更新为dfn[x]中的最小值。（x属于待合并的连通分量的并集）
深搜中，如果一个结点还没有被访问过，比如(a,b)这条边，b没有被访问过，那么b要做初始化：
- 已经访问过b
- 是深搜中第dfn[b]个被访问到的
- (b,a)边在当前在深搜树中一定不存在，所以初始化b所在的强连通分量的根节点是b本身，low[x]=dfn[b]
// 现在6没有next，由于6的root_6==low[6]==4，同时6是第dfn[6]==4个被访问到的，两个值相等，所以得到{6}这个强连通分量；同时将该连通分量从dfs栈中删除。
// 5除了6之外也没有next，dfs退栈，栈顶5也没有没访问过的next了，类似得到{5}，现在dfs栈是[13]
// 继续dfs到[134]，下一个是1，发现1已经在栈里面了，更新low[4]为dfn[1]，现在4没有next了，dfs回退，更新low[3]为low[4]，3没有next了，dfs回退，更新low[1]为low[3]
// 现在回到了结点1，dfs压栈没有到达过的2，下一个4，由于4在栈中，所以2也属于当前强连通，更新low[2]=dfn[4]。当前dfs栈1342
// 2没有没访问过的next了，dfs回退，更新low[1]=low[2]，dfs回退，dfs退到dfs树的根节点了，当前以1的出度为起点边的弱连通分量已完成
// tarjan求的是起点结点所在的强连通分量，但当要求图中所有强连通分量时，实际选择的起点可能是5，那么1234都没有访问到，所以要对所有结点都调一次tarjan方法。
// TODO: 输入
var n = 6;//共有6个结点
var edges = [[1, 3], [3, 5], [5, 6], [3, 4], [4, 6], [4, 1], [1, 2], [2, 4]];
// 转换为结点i的直接next都有谁
var head = Array(n + 1).fill(null).map((_, x) => new Array());// 因为结点从1开始而下标从0开始//每个元素初始化为空list
for (var edge of edges) {
head[edge[0]].push(edge[1])
}
//此时的head：[ [], [ 3, 2 ], [ 4 ], [ 5, 4 ], [ 6, 1 ], [ 6 ], [] ]第一个元素是index0，可忽略
// TODO: 初始化
var dfn = Array(n+1).fill(0);//深度优先搜索中i的访问次序，dfn[i]==0则说明没有访问过
var low = Array(n+1).fill(null);//结点i所在强连通分量的跟（能追溯到的最早被访问过的）
var in_stack = Array(n+1).fill(false);//元素i当前不在栈中，这里的栈指的是Tarjan算法中的栈
var stack = [];//Tarjan算法中的栈
var res = [];//一个元素是一个强连通分量，每个强连通分量是list
var dfs_num = 0;//当前已经访问了dfs_num个结点了。当前结点是深搜中第dfs_num个被访问的。
/**
* 以x为起点深搜得到的弱连通分量中所有强连通分量（包括整个图中包含x的强连通）都push到res中
* @param {*} x 结点/结点名称/图中的结点编号，从1开始
* @param {*} indentation 打印深搜过程时提供缩进
*/
function Tarjan(x,indentation) {
// TODO：x被访问的初始化
// 打印深搜过程
console.log(indentation,x,head[x]);
indentation+='| ';
// 深度优先搜索中x是第几个被访问的，当前强连通分量的根是元素本身
dfs_num+=1;
dfn[x] = dfs_num;
low[x] = dfs_num;
// 压栈x（Tarjan算法中的栈）
in_stack[x] = true;
stack.push(x);
// TODO：深搜，将x所在的，且以x为起点的弱连通分量中所有元素压栈
// 遍历x的所有next结点，更新x所在弱连通分量的栈底为能追溯到的最早的结点
for(var curr of head[x]) {
if (dfn[curr]==0) {//结点curr没被访问过
Tarjan(curr,indentation);//继续找next结点
low[x] = Math.min(low[x], low[curr]);// x和curr的强连通分量的根节点中更早被访问的一个
}
else if (in_stack[curr]){// curr当前在栈中
low[x] = Math.min(low[x], dfn[curr]);// x的强连通的根和curr哪个更早被访问
// low[x] = Math.min(low[x], low[curr]);// 仅限求强连通时，可以
}
}
//构成强连通分量
//深搜构成递归栈，该栈退栈到结点x时发现x是x所在强连通的根节点，
// 此时将以x为起点的弱连通分量从栈中弹出，这些元素组成了强连通分量
if (dfn[x] == low[x]) {
// console.log('stack',stack)
var curr = stack.pop();
in_stack[curr]=false;
res.push([curr]);
while (curr != x && stack.length>0) {
// 出栈
curr=stack.pop();
in_stack[curr] = false;
// res
res[res.length-1].push(curr)
}
// console.log('save',res)
}
}
// TODO：遍历所有结点，找到所有强连通分量
for(var i=1;i<=n;i++){
// i没有被访问过，否则x所在强连通分量已知
if(dfn[i]==0){
Tarjan(i,'| ');
}
}
// TODO：打印输出
console.log(res)
/**
深搜过程：（每行开头数字是当前结点，list是它的next数组）
| 1 [ 3, 2 ]
| | 3 [ 5, 4 ]
| | | 5 [ 6 ]
| | | | 6 []
| | | 4 [ 6, 1 ]
| | 2 [ 4 ]
结果：
[ [ 6 ], [ 5 ], [ 2, 4, 3, 1 ] ]
*/
FYI：安装了node，则命令行执行node 文件名.js即可看到输出
一道练习题，2020网易云提前批笔试8月8日前端/客户端/算法第四题，求互相认可的教授有几对
输入内容的格式相同，把edges和n改下代码即可。
输出则得到各个强连通分量各有几个结点tmp，比如[2,3]有两个强连通分量，一个有2个结点，一个有3个结点，然后利用组合的公式来计算从tmp里选2个结点有几种结果：C(tmp,2),公式推导结果C(tmp,2)=A(tmp,2)/A(2,2)=[ tmp!/(tmp-2)! ] / [ 2!/(2-2)! ]=tmp*(tmp-1)/2
total = 0
for tmp of res:
total += tmp*(tmp-1)/2
return total
更多练习题推荐leetcode或牛客中找图相关的内容
