当前位置： 文江博客 话题详情

从根到所有顶点中找到定向图中给定长度的所有路径

发布于 2025-01-17 17:12:50 字数 494 浏览 5 评论 0 原文

首先，如果我犯了任何英语错误，对不起。

我有以下图表 “在此处输入映像说明”

我需要找到 n length（例如4个顶点）的所有路径，仅从开始代码>。我使用C ++，无法更改语言。我使用Boost Graph库，并试图在没有成功的情况下了解他们的DFS访问者概念。

我什至接受“ 4K 2048 RAW”的路径 - ＆gt; “ 4K 2048 RAW” - ＆GT; “ 4K 2048 RAW” - ＆GT;例如，“ 4K 2048 RAW” 。

我使用像发电机一样的图。如果有人有或没有BGL的解决方案，请感谢您。

原文

First of all, if I make any English mistake, sorry in advance.

I have the following graph enter image description here

And I need to find all paths of an n length (4 vertices for example) starting only from "4K 2048 raw". I use C++ and I cannot change the language. I use the Boost Graph library and tried to understand their DFS visitor concept without success.

I even accept path like "4k 2048 raw" -> "4k 2048 raw" -> "4k 2048 raw" -> "4k 2048 raw" for example.

I use a graph like a generator. If anyone have a solution, with or without the BGL, thank you.

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（2）

香橙ぽ 2025-01-24 17:12:51

为什么不发布图表，并保存您的答复器10分钟的生命：

digraph {
    a [label="4k 2048 raw" ];
    b [label="4k 128 denoising" ];
    c [label="4k 32 denoising" ];
    d [label="4k 512 raw" ];
    e [label="2k 2048 raw" ];
    f [label="4k 128 raw" ];
    g [label="4k 32 raw" ];
    h [label="1k 2048 raw" ];

    a -> { h; g; f; c; b; e; d; };
    b -> { h; c; f; e; d; g; }
    c -> { h; g; f; e; d; }
    d -> { e; f; g; h; }
    e -> { f; h; g; }
    f -> { h; g; }
    g -> { h; }

    // self edges
    a -> a; b -> b; c -> c; d -> d;
    e -> e; f -> f; g -> g; h -> h;
}

比较结果在线a>。

使用BGL，

您可以，但我怀疑这确实有用，因为您描述的算法不容易存在，或者在BFS/DFS访问者上实施它会效率低下。这就是创建匹配 acchacency_list ：

实时在wandbox 

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>

using G = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
                                std::string>;
using V = G::vertex_descriptor;

int main() {
    G graph;

    auto a = add_vertex("4k 2048 raw", graph);
    auto b = add_vertex("4k 128 denoising", graph);
    auto c = add_vertex("4k 32 denoising", graph);
    auto d = add_vertex("4k 512 raw", graph);
    auto e = add_vertex("2k 2048 raw", graph);
    auto f = add_vertex("4k 128 raw", graph);
    auto g = add_vertex("4k 32 raw", graph);
    auto h = add_vertex("1k 2048 raw", graph);

    for (auto n : {h, g, f, c, b, e, d}) add_edge(a,n,graph);
    for (auto n : {h, c, f, e, d, g})    add_edge(b,n,graph);
    for (auto n : {h, g, f, e, d})       add_edge(c,n,graph);
    for (auto n : {e, f, g, h})          add_edge(d,n,graph);
    for (auto n : {f, h, g})             add_edge(e,n,graph);
    for (auto n : {h, g})                add_edge(f,n,graph);
    for (auto n : {h})                   add_edge(g,n,graph);
    // self edges
    for(auto n: boost::make_iterator_range(vertices(graph)))
        add_edge(n, n, graph);

    write_graphviz(std::cout, graph,
                make_label_writer(get(boost::vertex_bundle, graph)));
}

打印

digraph G {
0[label="4k 2048 raw"];
1[label="4k 128 denoising"];
2[label="4k 32 denoising"];
3[label="4k 512 raw"];
4[label="2k 2048 raw"];
5[label="4k 128 raw"];
6[label="4k 32 raw"];
7[label="1k 2048 raw"];
0->7 ;
0->6 ;
0->5 ;
0->2 ;
0->1 ;
0->4 ;
0->3 ;
0->0 ;
1->7 ;
1->2 ;
1->5 ;
1->4 ;
1->3 ;
1->6 ;
1->1 ;
2->7 ;
2->6 ;
2->5 ;
2->4 ;
2->3 ;
2->2 ;
3->4 ;
3->5 ;
3->6 ;
3->7 ;
3->3 ;
4->5 ;
4->7 ;
4->6 ;
4->4 ;
5->7 ;
5->6 ;
5->5 ;
6->7 ;
6->6 ;
7->7 ;
}

