java - 克鲁斯卡尔算法中的着色

Question

我正在 Java 中实现 Kruskals 算法，但我无法弄清楚跟踪访问顶点的最佳/最智能方法是什么。我应该给它们上色还是只是将顶点属性设置为访问或类似的东西？

Answer 1

I am implementing Kruskals algorithm in Java and i cannot figure out what would be the best/smartest way to track visited vertexes. Should i color them or just set vertex property to visited or something like that?

给它们着色和将它们设置为访问过是两件不同的事情。如果要将节点设置为已访问，可以使用标志数组( boolean 数组):

boolean[] visited = new boolean[numNodes];
visited[currNodeIdx] = true;

如果您已经为节点创建了类，只需更新属性:

class Node{
    private boolean visited;
    public void visited(boolean flag){
        visited = flag;
    }
}
//when updating the node
node.visited(true); 

您的后端算法不应该依赖于您的表示层(例如颜色变化)，而是，如果您想直观地显示访问的节点，您可以根据节点的访问状态设置颜色(而不是相反)。