kotlin 无向图：周期复苏

yvgpqqbh 于 2023-10-23 发布在 Kotlin

关注(0)|答案(1)|浏览(88)

我有下一个任务：给定一个无向图。您需要确定它是否包含一个循环，如果是，则打印它。

输入数据

第一行包含一个数字n -图中的顶点数（1 ≤ n ≤ 500）。接下来，在n行中，图本身由邻接矩阵指定。

输出数据

如果源图形中没有循环，则打印“否”。否则，在第一行打印“YES”，在第二行打印数字k -循环中的顶点数，并且在第三行打印k个不同的数字-属于遍历顺序中的循环的顶点数（遍历可以从循环的任何顶点开始）。如果有多个循环，则打印任何一个。
示例：Inp

出来

YES
3
3 2 1

InP

出来
NO
我有下一个代码：

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

class Solution {
    fun findCycle(n: Int, graph: Array<IntArray>): List<Int>? {
        val visited = BooleanArray(n)
        val parent = IntArray(n) { -1 }

        fun dfs(v: Int): List<Int>? {
            visited[v] = true
            for (u in 0 until n) {
                if (graph[v][u] == 1) {
                    if (!visited[u]) {
                        parent[u] = v
                        val cycle = dfs(u)
                        if (cycle != null) return cycle
                    } else if (parent[v] != u) {
                        val cycle = mutableListOf<Int>()
                        var cur = v
                        while (cur != -1) {
                            cycle.add(cur + 1)
                            cur = parent[cur]
                        }
                        return cycle.reversed()
                    }
                }
            }
            return null
        }

        for (v in 0 until n) {
            if (!visited[v]) {
                val cycle = dfs(v)
                if (cycle != null) return cycle
            }
        }

        return null
    }
}

fun main() {
    val solution = Solution()
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))

    val n = reader.readLine()!!.toInt()
    val graph = Array(n) { IntArray(n) }
    for (i in 0 until n) {
        graph[i] = reader.readLine()!!.split(" ").map { it.toInt() }.toIntArray()
    }

    val cycle = solution.findCycle(n, graph)
    if (cycle != null) {
        writer.write("YES\n")
        writer.write("${cycle.size}\n")
        writer.write("${cycle.joinToString(" ")}\n")
    } else {
        writer.write("NO\n")
    }

    reader.close()
    writer.close()
}

我使用DFS和访问标志数组进行周期检测。对于循环恢复，使用父阵列。但是我的解决方案并没有完全被to the system接受（并不是所有的测试用例都通过了）。你能帮我在这里找到一个问题吗？

kotlin

来源：https://stackoverflow.com/questions/77294159/undirected-graph-cycle-recovery

1条答案

按热度按时间

w6lpcovy1#

我看到你的代码有两个逻辑问题：
1.重新访问一个节点并不意味着你有一个周期。考虑简单无向图A - B - C。如果你从A开始一次，从C开始一次，你将访问B两次，并且来自不同的父母。
1.遵循“母”链没有足够早地停止;你可以超越这个循环。以A - B - C - D - B为例。这里的循环是B - C - D - B，但是如果你的DFS从A开始，你将返回A - B - C - D - B，因为B是你的DFS的“根”。
我会把它们修改如下：
1.一个简单的“已访问”布尔数组是不够的。你想区分
1.未看到-遇到以前未看到的节点将其标记为“正在进行”;
1.进行中（仍在处理后代）-如果遇到这样的节点，则有一个循环;

finished -遇到一个finished节点不是一个循环，因此布尔数组是不够的。
1.当你遇到一个循环时，你遇到了一些已经在进行中的节点 u。简单地循环，直到你到达那个节点，而不是循环，直到你找到一个DFS“根”。
还要注意，你不需要反转列表（图是无向的，逆序和遍历顺序一样有效），也不需要“父”Map;毕竟，循环仍然存储在调用堆栈上的局部变量中。这里有一个有点黑客的方式来检索周期从那里：

enum class NodeState {Unseen, InProgress, Finished}
enum class TraversalState {CollectingCycle, CollectedCycle, Done}
fun findCycle(n: Int, graph: Array<Array<Int>>): List<Int>? {
    val state = Array<NodeState> (n) { NodeState.Unseen }
    val cycle = mutableListOf<Int>()
    var cycleNode = -1
    fun findCycle(v: Int, parent: Int): TraversalState {
        // Encountered an in-progress node => cycle!
        if (state[v] == NodeState.InProgress) {
            cycleNode = v
            return TraversalState.CollectingCycle
        }
        state[v] = NodeState.InProgress
        neighbors@ for (u in 0 until n) {
            if (graph[v][u] == 0 || u == parent) continue
            if (state[u] == NodeState.Finished) continue
            when (findCycle(u, v)) {
                TraversalState.Done -> {
                    continue@neighbors
                }
                TraversalState.CollectedCycle -> {
                    return TraversalState.CollectedCycle
                }
                TraversalState.CollectingCycle -> {
                    cycle.add(v)
                    if (cycleNode == v)
                        return TraversalState.CollectedCycle
                    return TraversalState.CollectingCycle
                }
            }
        }
        state[v] = NodeState.Finished
        return TraversalState.Done
    }
    for (v in 0 until n) {
        if (state[v] != NodeState.Unseen) continue
        // No need to reverse, any traversal order is valid
        if (findCycle(v, -1) == TraversalState.CollectedCycle) return cycle
    }
    return null
}

对于你的两个例子，

println(findCycle(3, arrayOf(arrayOf(0, 1, 1), arrayOf(1, 0, 1), arrayOf(1, 1, 0))))
println(findCycle(4, arrayOf(arrayOf(0, 0, 1, 0), arrayOf(0, 0, 0, 1), arrayOf(1, 0, 0, 0), arrayOf(0, 1, 0, 0))))

工作正常，分别打印[2, 1, 0]和null。
注意：你仍然需要添加一个顶点，例如。使用简单的map { it + 1 }。我考虑将此I/O添加到findCycle dirty。

赞(0）回复(0）举报 2023-10-23

我来回答

kotlin 无向图：周期复苏

1条答案

相关问题

热门标签

最新问答