小编Rev*_*per的帖子

我的目标是生成n个顶点的有向图,这样每个顶点都有一个边出口和一条边进入.我认为这样做的一种方法是将所有顶点放在一个底池中并让顶点轮流进行将它抽空并拉出条目 - 例如,如果顶点1拉出顶点3,则意味着边缘将从1移动到3.如果顶点将其自身拉出底池,它只会将其放回并重新洗牌.如果最后,最后一个顶点发现底池只包含自己,那么我们需要重新开始.这是我的Kotlin代码:

fun generateGraph(n: Int): Map<Int, Int> {
    val vertices : List<Int> = (1..n).toList()
    while (true) {
        val pot = vertices.toMutableList()
        val result = mutableMapOf<Int, Int>()
        for (vertex in 1 until n) {
            do {
                java.util.Collections.shuffle(pot)
            } while (pot[0] == vertex)
            result.put(vertex, pot.removeAt(0))
        }
        if (pot[0] != n) {
            result.put(n, pot.removeAt(0))
            return result
        }
        else {
            // The last vertex left in the pot is also the last one unassigned.  Try again...
        }
    }
}

它似乎工作.然而,在测试时我发现它比其他图形更多.当n为3时,唯一有效的图形是周期

{1=3, 2=1, 3=2} …