目录

一、Tarjan算法

二、实现

三、小结

一、Tarjan算法

Tarjan算法是用来求有向图的强连通分量的。Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。

二、实现

package Algorithm.tarjan
import std.collection.*

public class TarjansAlgorithm {
    // DFS遍历的索引
    private var index = 0 
    // 记录每个顶点的访问顺序
    private var indices: Array<Int64>
    // 记录顶点能回溯到的最小索引
    private var lowLinks: Array<Int64>
    // 记录顶点是否在栈中
    private var onStack: Array<Bool>
    // 用于DFS的栈
    private var stack: ArrayList<Int64> 
    // 存储所有强连通分量
    private var sccs: ArrayList<ArrayList<Int64>>
    
    public init () {
        this.indices = Array<Int64>(0, item: -1)
        this.lowLinks = Array<Int64>(0, item: 0)
        this.onStack = Array<Bool>(0, item: false)
        this.stack = ArrayList<Int64>()
        this.sccs = ArrayList<ArrayList<Int64>>()
    }

    public func findSCCs(graph: Array<Array<Int64>>) {
        let n = graph.size
        this.indices = Array<Int64>(n, item: -1)
        this.lowLinks = Array<Int64>(n, item: 0)
        this.onStack = Array<Bool>(n, item: false)
        this.stack = ArrayList<Int64>()
        this.sccs = ArrayList<ArrayList<Int64>>()

        for (v in 0..n) {
            if (indices[v] == -1) {
                dfs(v, graph)
            }
        }

        return this.sccs
    }

    private func min(a: Int64, b: Int64): Int64 {
        if (a > b) {
            return a
        } else {
            return b
        }
    }
  
    private func dfs(v: Int64, graph: Array<Array<Int64>>): Unit {
        indices[v] = index
        lowLinks[v] = index
        index++
        stack.append(v)
        onStack[v] = true

        for (w in 0..graph[v].size) {
            if (indices[w] == -1) {
                // 递归访问未访问的邻接顶点
                dfs(w, graph);
                lowLinks[v] = min(lowLinks[v], lowLinks[w])
            } else if (onStack[w]) {
                // 遇到在栈中的顶点，更新lowLink值
                lowLinks[v] = min(lowLinks[v], indices[w])
            }
        }
 
        // 如果v是强连通分量的根节点
        if (lowLinks[v] == indices[v]) {
            let scc = ArrayList<Int64>()
            var w = 0
            do {
                w = stack.remove(stack.size - 1)
                onStack[w] = false
                scc.append(w)
            } while (w != v)
            sccs.append(scc)
        }
    }
}

测试环境

package Algorithm
import Algorithm.tarjan.*

main(): Int64 {
    // 示例图
    let graph = [
        [1], // 0 -> 1
        [2], // 1 -> 2
        [0, 3], // 2 -> 0, 3
        [4], // 3 -> 4
        [5], // 4 -> 5
        [3] // 5 -> 3
    ]
 
    let tarjan = TarjansAlgorithm()
    let sccs = tarjan.findSCCs(graph)
 
    println("强连通分量:");
    for (i in 0..sccs.size) {
        println(sccs[i])
    }
    return 0
}

三、小结

本章为大家详细的介绍了仓颉数据结构与算法中Tarjan算法的内容，下一章，为大家带来Tarjan算法练习题的内容。最后，创作不易，如果大家觉得我的文章对学习仓颉数据结构与算法有帮助的话，就动动小手，点个免费的赞吧！收到的赞越多，我的创作动力也会越大哦，谢谢大家🌹🌹🌹！！！