Minimum Edge Reversals to Make a Root

Approach

DFS Algorithm can be used to solve this problem. 

📝We begin with a depth-first-search at any random node of the given tree, and at each node of the tree, we record the distance from the starting node of the tree. 

📝Assuming that all edges are undirected, as well as the number of edges that need to be reversed to get from the starting node to the current node.

📝We'll refer to these as back edges since they point in the direction of the node. Using this algorithm, we also count the tree's total number of edge reversals.

📝Following this approach, we can determine the "number of edge reversals to reach every other node" at each node using the methods below.

Let’s Understand the algorithm, for Minimum Edge Reversals to Make a Root.

Algorithm

📌If the overall number of reversals in the tree is termed as Rev and some node is chosen, as the initial node for the depth-first search, then we have to reverse all back edges along the path. From node i to the starting node as well as all other back edges to reach every other node from the current node i.

📌The first part will be (distance of node I from starting node - back edges count at node I instead of, total edges (i.e., distance) minus back edges from node I to creating node because we want to reverse the edges along the path from node I to starting node (i.e., back edge count at node i).

📌After that, there will be a (total edge reversal or total back edges of tree Rev- back edge count of node i). After computing this at each node, we will select the lowest value as our result.

🧑‍💻The code below uses the DFS method to count reversal edges by adding weights of 0 for the specified edge direction and 1 for the reverse edge direction.

Let’s move to understand the implementation of Minimum Edge Reversals to Make a Root.

Code

C++

#include <bits/stdc++.h>
using namespace std;

/* method to depth_first_search in tree and populates distance_Rev values*/
int depth_first_search(vector<pair<int, int>> Tree_directed[],
                       pair<int, int> distance_Rev[], bool visited[], int u)
{
    /* visited current node*/
    visited[u] = true;
    int reversals = 0;

    /* looping over all neighbors*/
    for (int i = 0; i < Tree_directed[u].size(); i++)
    {
        int v = Tree_directed[u][i].first;
        if (!visited[v])
        {
           /*distance of node v will be one more than distance of node u*/
            distance_Rev[v].first = distance_Rev[u].first + 1;

            /*initialize back edge count same as
            parent nodes count*/
            distance_Rev[v].second = distance_Rev[u].second;

           /* if there is a reverse edge from given node u to node i,
            then only update the below*/
            if (Tree_directed[u][i].second)
            {
                distance_Rev[v].second = distance_Rev[u].second + 1;
                reversals++;
            }
            reversals += depth_first_search(Tree_directed, distance_Rev, visited, v);
        }
    }

    /* return total reversal in the subtree rooted at u*/
    return reversals;
}


/*This method prints root and minimum number of edge reversal*/
void min_edge_reversals_to_make_root(int edges[][2], int e)
{
   /* Since the count for the number of nodes is one more than the number of edges in the given hence*/
    int V = e + 1;

  /* data structure to store directed tree*/
    vector<pair<int, int>> Tree_directed[V];

    /* distance_Rev stores two values - distance and back
    edge count from root node*/
    pair<int, int> distance_Rev[V];

    bool visited[V];

    int u, v;
    for (int i = 0; i < e; i++)
    {
        u = edges[i][0];
        v = edges[i][1];

        /*add 0 weight in the direction of u to v*/
        Tree_directed[u].push_back(make_pair(v, 0));

       /* add 1 weight in reverse direction*/
        Tree_directed[v].push_back(make_pair(u, 1));
    }

    /*   initialize all variables*/
    for (int i = 0; i < V; i++)
    {
        visited[i] = false;
        distance_Rev[i].first = distance_Rev[i].second = 0;
    }

    int root = 0;

    /*depth_first_search populates distance_Rev data structure and
    store total reverse edge counts*/
    int reversals = depth_first_search(Tree_directed, distance_Rev, visited, root);

    /* UnComment the below lines to print each node's
    distance and edge reversal count from the root node*/
    /*
This will Print the Tree. Try it on our code studio editor.
    for (int i = 0; i < V; i++)
    {
        cout << i << " : " << distance_Rev[i].first
              << " " << distance_Rev[i].second << endl;
    }
    */

    int res = INT_MAX;

    /* Start to loop over all the nodes to choose minimum edge reversal*/
    for (int i = 0; i < V; i++)
    {
        /*(reversal in path to i) + (reversal
        in all other tree parts)*/
        int edgesToRev = (reversals - distance_Rev[i].second) +
                         (distance_Rev[i].first - distance_Rev[i].second);

       /* choose minimum among all values*/
        if (edgesToRev < res)
        {
            res = edgesToRev;
            root = i;
        }
    }

   /* print the designated root and total
    edge reversal made*/
    cout << root << " " << res << endl;
}


/* Driver code to test the above methods*/
int main()
{
    int Treeedges[][2] =
        {
            {0, 1},
            {2, 1},
            {3, 2},
            {3, 4},
            {5, 4},
            {5, 6},
            {7, 6}};
    int e = sizeof(Treeedges) / sizeof(Treeedges[0]);

    min_edge_reversals_to_make_root(Treeedges, e);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Python

# Python code to find min edge reversal
# to make every node reachable from the root
import sys

# Method to depth_first_search in the tree and populates
# distanceRev values
def depth_first_search(g, distanceRev, visited, u):
   
   # Visit the 
   #current node
   visited[u] = True
   totalRev = 0

   # Looping over 
   #all neighbors
   for i in range(len(g[u])):
       v = g[u][i][0]
       
       if (not visited[v]):
           
           # Distance of v will be one more
           # than the distance of u
           distanceRev[v][0] = distanceRev[u][0] + 1

           # Initialize back edge count same as
           # parent node's count
           distanceRev[v][1] = distanceRev[u][1]

           # If there is a reverse edge from node u to node i,
           # then only update the
           if (g[u][i][1]):
               distanceRev[v][1] = distanceRev[u][1] + 1
               totalRev += 1
               
           totalRev += depth_first_search(g, distanceRev, visited, v)

   # Return total reversal
   # in the subtree rooted at u
   return totalRev

# Method prints root and minimum number of
# edge reversal
def min_edge_reversals_to_make_root(edges, e):
   
   # Number of nodes are one more than
   # number of edges
   V = e + 1

   # Data structure to 
   #store directed tree
   g = [[] for i in range(V)]

   # distanceRev stores two values - distance
   # and back edge count from the root node
   distanceRev = [[0, 0] for i in range(V)]

   visited = [False for i in range(V)]

   # node u, 
   #and node v
   for i in range(e):
       u = edges[i][0]
       v = edges[i][1]
       
       # Add 0 weight in 
       #direction of u to v
       g[u].append([v, 0])

       # Add 1 weight in
       #reverse direction
       g[v].append([u, 1])

   # Initialize 
   #all variables
   for i in range(V):
       visited[i] = False
       distanceRev[i][0] = distanceRev[i][1] = 0

   root = 0

   # depth_first_search populates distanceRev data structure and
   # store total reverse edge counts
   totalRev = depth_first_search(g, distanceRev, visited, root)

   # UnComment below lines to preach node's
   # distance and edge reversal count from the root node
   #Coding Ninjas Studio
   # for (i = 0 i < V i++)
   # {
   #     cout << i << " : " << distanceRev[i][0]
   #         << " " << distanceRev[i][1] << endl
   # }
   res = sys.maxsize

   # Loop over all nodes to choose
   # minimum edge reversal
   for i in range(V):
       
       # (reversal in the path to i) + (reversal
       # in all other tree parts)
       edgesToRev = ((totalRev - distanceRev[i][1]) +
                 (distanceRev[i][0] - distanceRev[i][1]))

       # Choose minimum 
       #among all values
       if (edgesToRev < res):
           res = edgesToRev
           root = i

   # Print the designated root and total
   # edge reversal made
   print(root, res)

# Driver code
if __name__ == '__main__':
   
   edges = [ [ 0, 1 ], [ 2, 1 ],
             [ 3, 2 ], [ 3, 4 ],
             [ 5, 4 ], [ 5, 6 ],
             [ 7, 6 ] ]

   e = len(edges)

   min_edge_reversals_to_make_root(edges, e)

You can also try this code with Online Python Compiler

Run Code

Output

3 3

Time and Space Complexities

Time Complexity: O(V+E)

Space Complexity: O(H+V)

Where V is vertices and E edges and H is the height of the tree.

I hope now you have understood the Minimum Edge Reversals to Make a Root implementation and Algorithm.

Check out this problem - Reverse Nodes In K Group
Must Read  C Program to Reverse a Number

Frequently Asked Questions

Explain tree structure.

A group of nodes is referred to as a tree in the context of hierarchical data structures. Value is represented by nodes, which are linked together via edges. The following characteristics of trees: One root-named node makes up the tree.

Give an example of a tree structure.

You probably use a file system every day in your life. In any digital file system, directories, or folders, are structured as a tree internally.

Which database is best for tree structure?

Use any of the SQL databases you are most familiar with unless you're aiming at massive volumes of data (MSSQL, MySQL, Oracle). However, if your database has many hierarchy nodes, you might be better off using a specialized graph-oriented database.

What is a tree in SQL?

Each node in the SQL tree structure has a distinct, individual id. A reference to the parent node is present. We require the sequence number for each node in a submenu for ordering purposes.

Explain binary tree.

The left and right child are the only two children that each node may have in a binary tree, a type of tree data structure.

Conclusion

In this article, we have extensively discussed the problem of Minimum edge reversals to make a root, which was a question based on Trees.

To read more about Trees, see, Learn Tree, Binary Tree, and Master Tree Data Structures, Depth First Search.

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses, refer to the mock test and problems; look at the interview experiences and interview bundle for placement preparations.

Happy Learning, Ninjas!