curious about find depth of a graph algorithm

Question

I'm very new to Data structure and algorithm, and we learn graph today, but i don't understand this code, here is it, this code use to find depth of graph:

struct Node {
    int id;
    int weight;

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

int depth_tree(vector 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 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);

}

i don't understand in 2 point:

FIRST: when calculate depth int max_d = depth_tree(graph, graph[root][0].id i understand it mean it take the id of [0] element of root Node for example when input

there that max_d would be 1,and 0 must be u when input in main(),but root (root is u not change value) so i think when call depth_tree(graph, 0) just to find deep of 0???????

SECOND:why int max_d = depth_tree(graph, graph[root][0].id)??? like above example there are 1 2 3 4??? so answer is should be 4(wrong but i don't understand)

ANYONE PLEASE EXPLAIN THIS CODE LOGIC, THANKS A LOTS, i'm very curious

user_1571709 · Answer

You start by the definition of the word Depth : The depth of a node is the number of edges from the node to the tree's root node.

The main idea to find the maximum depth is to slice the problem in smaller one.

What the simplest problem: what is the depth of a leaf root node? Well it's 0, because below a leaf there are no children and therefore you cannot traverse any edge.

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

Next, we ask: what is the depth of a node that is not a leaf? Well it depends on the depth of the children. Here the algorithm look for the max depth, so we need to look for the highest depth of the children.

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;
    }
}

And once we know that and because there is an edge between a child node and the current node we add 1.

return max_d + 1;

curious about find depth of a graph algorithm

1 Answers