Longest path in a tree

Finding longest path in a tree / diameters of a tree using Depth First Search (DFS) algorithm

The logic behind finding the longest path in a tree (diameter of a tree) is as below
a)    Traverse from the root node and find the farthest node from it using Depth First Search (DFS).
b)    Treat the farthest node from the root as the start node.
c)    Traverse from the start node and reach the farthest node using Depth First Search (DFS). The farthest node is the end node of the longest path.

Note: To print the actual path from the start node till the end node, we can do another DFS traversal.

Example of finding the longest path in a tree using depth-first search traversal

DFS_Longest_Path_In_A_Tree

C++ : Finding longest path in a tree using depth first search (DFS) implementation in C++11


#include<iostream>
#include<list>
#include<vector>
#include<stack>

using namespace std;

class Tree{

    private:

        int nodes;  // Nodes in a tree
        int node_farthest_from_root; // Node farthest from the root node
        int max_path_length; // To store the length of the longest path
        int length; // Length calculated at the current node
        int start_node, end_node; // The start and end nodes of the longest path
        list<int> *adjlist;
        vector<bool> visited;
        vector<int> longest_path; // Store the longest path from the start_node till the end_node
        
    public:

        Tree () {
        }

        Tree (int nodes) { // Allocate resources 
            max_path_length = 0;  
            node_farthest_from_root = 0;
            length = 0;
            adjlist = new list<int> [nodes];
            visited.resize(nodes, false);
            this->nodes = nodes;
        }

        ~Tree(){ // Free allocated resources
            delete [] adjlist;
        }

        void AddEdge (int src, int dst) {
            adjlist[src].push_back(dst);
            adjlist[dst].push_back(src);
        }
         
        /* Below DFS function finds 
           1. The length of the longest path from the source node.
           2. The node farthest from the source node.
        */
        void DFS_GoFarthest (int src) {

            visited[src] = true;
            for (auto& itr : adjlist[src]) {
                if (!visited[itr]) {
                    length++;
                    DFS_GoFarthest(itr);
                    length--;
                }
            }
            if (length > max_path_length) {
                max_path_length = length;
                node_farthest_from_root = src;
            }
        }

        /* Below DFS function
           1. Finds the longest path from the start node to the end node.
        */
        void DFS_FindPath (int src) {

            visited[src] = true;
            for (auto& itr : adjlist[src]) {
                if (!visited[itr]) {
                    longest_path.push_back(itr);
                    if (itr == end_node) {
                        for (auto& it : longest_path)
                            cout << it << " ";
                    }
                    DFS_FindPath(itr);
                    longest_path.pop_back();
                }
            }
        }

        // Mark nodes unvisited for next traversal
        void MarkUnvisited () {
            fill(visited.begin(), visited.end(), false);
        }

        void Reset_PathLengths () {
            length = 0;
            max_path_length = 0;
        }

        int Get_FarthestNode () {
            return node_farthest_from_root;
        }
      
        int Get_LenghtOfLongestPath () {
            return max_path_length;
        }

        int Set_StartAndEndNode (int arg_start_node, int arg_end_node) {
            start_node = arg_start_node;
            end_node   = arg_end_node;
            longest_path.push_back(start_node);
        }
};

int main() 
{
    Tree t(16);

    t.AddEdge(0,1);
    t.AddEdge(0,2);
    t.AddEdge(0,3);
    t.AddEdge(1,4);
    t.AddEdge(1,5);
    t.AddEdge(1,6);
    t.AddEdge(3,7);
    t.AddEdge(3,8);
    t.AddEdge(4,9);
    t.AddEdge(7,11);
    t.AddEdge(9,10);
    t.AddEdge(11,12);
    t.AddEdge(11,13);
    t.AddEdge(11,14);
    t.AddEdge(14,15);

    int start_node, end_node;

    // Find the node farthest from the root node i.e from node 0.
    t.DFS_GoFarthest(0);

    // Node farthest from the root will be the start node.
    start_node = t.Get_FarthestNode();

    // Mark the nodes unvisited for another DFS traversal.
    t.MarkUnvisited();

    // Once the node farthest from the root node is found, reset the max_path_length
    t.Reset_PathLengths();

    // Find the farthest node from the start node (farthest_node_from_root).
    t.DFS_GoFarthest(start_node);

    // Node farthest from the start node will be the end node.
    end_node = t.Get_FarthestNode();

    // Set the start node and the end node in the tree.
    t.Set_StartAndEndNode(start_node, end_node);
    
    cout << "Starting node : " << start_node << endl; 
    cout << "Ending node   : " << end_node << endl;

    // Mark the nodes unvisited for another DFS traversal.
    t.MarkUnvisited();

    // Find the path from the start node to the end node.
    cout << "Longest Path : ";
    t.DFS_FindPath(start_node);

    cout << endl << "Length of the longest path : " << t.Get_LenghtOfLongestPath() << endl;
 
    return 0;
}

Output showing the longest path in a tree found using depth-first search traversal

Starting node : 15
Ending node   : 10
Longest Path : 15 14 11 7 3 0 1 4 9 10
Length of the longest path : 9

Copyright © 2019-2020, Algotree.org.
All rights reserved.