Tag: 图

连接图中的桥梁

我有一个编程任务（不是家庭作业），我必须在图表中find桥梁。 我自己做了一些，但是不能拿出任何令人满意的结果。 所以我GOOGLE了，我find了一些东西，但我无法理解算法，因为它是呈现。 有人可以看看这个代码，给我一个解释。 public Bridge(Graph G) { low = new int[GV()]; pre = new int[GV()]; for (int v = 0; v < GV(); v++) low[v] = -1; for (int v = 0; v < GV(); v++) pre[v] = -1; for (int v = 0; v < GV(); v++) if (pre[v] == -1) dfs(G, v, […]

为什么这种随机生成图表的方式不公平？

我的目标是生成一个有向图，包含n个顶点，每个顶点都有一个边缘出来，并有一个边缘进来。我认为这样做的一种方法是将所有的顶点放在一个底池中，顶点轮流洗牌和拉出条目 – 例如，如果顶点1拉出顶点3，那么意味着将有一个从1到3的边缘。如果一个顶点从jar子中拉出来，它就把它放回去重新洗牌。 如果最后一个顶点发现底池只包含它自己，那么我们需要重新开始。 这是我的Kotlin代码： fun generateGraph(n: Int): Map { val vertices : List = (1..n).toList() while (true) { val pot = vertices.toMutableList() val result = mutableMapOf() 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 } […]