目录

一、练习题

二、小结

一、练习题

1. 给定N个顶点若干条边， 求割点个数。

package Algorithm.tarjan
import std.collection.*

public class ArticulationPoints {
    // DFS时间戳
    private let time = 0
    // 发现时间
    private var disc: Array<Int64> = Array<Int64>()
    // 能回溯到的最早访问的顶点
    private var low: Array<Int64> = Array<Int64>()
    // 记录顶点是否被访问过
    private var visited: Array<Bool> = Array<Bool>()
    // 标记是否为割点
    private var isArticulation: Array<Bool> = Array<Bool>()
    // 图的邻接表表示
    private var graph: ArrayList<ArrayList<Int64>> = ArrayList<ArrayList<Int64>>()
 
    public func countArticulationPoints(n: Int64, edges: ArrayList<ArrayList<Int64>>): Int64 {
        // 构建邻接表
        graph = ArrayList<ArrayList<Int64>>()
        for (_ in 0..n) {
            graph.append(ArrayList<Int64>())
        }

        for (edge in 0..edges.size) {
            let u = edges[edge][0]
            let v = edges[edge][1]
            this.graph[u][v]
            this.graph[v][u]
        }
        // 初始化为-1表示未访问
        this.disc = Array<Int64>(n, item: -1)
        this.low = Array<Int64>(n, item: 0)
        this.visited = Array<Bool>(n, item: false)
        this.isArticulation = Array<Bool>(n, item: false)
 
        // 对于无向图，可能需要处理多个连通分量
        for (i in 0..n) {
            if (!visited[i]) {
                // -1表示没有父节点
                dfs(i, -1) 
            }
        }
 
        // 统计割点数量
        var count = 0;
        for (ap in this.isArticulation) {
            if (ap) {
                count++
            }
        }
        return count
    }

    private func min(a: Int64, b: Int64): Int64 {
        if (a > b) {
            return a
        } else {
            return b
        }
    }
 
    private func dfs(u: Int64, parent: Int64): Unit {
        visited[u] = true
        // 首先递增时间戳
        var time = 0 
        time++ 
        // 然后将递增后的时间戳赋值给disc[u]
        disc[u] = time
        // 最后将disc[u]的值赋给low[u]
        low[u] = disc[u];
        // 用于根节点判断
        var children = 0 
        for (i in 0..graph[u].size) {
            let v = graph[u][i]
            if (!visited[v]) {
                children++
                dfs(v, u)
                low[u] = min(low[u], low[v])
 
                // 判断割点条件
                if (parent != -1 && low[v] >= disc[u]) {
                    isArticulation[u] = true
                }
            } else if (v != parent) {
                // 遇到已访问的邻接顶点（非父节点），更新low值
                low[u] = min(low[u], disc[v])
            }
        }
 
        // 根节点且有至少两个子节点
        if (parent == -1 && children > 1) {
            isArticulation[u] = true
        }
    }
}

测试代码

package Algorithm
import Algorithm.tarjan.*
import std.collection.*

main(): Int64 {
    let n = 5
    let edges = ArrayList<ArrayList<Int64>>()
    edges.append(ArrayList<Int64>([0, 1]))
    edges.append(ArrayList<Int64>([1, 2]))
    edges.append(ArrayList<Int64>([2, 0]))
    edges.append(ArrayList<Int64>([1, 3]))
    edges.append(ArrayList<Int64>([3, 4]))
 
    let ap = ArticulationPoints()
    let count = ap.countArticulationPoints(n, edges)
    // 输出: 割点数量: 1 (顶点1)
    println("割点数量: ${count}") 
    return 0
}

二、小结

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