呈现为相同

请注意，我什至没有尝试在此时实施路径搜索。

应用 depth_first_visit 实际上对我们没有帮助，因为它不会访问两次顶点，因此您只能获得最小的路径子集：

live on Compiler Explorer上 

auto pretty =
    std::ranges::views::transform([&graph](V n) { return graph[n]; });

PathRecord vis([=](Path const& p) {
    if (p.size() == 4)
        fmt::print("{}\n", p | pretty);
});

std::vector<boost::default_color_type> colors(num_vertices(graph));
depth_first_visit(graph, A, vis, colors.data());

库（

["4k 2048 raw", "4k 32 denoising", "2k 2048 raw", "4k 128 raw"]
["4k 2048 raw", "4k 32 denoising", "2k 2048 raw", "1k 2048 raw"]
["4k 2048 raw", "4k 32 denoising", "2k 2048 raw", "4k 32 raw"]
["4k 2048 raw", "4k 32 denoising", "2k 2048 raw", "2k 2048 raw"]
["4k 2048 raw", "4k 32 denoising", "4k 512 raw", "2k 2048 raw"]
["4k 2048 raw", "4k 32 denoising", "4k 512 raw", "4k 128 raw"]
["4k 2048 raw", "4k 32 denoising", "4k 512 raw", "4k 32 raw"]
["4k 2048 raw", "4k 32 denoising", "4k 512 raw", "1k 2048 raw"]
["4k 2048 raw", "4k 32 denoising", "4k 512 raw", "4k 512 raw"]

使用标准库使用标准

和libfmt）（和libfmt）（和自libfmt in Standard-formatting尚未进行）在标准中）：

live in Compiler Explorer上 

#include <array>
#include <cassert>
#include <vector>

enum { a, b, c, d, e, f, g, h, NUM };
using Graph = std::array<std::array<bool, NUM>, NUM>; // adjacency matrix
using Path = std::vector<int>;

Graph make_sample() {
    Graph r;
    for (int t : {h, g, f, c, b, e, d}) r[a][t] = true;
    for (int t : {h, c, f, e, d, g})    r[b][t] = true;
    for (int t : {h, g, f, e, d})       r[c][t] = true;
    for (int t : {e, f, g, h})          r[d][t] = true;
    for (int t : {f, h, g})             r[e][t] = true;
    for (int t : {h, g})                r[f][t] = true;
    for (int t : {h})                   r[g][t] = true;
    // self edges
    for (int n = a; n < NUM; ++n)
        r[n][n] = true;
    return r;
}

template <typename Out>
Out explore(Graph const& g, Path current, unsigned length, Out out) {
    if (length) {
        for (int n = a; n < NUM; ++n) {
            if (g[current.back()][n]) {
                current.push_back(n);
                explore(g, current, length - 1, out);
                current.pop_back();
            }
        }
    } else {
        *out++ = current;
    }
    return out;
}

template <typename Out>
Out paths(Graph const& g, int start, unsigned length, Out out) {
    assert(length >= 1);
    return explore(g, {start}, length -1, out);
}

#include <fmt/ranges.h>
#include <ranges>
#include <set>

auto pretty(auto const& paths) {
    using std::ranges::views::transform;
    std::array static constexpr names{
        "4k 2048 raw", "4k 128 denoising", "4k 32 denoising", "4k 512 raw",
        "2k 2048 raw", "4k 128 raw",       "4k 32 raw",       "1k 2048 raw",
    };

    return fmt::join( //
        paths | transform([](Path const& p) {
            auto name_of = [](int n) { return names.at(n); };
            return p | transform(name_of);
        }),
        "\n - ");
}

int main() {
    std::vector<Path> vec;
    std::set<Path>    set;

    Graph g = make_sample();
    paths(g, 0, 4, back_inserter(vec));
    paths(g, 0, 4, inserter(set, set.end()));

    fmt::print("Set: {}\n - {}\n", set.size(), pretty(set));
    fmt::print("Vec: {}\n - {}\n", vec.size(), pretty(vec));
}

输出“ https://godbolt.org/z/t6e7wjpqv” rel =“ nofollow noreferrer”> length == 3 

