как реализовать дерево, где ветви имеют значение

Question

существует ли способ, которым соединение между двумя узлами (скажем, ветвь) может содержать значение?

Использование этого может быть в том, что существует переменная стоимости, и для перехода от одного узла к корню программа должна будет найти наиболее экономически эффективный маршрут.

показано как показано

Answer 1

Это довольно часто встречается в задачах с графами.Обычно вы создаете класс с именем Edge (или, возможно, Arc, или некоторые люди просто называют их lines), который содержит связь между двумя узлами и вес этого ребра / дуги / линии.

// Warning: this is really pseudo-code.

class Node;

class Edge {
    unsigned weight;
    Node *node;
};

class Node {    // Also often called a Vertex
    std::vector<Edge> edges;
    // ...
};

// find minimum cost path from start to end in a DAG:
unsigned find_path(Node &start, Node &end) { 
    unsigned current_weight = -1;

    for (auto const &e : start.edges) {
        if (e == end)
            return e.weight;
        weight = e.weight + find_path(*(e.node))
        if (weight < current_weight)
            current_weight = weight;
    return current_weight;
}

Обратите внимание, что это просто наиболее очевидный алгоритм обхода DFS методом грубой силы, поэтому он не практичен для больших графов или чего-то подобного.Хотя этого должно быть достаточно, чтобы передать общую идею.

Конечно, здесь можно добавить гораздо больше.Это просто краткий набросок, чтобы дать хотя бы начальную точку направления, в котором вы можете идти.