{"id":34360,"date":"2024-11-01T09:27:16","date_gmt":"2024-11-01T09:27:16","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34360"},"modified":"2024-11-01T10:57:33","modified_gmt":"2024-11-01T10:57:33","slug":"c-coding-test-course-finding-the-diameter-of-a-tree-2","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34360\/","title":{"rendered":"C++ Coding Test Course, Finding the Diameter of a Tree"},"content":{"rendered":"

<\/p>\n

1. Problem Definition<\/h2>\n

This is the problem of finding the diameter of a given tree. The diameter of a tree refers to the length of the longest path between any two nodes. A tree is a graph composed of nodes and edges, characterized as a connected graph without cycles. To solve this problem, we can use either the DFS (Depth First Search) or BFS (Breadth First Search) algorithm.<\/p>\n

2. Problem Input<\/h2>\n

The first line contains the number of nodes N<\/code>. From the next line onwards, N-1<\/code> lines contain the edges, with each edge represented by two integers a<\/code> and b<\/code>. This indicates that there is an edge between node a<\/code> and node b<\/code>.<\/p>\n

Input Example<\/h3>\n
\n    5\n    1 2\n    1 3\n    2 4\n    2 5\n    <\/pre>\n
3. Problem Output<\/h2>\n
The program outputs the diameter of the tree.<\/p>\n
Output Example<\/h3>\n
\n    3\n    <\/pre>\n
4. Algorithm Explanation<\/h2>\n
The algorithm for finding the diameter of a tree proceeds as follows:<\/p>\n
    \n
  1. Store the tree in the form of an adjacency list.<\/li>\n
  2. Use the first DFS to find the farthest node.<\/li>\n
  3. Use a second DFS to find the farthest node from the one identified in the first DFS.<\/li>\n
  4. The result of the second DFS is the diameter of the tree.<\/li>\n<\/ol>\n
    5. C++ Code Implementation<\/h2>\n
    The C++ code to calculate the diameter of the tree is as follows:<\/p>\n
    \n#include \n#include \n#include \n\nusing namespace std;\n\nvector > tree;\nvector visited;\n\nint furthestNode(int node) {\n    visited[node] = true;\n\n    int maxDistance = 0;\n    int farthestNode = node;\n\n    for (int neighbor : tree[node]) {\n        if (!visited[neighbor]) {\n            int distance = furthestNode(neighbor) + 1;\n            if (distance > maxDistance) {\n                maxDistance = distance;\n                farthestNode = neighbor;\n            }\n        }\n    }\n\n    return farthestNode;\n}\n\nint main() {\n    int N;\n    cin >> N;\n\n    tree.resize(N + 1);\n    visited.resize(N + 1, false);\n\n    for (int i = 0; i < N - 1; i++) {\n        int a, b;\n        cin >> a >> b;\n        tree[a].push_back(b);\n        tree[b].push_back(a);\n    }\n\n    int farthestFromStart = furthestNode(1);\n    \n    fill(visited.begin(), visited.end(), false);\n    \n    int diameterEnd = furthestNode(farthestFromStart);\n    \n    cout << diameterEnd << endl;\n\n    return 0;\n}\n    <\/bool><\/vector<\/algorithm><\/vector><\/iostream><\/code><\/pre>\n
    6. Code Explanation<\/h2>\n
    The code is structured as follows:<\/p>\n
      \n
    1. Include libraries and declare global variables.<\/li>\n
    2. Perform DFS through the furthestNode<\/code> function to return the farthest node.<\/li>\n
    3. In the main function, read input and construct the tree.<\/li>\n
    4. Use the first DFS to find the farthest node from the starting node.<\/li>\n
    5. Use the second DFS to find the farthest node from the node found in the first DFS, which will be the end of the diameter.<\/li>\n
    6. Output the length of the diameter.<\/li>\n<\/ol>\n
      7. Time Complexity Analysis<\/h2>\n
      The time complexity of this algorithm is O(N)<\/code>. It executes DFS for each node while visiting N<\/code> nodes, thus it is proportional to the size of the tree.<\/p>\n
      8. Conclusion<\/h2>\n
      In this lesson, we learned how to solve the problem of finding the diameter of a tree. It is important to understand the process of exploring the tree’s structure and deriving a solution using DFS. By practicing various graph problems, you can enhance your algorithm skills.<\/p>\n
      9. References<\/h2>\n