检查给定关系是否可传递，如果不是，则添加新对以使其可传递

Question

我正在尝试检查给定关系是否具有传递性，如果不是，则添加新的关系对以使其具有传递性。输入示例：

aa ab ad be

函数应该是这样的： aa ab ad be ae 因为为了传递，如果 ab 和 bc 存在，ac 也必须存在。但是无论我尝试什么，我都会遇到分段错误。

我是 C++ 编程的新手，正在尝试了解迭代器。这是我的功能：

vector<string> isTransitive(vector<string> relations){
    bool flag;
    for(auto it=relations.begin();it != relations.end(); ++it){ 
        for(auto it2=relations.begin();it2 != relations.end(); ++it2){
            if((*it)[1] == (*it2)[0] && (*it)[0] != (*it)[1] && (*it2)[0]!=(*it2)[1]){ //if there exists ab and bc
                string newRelation;  //if there is a (a,b) (b,c) holds (a,c)
                newRelation.push_back((*it)[0]);
                newRelation.push_back((*it2)[1]);
                flag=false;
                for(auto it3=relations.begin();it3 != relations.end(); ++it3){
                    if(*it3==newRelation){
                        flag=true;
                        it3=relations.end(); //break the loop
                        it2=relations.end(); //break the loop
                    }
                }
                if(flag==false){
                    relations.push_back(newRelation);
                }
            }
        }
    }
    return relations;
}

if(*it3==newRelation) 当这个语句是 true 时，我得到了段错误。

Answer 1

一个for循环等同于一个while循环（来自cppreference）：

{

    init_statement
    while ( condition ) {

        statement
        iteration_expression ;

    } 

}

加上这两行：

it3=relations.end(); //break the loop
it2=relations.end(); //break the loop

你没有打破循环，但你导致了未定义的行为。两个迭代器都将首先递增，然后检查循环条件。那时 it3 不再是 relations.end()。大致是这样的：

{
    auto it = relations.begin();
    while (it != relations.end()) {
        it = relations.end();
        ++it;
    }
}

条件永远不会是 true 而你运行超出了 relations 的结尾。

要跳出循环，请使用 break。要跳出嵌套循环，您可以将它们放在函数中并使用 return.

检查给定关系是否可传递，如果不是，则添加新对以使其可传递

Check if the given relations are transitive and if not, add new pairs to make it transitive

c++

iterator

discrete-mathematics