在樹中遍歷

Question

我正在研究TreeDecomposition，樹中的每個節點可以有多個圖中的頂點。
現在，我試圖找到第一個節點其中包含頂點u從樹的根。

int Tree::traversing(Node* node, int u){ 
    //search in current node 
    int j = node->point_in_bag(u); //this function returns position of vertex u in node if not available -1 
    if(j != -1){ 
     return node->index; 
    } 
    else{  
    // traverse in its children 
    for(int k=0; k<node->children.size(); k++){ // children has the node's childs in it 
     Node* nod = node->children[k]; 
     cout << "nod index is " << nod->index << endl; 
     traversing(nod,u); // if vertex isn't found in node, traverse again in its children 
     } 
    } 
} 

我已經嘗試像上面那樣，但它沒有返回確切的節點索引。我在哪裏做錯了。

Answer 1

你忘了return這裏：

traversing(nod,u); 

所以你的遞歸調用返回了一些隨機數據（並已未定義行爲）。

即使您已經返回，您也只會返回第一個孩子的索引。
如果找不到，你需要繼續尋找。

for(int k=0; k<node->children.size(); k++){ 
    Node* nod = node->children[k]; 
    int childIndex = traversing(nod,u); 
    if (childIndex != -1) 
     return childIndex; 
} 
return -1; 

您應該增加編譯器的警告級別。