递归有序节点着色

Question

我想根据给定的节点顺序为给定图形的所有节点着色：顺序是通过 Iterator<Node> nodeIterator 参数设置的，该参数包含要按正确顺序处理的所有节点。

如果一个节点的邻居不是并且满足两个考虑的节点之间的特定条件，则该节点是彩色的。如果节点是参数 vector 的元素，则它是彩色的。节点使用其预定义的颜色着色。

这是我的代码：

  #Recursive method colorNodes
    colorNodes(Graph graph,Iterator<Node> nodeIterator, Vector vector)
        if (vector.size() == graph.size())
            return true;
        node = nodeIterator.next();
        nodeNeighbors = node.getNeighbors();
        while(nodeNeighbors.hasnext()) {
            neighbor = nodeNeighbors.next();
            if (!nodeIsColored(vector, neighbor)) {
                if(conditionBetweenNodeAndNeighbor is true) {
                    vector.add(node) #color current node 
                    colorNodes(graph, nodeIterator,vector)#call recursively the method
                }
            }  
            else if (!nodeNeighbors.hasNext()) {
                    #potential last node or isolated node (having one neighbor only)
                  if(conditionBetweenNodeAndNeighbor is true) {
                    vector.add(node) #color last node anyway 
                    colorNodes(graph, nodeIterator,vector)#call recursively the method
                    }
                   }
            else {
                    continue;
                }
          return false;
        }

谁能阐明如何解决这个问题以及我的方法是否正确（尤其是案例区分）？

Answer 1

我不确定我是否完全理解要求。请检查这个伪代码：

    //Recursive method colorNodes
    colorNodes(Graph graph,Iterator<Node> nodeIterator, Vector vector){
        
        if (vector.size() == graph.size())   return true;
        node = nodeIterator.next();       
        neighbors = node.getNeighbors()
        
        //check if leaf or isolted or all neigbors colored 
        if( (! nodeIterator.hasNext())  or  (neighbor.length == 0)   or (allNodesAreColored(neighbors))  ) { 
            //color leaf 
            if(conditionBetweenNodeAndNeighbor is true) {
                vector.add(node) 
                node.setColor(color)
                // no need for recursive call for a leaf 
            }
            return;
        }
        
        for(neighbor : neighbors ){

            if ((!nodeIsColored(vector, neighbor) and
                    (conditionBetweenNodeAndNeighbor is true) ){
                    vector.add(node) 
                    node.setColor(color)
                    colorNodes(graph, nodeIterator,vector)
                    //break if you don't want to check rest of the neighbors 
             }
         }                      
     }

Answer 2

我只是给出一个答案，因为递归有点尴尬。我期望以下内容 - 与逻辑无关。

// Recursive method colorNodes
void colorNodes(Graph graph, Iterator<Node> nodeIterator, List<Node> vector)
    //if (vector.size() == graph.size())
    //    return true;
    if (!nodeIterator.hasNext()) {
        return;
    }
    Node node = nodeIterator.next();
    if (nodeIsColored(vector, node)) {
        return;
    }               
    // Here the node is processed before the children, to stop recursion.
    vector.add(node);
    for (Node neighbor: node.getNeighbors()) {
        //if (!nodeIsColored(vector, neighbor)) {               
            colorNodes(graph, nodeIterator,vector);
        //}  
    }
    // Here the node could be processed after the children.
}

Vector<> 是旧的 class，并且在例如 C++ 中仍然使用该名称。

递归有序节点着色

recursive ordered node coloring

java

algorithm

recursion

pseudocode