Finding The Longest path in a tree using DFS

The logic behind finding the longest path in a tree (diameter of a tree) using Depth First Search (DFS) 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

DFS_Longest_Path_In_A_Tree



Program for finding the longest path in a tree

#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 << " ";
                        } 
                        max_path_length = longest_path.size();
                        return ;
                    }
                    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;
        }

        void 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);

    // Add edges to the tree
    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() << " nodes." << endl;
 
    return 0;
}

Output

Starting node : 15
Ending node   : 10
Longest Path : 15 14 11 7 3 0 1 4 9 10
Length of the longest path : 10 nodes.
import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;

class Tree{

    private int nodes;  // Nodes in a tree
    private int node_farthest_from_root; // Node farthest from the root node
    private int max_path_length; // To store the length of the longest path
    private int length; // Length calculated at the current node
    private int start_node, end_node; // The start and end nodes of the longest path
    private List<List<Integer>> adjlist; // Adjacency list to store the graph
    private boolean visited[];
    private List<Integer> longest_path; // Store the longest path from the start_node till the end_node
        
    Tree () {
    }

    Tree (int arg_nodes) { // Allocate resources

        nodes = arg_nodes;
        max_path_length = 0;
        node_farthest_from_root = 0;
        length = 0;

        adjlist = new ArrayList<>(nodes);
        for (int i=0; i<nodes; i++)
            adjlist.add(new ArrayList<>());

        visited = new boolean[nodes];
        longest_path = new ArrayList<>();
    }

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

        visited[src] = true;
        for (Integer adj_node : adjlist.get(src)) {
            if (!visited[adj_node]) {
                length++;
                DFS_GoFarthest(adj_node);
                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.
    */
    public void DFS_FindPath (int src) {

        visited[src] = true;
        for (Integer adj_node : adjlist.get(src)) {
            if (!visited[adj_node]) {
                longest_path.add(adj_node);
                if (adj_node == end_node) {
                    for (Integer node : longest_path) {
                        System.out.print(node + " ");
                    }
                    max_path_length = longest_path.size();
                    return;
                }
                DFS_FindPath(adj_node);
                longest_path.remove(longest_path.size()-1);
            }
        }
    }

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

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

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

    public void Set_StartAndEndNode (int arg_start_node, int arg_end_node) {
        start_node = arg_start_node;
        end_node   = arg_end_node;
        longest_path.add(start_node);
    }

    public static void main(String args[]) {

        Tree t = new Tree(16);
    
        // Add edges to the tree
        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 that was found earlier.
        // (start node is the 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);
        
        System.out.println("Starting node : " + start_node); 
        System.out.println("Ending node   : " + end_node);
    
        // Mark the nodes unvisited for another DFS traversal.
        t.MarkUnvisited();
    
        // Find the path from the start node to the end node.
        System.out.print("Longest Path : ");
        t.DFS_FindPath(start_node);
    
        System.out.print("\nLength of the longest path : " + t.Get_LenghtOfLongestPath() + " nodes.");
    }
}

Output

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


Copyright (c) 2019-2021, Algotree.org.
All rights reserved.