时间戳

首页 > 解决方案 > 好奇查找图算法的深度

c++ - 好奇查找图算法的深度

问题描述

我是数据结构和算法的新手，今天我们学习图，但我不明白这段代码，这里是，这段代码用于查找图的深度：

struct Node {
    int id;
    int weight;

    Node(int id_, int weight_)
    {
        id = id_;
        weight = weight_;
    }
};

int depth_tree(vector<Node> graph[], int root)
{
    if (graph[root].size() == 0) {
        return 0;
    } else {
        int max_d = depth_tree(graph, graph[root][0].id);
        for (int i = 1; i < graph[root].size(); i++) {
            int d = depth_tree(graph, graph[root][i].id);
            if (d > max_d) {
                max_d = d;
            }
        }
        return max_d + 1;
    }
}

int main()
{
    int n;
    cin >> n;
    vector<Node> graph[n];

    int u, v;
    for (int i = 0; i < n - 1; i++) {
        cin >> u >> v;
        Node temp_uv(v, 0);
        graph[u].push_back(temp_uv);
    }

    cout << depth_tree(graph, 0);

}

我不明白 2 点：

第一：当计算深度时，我理解这意味着它在输入时采用节点int max_d = depth_tree(graph, graph[root][0].id的 [0] 元素的 idroot

5
0 1
0 2
1 3
3 4

u那里 max_d 将为 1，输入时必须为 0 main()，但是root（root不是u更改值）所以我认为调用时depth_tree(graph, 0)只是为了找到深度0???????

第二：为什么 int max_d = depth_tree(graph, graph[root][0].id)？？？像上面的例子有1 2 3 4？？？所以答案应该是 4（错误但我不明白）

任何人请解释这个代码逻辑，非常感谢，我很好奇

标签： c++graph-theory

解决方案

您从单词 Depth 的定义开始：节点的深度是从节点到树根节点的边数。

找到最大深度的主要思想是将问题切成更小的问题。

什么最简单的问题：叶根节点的深度是多少？嗯，它是 0，因为在叶子下面没有孩子，因此你不能遍历任何边缘。

if (graph[root].size() == 0) { // here root only means the current node
    return 0;

接下来，我们问：不是叶子的节点的深度是多少？好吧，这取决于孩子们的深度。这里算法寻找最大深度，所以我们需要寻找孩子的最高深度。

int max_d = depth_tree(..., ...[0]...);

for (int i = 1; i < graph[root].size(); i++) {

    // the loop starts at 1 because 0 is the highest depth so far

    int d = depth_tree(..., ...[i]...);

    if (d > max_d) { // if the new child is deeper

       // then this is the new max depth

       max_d = d;
    }
}

一旦我们知道这一点，并且因为在子节点和当前节点之间有一条边，我们就加 1。

return max_d + 1;

推荐阅读