Set: 51
 - ["4k 2048 raw", "4k 2048 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 512 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "2k 2048 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 128 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 32 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 128 denoising"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 512 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "2k 2048 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 128 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 32 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 512 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "2k 2048 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 128 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 32 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 512 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 512 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "4k 512 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 512 raw", "4k 512 raw"]
 - ["4k 2048 raw", "4k 512 raw", "2k 2048 raw"]
 - ["4k 2048 raw", "4k 512 raw", "4k 128 raw"]
 - ["4k 2048 raw", "4k 512 raw", "4k 32 raw"]
 - ["4k 2048 raw", "4k 512 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 512 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "2k 2048 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 128 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 32 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 128 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 128 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "4k 128 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 128 raw", "4k 128 raw"]
 - ["4k 2048 raw", "4k 128 raw", "4k 32 raw"]
 - ["4k 2048 raw", "4k 128 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 32 raw", "4k 32 raw"]
 - ["4k 2048 raw", "4k 32 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "1k 2048 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "1k 2048 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "1k 2048 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "1k 2048 raw", "1k 2048 raw"]
Vec: 51
 - ["4k 2048 raw", "4k 2048 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 512 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "2k 2048 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 128 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 32 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 128 denoising"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 512 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "2k 2048 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 128 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 32 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 512 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "2k 2048 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 128 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 32 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 512 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 512 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "4k 512 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 512 raw", "4k 512 raw"]
 - ["4k 2048 raw", "4k 512 raw", "2k 2048 raw"]
 - ["4k 2048 raw", "4k 512 raw", "4k 128 raw"]
 - ["4k 2048 raw", "4k 512 raw", "4k 32 raw"]
 - ["4k 2048 raw", "4k 512 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 512 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "2k 2048 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 128 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 32 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 128 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 128 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "4k 128 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 128 raw", "4k 128 raw"]
 - ["4k 2048 raw", "4k 128 raw", "4k 32 raw"]
 - ["4k 2048 raw", "4k 128 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 32 raw", "4k 32 raw"]
 - ["4k 2048 raw", "4k 32 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "1k 2048 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "1k 2048 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "1k 2048 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "1k 2048 raw", "1k 2048 raw"]

Why not post the graph, and save your answerers 10 minutes of their life:

digraph {
    a [label="4k 2048 raw" ];
    b [label="4k 128 denoising" ];
    c [label="4k 32 denoising" ];
    d [label="4k 512 raw" ];
    e [label="2k 2048 raw" ];
    f [label="4k 128 raw" ];
    g [label="4k 32 raw" ];
    h [label="1k 2048 raw" ];

    a -> { h; g; f; c; b; e; d; };
    b -> { h; c; f; e; d; g; }
    c -> { h; g; f; e; d; }
    d -> { e; f; g; h; }
    e -> { f; h; g; }
    f -> { h; g; }
    g -> { h; }

    // self edges
    a -> a; b -> b; c -> c; d -> d;
    e -> e; f -> f; g -> g; h -> h;
}

Compare the result online.

With BGL

You can, but I doubt it is really helpful as the algorithm you describe doesn't readily exist, or implementing it on the BFS/DFS visitors will be inefficient. Here's what it would look like to create a matching adjacency_list:

Live On Wandbox

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>

using G = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
                                std::string>;
using V = G::vertex_descriptor;

int main() {
    G graph;

    auto a = add_vertex("4k 2048 raw", graph);
    auto b = add_vertex("4k 128 denoising", graph);
    auto c = add_vertex("4k 32 denoising", graph);
    auto d = add_vertex("4k 512 raw", graph);
    auto e = add_vertex("2k 2048 raw", graph);
    auto f = add_vertex("4k 128 raw", graph);
    auto g = add_vertex("4k 32 raw", graph);
    auto h = add_vertex("1k 2048 raw", graph);

    for (auto n : {h, g, f, c, b, e, d}) add_edge(a,n,graph);
    for (auto n : {h, c, f, e, d, g})    add_edge(b,n,graph);
    for (auto n : {h, g, f, e, d})       add_edge(c,n,graph);
    for (auto n : {e, f, g, h})          add_edge(d,n,graph);
    for (auto n : {f, h, g})             add_edge(e,n,graph);
    for (auto n : {h, g})                add_edge(f,n,graph);
    for (auto n : {h})                   add_edge(g,n,graph);
    // self edges
    for(auto n: boost::make_iterator_range(vertices(graph)))
        add_edge(n, n, graph);

    write_graphviz(std::cout, graph,
                make_label_writer(get(boost::vertex_bundle, graph)));
}

Prints

digraph G {
0[label="4k 2048 raw"];
1[label="4k 128 denoising"];
2[label="4k 32 denoising"];
3[label="4k 512 raw"];
4[label="2k 2048 raw"];
5[label="4k 128 raw"];
6[label="4k 32 raw"];
7[label="1k 2048 raw"];
0->7 ;
0->6 ;
0->5 ;
0->2 ;
0->1 ;
0->4 ;
0->3 ;
0->0 ;
1->7 ;
1->2 ;
1->5 ;
1->4 ;
1->3 ;
1->6 ;
1->1 ;
2->7 ;
2->6 ;
2->5 ;
2->4 ;
2->3 ;
2->2 ;
3->4 ;
3->5 ;
3->6 ;
3->7 ;
3->3 ;
4->5 ;
4->7 ;
4->6 ;
4->4 ;
5->7 ;
5->6 ;
5->5 ;
6->7 ;
6->6 ;
7->7 ;
}

Which renders to the same

Note that I'm not even attempting to implementing the path search at this time.

Applying depth_first_visit doesn't really help us, because it doesn't visit any vertex twice, so you get only a minimal subset of the paths you're after:

Live On Compiler Explorer

auto pretty =
    std::ranges::views::transform([&graph](V n) { return graph[n]; });

PathRecord vis([=](Path const& p) {
    if (p.size() == 4)
        fmt::print("{}\n", p | pretty);
});

std::vector<boost::default_color_type> colors(num_vertices(graph));
depth_first_visit(graph, A, vis, colors.data());

Prints

["4k 2048 raw", "4k 32 denoising", "2k 2048 raw", "4k 128 raw"]
["4k 2048 raw", "4k 32 denoising", "2k 2048 raw", "1k 2048 raw"]
["4k 2048 raw", "4k 32 denoising", "2k 2048 raw", "4k 32 raw"]
["4k 2048 raw", "4k 32 denoising", "2k 2048 raw", "2k 2048 raw"]
["4k 2048 raw", "4k 32 denoising", "4k 512 raw", "2k 2048 raw"]
["4k 2048 raw", "4k 32 denoising", "4k 512 raw", "4k 128 raw"]
["4k 2048 raw", "4k 32 denoising", "4k 512 raw", "4k 32 raw"]
["4k 2048 raw", "4k 32 denoising", "4k 512 raw", "1k 2048 raw"]
["4k 2048 raw", "4k 32 denoising", "4k 512 raw", "4k 512 raw"]

Bespoke Using Standard Library

Using just the standard library (and libfmt since range-formatting is not yet in the standard):

Live On Compiler Explorer

#include <array>
#include <cassert>
#include <vector>

enum { a, b, c, d, e, f, g, h, NUM };
using Graph = std::array<std::array<bool, NUM>, NUM>; // adjacency matrix
using Path = std::vector<int>;

Graph make_sample() {
    Graph r;
    for (int t : {h, g, f, c, b, e, d}) r[a][t] = true;
    for (int t : {h, c, f, e, d, g})    r[b][t] = true;
    for (int t : {h, g, f, e, d})       r[c][t] = true;
    for (int t : {e, f, g, h})          r[d][t] = true;
    for (int t : {f, h, g})             r[e][t] = true;
    for (int t : {h, g})                r[f][t] = true;
    for (int t : {h})                   r[g][t] = true;
    // self edges
    for (int n = a; n < NUM; ++n)
        r[n][n] = true;
    return r;
}

template <typename Out>
Out explore(Graph const& g, Path current, unsigned length, Out out) {
    if (length) {
        for (int n = a; n < NUM; ++n) {
            if (g[current.back()][n]) {
                current.push_back(n);
                explore(g, current, length - 1, out);
                current.pop_back();
            }
        }
    } else {
        *out++ = current;
    }
    return out;
}

template <typename Out>
Out paths(Graph const& g, int start, unsigned length, Out out) {
    assert(length >= 1);
    return explore(g, {start}, length -1, out);
}

#include <fmt/ranges.h>
#include <ranges>
#include <set>

auto pretty(auto const& paths) {
    using std::ranges::views::transform;
    std::array static constexpr names{
        "4k 2048 raw", "4k 128 denoising", "4k 32 denoising", "4k 512 raw",
        "2k 2048 raw", "4k 128 raw",       "4k 32 raw",       "1k 2048 raw",
    };

    return fmt::join( //
        paths | transform([](Path const& p) {
            auto name_of = [](int n) { return names.at(n); };
            return p | transform(name_of);
        }),
        "\n - ");
}

int main() {
    std::vector<Path> vec;
    std::set<Path>    set;

    Graph g = make_sample();
    paths(g, 0, 4, back_inserter(vec));
    paths(g, 0, 4, inserter(set, set.end()));

    fmt::print("Set: {}\n - {}\n", set.size(), pretty(set));
    fmt::print("Vec: {}\n - {}\n", vec.size(), pretty(vec));
}

Output for length == 3

Set: 51
 - ["4k 2048 raw", "4k 2048 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 512 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "2k 2048 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 128 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 32 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 128 denoising"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 512 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "2k 2048 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 128 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 32 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 512 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "2k 2048 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 128 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 32 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 512 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 512 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "4k 512 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 512 raw", "4k 512 raw"]
 - ["4k 2048 raw", "4k 512 raw", "2k 2048 raw"]
 - ["4k 2048 raw", "4k 512 raw", "4k 128 raw"]
 - ["4k 2048 raw", "4k 512 raw", "4k 32 raw"]
 - ["4k 2048 raw", "4k 512 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 512 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "2k 2048 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 128 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 32 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 128 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 128 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "4k 128 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 128 raw", "4k 128 raw"]
 - ["4k 2048 raw", "4k 128 raw", "4k 32 raw"]
 - ["4k 2048 raw", "4k 128 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 32 raw", "4k 32 raw"]
 - ["4k 2048 raw", "4k 32 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "1k 2048 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "1k 2048 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "1k 2048 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "1k 2048 raw", "1k 2048 raw"]
Vec: 51
 - ["4k 2048 raw", "4k 2048 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 512 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "2k 2048 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 128 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 32 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 128 denoising"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 512 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "2k 2048 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 128 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 32 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 512 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "2k 2048 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 128 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 32 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 512 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 512 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "4k 512 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 512 raw", "4k 512 raw"]
 - ["4k 2048 raw", "4k 512 raw", "2k 2048 raw"]
 - ["4k 2048 raw", "4k 512 raw", "4k 128 raw"]
 - ["4k 2048 raw", "4k 512 raw", "4k 32 raw"]
 - ["4k 2048 raw", "4k 512 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 512 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "2k 2048 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 128 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 32 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 128 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 128 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "4k 128 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 128 raw", "4k 128 raw"]
 - ["4k 2048 raw", "4k 128 raw", "4k 32 raw"]
 - ["4k 2048 raw", "4k 128 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 32 raw", "4k 32 raw"]
 - ["4k 2048 raw", "4k 32 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "1k 2048 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "1k 2048 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "1k 2048 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "1k 2048 raw", "1k 2048 raw"]
回复 原文
灼痛 2025-01-24 17:12:51

使用深度优先搜索（DFS）的算法

   SELECT N as ROOT
   DFS from N until a leaf node is reached
   SAVE path from ROOT to leaf
   SELECT M as second last node in just saved path
   LOOP
       IF M = ROOT
          BREAK
       DFS from M until a leaf node is reached
       SET P to path from ROOT to M to leaf
       IF Leaf != ROOT AND ( P length is required OR greater )
          SAVE P
       SET M = second last node in P


   // this gives all the paths from ROOT to leaf nodes
   // now find paths to non leaf nodes

   LOOP P over saved paths
       LOOP V over nodes in P, except last
           SET P to path from ROOT to V
           IF P length is required
               SAVE P
   REMOVE saved paths longer than required
   SORT saved paths by their last node
   REMOVE duplicates
   OUTPUT saved paths

Algorithm using depth first search ( DFS )

   SELECT N as ROOT
   DFS from N until a leaf node is reached
   SAVE path from ROOT to leaf
   SELECT M as second last node in just saved path
   LOOP
       IF M = ROOT
          BREAK
       DFS from M until a leaf node is reached
       SET P to path from ROOT to M to leaf
       IF Leaf != ROOT AND ( P length is required OR greater )
          SAVE P
       SET M = second last node in P


   // this gives all the paths from ROOT to leaf nodes
   // now find paths to non leaf nodes

   LOOP P over saved paths
       LOOP V over nodes in P, except last
           SET P to path from ROOT to V
           IF P length is required
               SAVE P
   REMOVE saved paths longer than required
   SORT saved paths by their last node
   REMOVE duplicates
   OUTPUT saved paths
回复 原文
~没有更多了~

关于作者

橙味迷妹

暂无简介

文章
评论
27 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

佚名

文章 0 评论 0

今天

文章 0 评论 0

゛时过境迁

文章 0 评论 0

达拉崩吧

文章 0 评论 0

呆萌少年

文章 0 评论 0

孤者何惧

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文