问题标签 [kargers-algorithm]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
11 问题
0
投票
0
回答
25
浏览
c++ - 我在这里执行 Karger 的随机最小切割算法有什么问题吗？
我对代码的解释如下 -
- 函数 remove sl 最初删除图中的自循环。
- 函数 adjacency_list 以邻接表的形式读取输入文本文件并创建向量映射。地图中的每个键都充当节点，每个向量也是它相邻的节点列表。
该算法在函数 mincut 中实现。
- 当节点的数量大于两个时，它会先选择一个节点，然后再选择另一个节点来有效地选择一条随机边。
- 如果与节点 2 相邻的所有节点不为零或节点 1 本身，则将它们添加到节点 1 的列表中。
- 在 node1 的列表中 node2 的条目为零，因此也有效地消除了自循环。
- 任何其他等于 node2 的条目都等于 node1，因为该节点现在连接到 node1。
- Node2 从地图中移除。
- 在 while 循环之后，计算第一个节点中的所有非零条目以给出最小切割。
我注意到的一个错误是，在 mincut 步骤三中没有反映在图表中。否则我无法找到我出错的地方。