Components (Undirected)

无向图求联通分量

具体实现

class Components(graph: Graph) : GraphCompute(graph) {

    init {
        checkEmpty().checkDirected(false)
    }

    fun compute(): Result {
        val result = Result(graph)
        val visited = BooleanArray(graph.getVertexesNum())
        var count: Int

        graph.getVertexes().apply {
            count = 0
        }.forEach { vertex ->
            if (!visited[vertex.id]) {
                this.dfs(vertex, visited, result)
                count++
                result.setComponentCount(count)
            }
        }
        return result
    }

    private fun dfs(vertex: Vertex, visited: BooleanArray, result: Result) {
        visited[vertex.id] = true

        this.graph.adjacentEdges(vertex.id).forEach { edge ->
            val toV = edge.to
            if (visited[toV.id]) return@forEach

            // Union-Find 合并操作
            result.uf.union(vertex, toV)

            // 继续深度优先遍历
            this.dfs(toV, visited, result)
        }
    }

    class Result(private val graph: Graph) {
        private var _count = 0
        val componentCount: Int get() = _count
        internal val uf: UnionFind<Vertex> = IndexedUnionFind(Vertex::id)

        internal fun setComponentCount(count: Int) {
            this._count = count
        }

        fun hasPath(src: String, dest: String): Boolean {
            val srcV = graph.vertexIndex().getVertex(src)
            val destV = graph.vertexIndex().getVertex(dest)
            if (srcV == null || destV == null) return false
            return uf.isConnected(srcV, destV)
        }

    }

}