c++ - 用 C++ 实现 Bridesearch

Question

std::string Breitensuche ( std::array < std::list<std::array<int, 2>>, 3> list, int von, int zu ,std::string weg)
{
        std::list<int> markiert;
        for ( auto &b : list.at(von) )
        {
            if ( b.at ( 0 ) == zu )
                return
                weg += std::to_string ( b.at ( 0 ) );
            else
                markiert.push_back ( b.at ( 0 ) );

        }
        for ( auto &a : markiert )
        {
            Breitensuche ( list, a.at ( 0 ), zu );
        }


        return  "";
}
int main ( )
{
    std::array < std::list<std::array<int, 2>>, 3> Adjazenzliste { { { { { 0, 5 } } }, { { { 0, 5 } }, { { 2, 7 } } }, { { { 1, 4 } } } } };
    std::cout << Breitensuche ( Adjazenzliste, 1, 2 ,"");
    system ( "Pause" );
}

我正在尝试使用带有 adjazenzlists 的 C++ 实现图形的新娘搜索。 列表中保存的数组的第一部分是列表的起始节点连接到的节点的名称，第二部分是连接的权重。 所以基本上在这个初始化中有 3 个列表

0 -> 1
1 -> 0 -> 2
2 -> 1

在上面的函数中，尝试首先检查列表中的每个元素，如果它不是搜索到的节点，它就会被标记，然后函数被一次又一次地调用每个标记点，如果找到它返回节点名。 我遇到了没有进入深度搜索的问题，因为如果我递归地做它，它总是会先深入检查，然后再做下一步…… 此外，如果找到并返回它，我在保护“路径”方面遇到问题......

我希望你明白我的意思，抱歉我的英语不好

Answer 1

Wikipedia 中描述的广度优先搜索 算法不需要递归。伪代码讨论了用于排序的 queue q 和用于确保重复值仅匹配一次的 set V(大写 V)(我在代码中省略了这一点)下):

#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

template<class T>
struct tree_item {
    T value;
    vector<tree_item<T>> children;

    tree_item(T value) : value(value) {}
};

// constructs animated gif http://en.wikipedia.org/wiki/Breadth-first_search
tree_item<string> build_tree() {
    tree_item<string> a("a"), b("b"), c("c"), d("d"), e("e"), f("f"), g("g"), h("h");

    e.children = { h };
    b.children = {d, e};
    c.children = {f, g};
    a.children = {b, c};

    return a;
}

// implements "Algorithm" -> "Pseudocode" http://en.wikipedia.org/wiki/Breadth-first_search
template<class T>
bool find_breadth_first(const tree_item<T>& v, function<bool(const T&)> matcher, tree_item<T>& found_item) {
    queue<const tree_item<T>*> q; // step 2
    q.push(&v); // step 5

    while(!q.empty()) { // step 6
        auto t = q.front(); q.pop(); // step 7

        cout << "currently visiting " << t->value << endl;
        if(matcher(t->value)) { // step 8
            cout << t->value << " is a match " << endl;
            found_item = *t; return true; // step 9
        }

        for(auto& u : t->children) // step 11
            q.push(&u); // step 15
    }

    return false; // step 19
}

int main() {
    auto root = build_tree();

    tree_item<string> match("no match");
    auto matcher = [&](auto candidate) {
        return candidate == "g";
    };

    auto found = find_breadth_first<string>(root, matcher, match);

    if(found)
        cout << "found: " << match.value << endl;
    else
        cout << "not found" << endl;
}

输出:

currently visiting a
currently visiting b
currently visiting c
currently visiting d
currently visiting e
currently visiting f
currently visiting g
g is a match 
found: g