Hello, everyone! Today, we will discuss a problem of finding the diameter of a tree using C#. This article will help you understand through problem definition, algorithm design, implementation, and testing process.<\/p>\n
\n The diameter of a tree refers to the length of the longest path between two nodes in the tree. The given tree is represented by the number of vertices \n An integer value representing the diameter of the tree.\n<\/p>\n \n The most common method to find the diameter of a tree is to use “two depth-first searches (DFS).” \n This method can efficiently determine the diameter of the tree. In the worst case, the time complexity is Below is the C# code based on the above algorithm:<\/p>\n \n 1. Your code can be validated with the following test cases:<\/p>\n \n If we draw the tree from the above input, it looks like this:\n<\/p>\nn<\/code> and n-1<\/code> edges.
\n Based on this, write a function to calculate the diameter of the tree.\n<\/p>\nInput<\/h3>\n
\n
n<\/code> : Number of vertices (2 \u2264 n \u2264 10^5)<\/li>\nn-1<\/code> edges that make up the tree. Each edge is given in the form of u v w<\/code>, where u<\/code> and v<\/code> are connected vertices, and w<\/code> is the weight between the two vertices.<\/li>\n<\/ul>\nOutput<\/h3>\n
Algorithm Design<\/h2>\n
\n Below is a summary of the simple procedure.\n<\/p>\n\n
A<\/code>.<\/li>\nA<\/code> to find the farthest vertex B<\/code>, and calculate the distance.<\/li>\n<\/ol>\nO(n)<\/code>.\n<\/p>\nC# Code Implementation<\/h2>\n
using System;\nusing System.Collections.Generic;\n\nclass TreeDiameter\n{\n static ListCode Explanation<\/h3>\n
graph<\/code>: An array to store the edges of the tree in an adjacency list format.
\n 2. visited<\/code>: An array to track visited vertices during DFS.
\n 3. maxDistance<\/code>: Stores the length of the longest path found so far.
\n 4. furthestNode<\/code>: Stores the ID of the farthest vertex.
\n 5. Main()<\/code>: Receives the tree structure input and calls DFS twice to calculate the diameter of the tree.
\n 6. DFS(int node, int distance)<\/code>: Implements the depth-first search function to recursively explore each vertex while updating the distance.\n<\/p>\nTest Cases<\/h2>\n
Test Input<\/h3>\n
5\n1 2 3\n1 3 2\n3 4 4\n3 5 1\n<\/code><\/pre>\nExpected Output<\/h3>\n
9\n<\/code><\/pre>\nDescription<\/h3>\n
\n 1\n \/ \\\n 2 3\n \/ \\\n 4 5\n<\/pre>\n