Find root vertex of a graph
A root vertex of a directed graph is a vertex u with a directed path from u to v for every pair of vertices (u, v) in the graph. In other words, all other vertices in the graph can be reached from the root vertex.
A graph can have multiple root vertices. For example, each vertex in a strongly connected component is a root vertex. In such cases, the solution should return anyone of them. If the graph has no root vertices, the solution should return -1.
The root vertex is 4 since it has a path to every other vertex in the following graph:
A simple solution would be to perform a DFS (or BFS) on all the graph vertices until we encounter a vertex from which every other vertex can be reached. The time complexity of this solution is O(V × (V + E)), where V and E are the total number of vertices and edges in the graph, respectively.
Another solution is to perform topological sorting on the graph. This will reduce the time complexity to linear but may not work for the cyclic graphs.
We can easily find the root vertex in O(n + m) time using a DFS. The idea is to start a DFS procedure from any node of the graph and mark the visited vertices. If there are any unvisited vertices, start the DFS again until all vertices are visited. Finally, the vertex having the maximum departure time in DFS is a candidate for the root vertex. We can easily check whether that vertex is a root vertex or not by doing a DFS (or BFS) on it.
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; // Data structure to store a graph edge struct Edge { int src, dest; }; // A class to represent a graph object class Graph { public: // a vector of vectors to represent an adjacency list vector<vector<int>> adjList; // Graph Constructor Graph(vector<Edge> const &edges, int n) { // resize the vector to hold `n` elements adjList.resize(n); // add edges to the directed graph for (auto &edge: edges) { adjList[edge.src].push_back(edge.dest); } } }; // Utility function to perform DFS traversal on the graph on a graph void DFS(Graph const &graph, int u, vector<bool> &visited) { // mark the current node as visited visited[u] = true; // do for every edge (u, v) for (int v: graph.adjList[u]) { // if `v` is not visited if (!visited[v]) { DFS(graph, v, visited); } } } // Function to find the root vertex of a graph int findRootVertex(Graph const &graph, int n) { // to keep track of all previously visited vertices in DFS vector<bool> visited(n); // find the last starting vertex `v` in DFS int v = 0; for (int i = 0; i < n; i++) { if (!visited[i]) { DFS(graph, i, visited); v = i; } } // reset the visited vertices fill(visited.begin(), visited.end(), false); // perform DFS on the graph from the last starting vertex `v` DFS(graph, v, visited); // return -1 if all vertices are not reachable from vertex `v` for (int i = 0; i < n; i++) { if (!visited[i]) { return -1; } } // we reach here only if `v` is a root vertex return v; } int main() { // vector of graph edges as per the above diagram vector<Edge> edges = { {0, 1}, {1, 2}, {2, 3}, {3, 0}, {4, 3}, {4, 5}, {5, 0} }; // total number of nodes in the graph (0 to 5) int n = 6; // build a directed graph from the given edges Graph graph(edges, n); // find the root vertex in the graph int root = findRootVertex(graph, n); if (root != -1) { cout << "The root vertex is " << root << endl; } else { cout << "The root vertex does not exist" << endl; } return 0; } |
Output:
The root vertex is 4
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 |
import java.util.ArrayList; import java.util.Arrays; import java.util.List; // A class to store a graph edge class Edge { int source, dest; public Edge(int source, int dest) { this.source = source; this.dest = dest; } } // A class to represent a graph object class Graph { // A list of lists to represent an adjacency list List<List<Integer>> adjList; // Constructor Graph(List<Edge> edges, int n) { adjList = new ArrayList<>(); for (int i = 0; i < n; i++) { adjList.add(new ArrayList<>()); } // add edges to the directed graph for (Edge edge: edges) { adjList.get(edge.source).add(edge.dest); } } } class Main { // Utility function to perform DFS traversal on the graph public static void DFS(Graph graph, int v, boolean[] discovered) { // mark the current node as discovered discovered[v] = true; // do for every edge (v, u) for (int u: graph.adjList.get(v)) { // `u` is not discovered if (!discovered[u]) { DFS(graph, u, discovered); } } } // Function to find the root vertex of a graph public static int findRootVertex(Graph graph, int n) { // to keep track of all previously visited vertices in DFS boolean[] visited = new boolean[n]; // find the last starting vertex `v` in DFS int v = 0; for (int i = 0; i < n; i++) { if (!visited[i]) { DFS(graph, i, visited); v = i; } } // reset the visited vertices Arrays.fill(visited, false); // perform DFS on the graph from the last starting vertex `v` DFS(graph, v, visited); // return -1 if all vertices are not reachable from vertex `v` for (int i = 0; i < n; i++) { if (!visited[i]) { return -1; } } // we reach here only if `v` is a root vertex return v; } public static void main(String[] args) { // List of graph edges as per the above diagram List<Edge> edges = Arrays.asList(new Edge(0, 1), new Edge(1, 2), new Edge(2, 3), new Edge(3, 0), new Edge(4, 3), new Edge(4, 5), new Edge(5, 0)); // total number of nodes in the graph (0 to 5) int n = 6; // build a directed graph from the given edges Graph graph = new Graph(edges, n); // find the root vertex in the graph int root = findRootVertex(graph, n); if (root != -1) { System.out.println("The root vertex is " + root); } else { System.out.println("The root vertex does not exist"); } } } |
Output:
The root vertex is 4
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
# A class to represent a graph object class Graph: def __init__(self, edges, n): # resize the list to hold `n` elements self.adj = [[] for _ in range(n)] # add an edge from source to destination for edge in edges: self.adj[edge[0]].append(edge[1]) # Function to perform DFS traversal on the graph def DFS(graph, v, discovered): discovered[v] = True # mark the current node as discovered # do for every edge (v, u) for u in graph.adj[v]: if not discovered[u]: # `u` is not discovered DFS(graph, u, discovered) # Function to find the root vertex of a graph def findRootVertex(graph, n): # to keep track of all previously discovered vertices in DFS discovered = [False] * n # find the last starting vertex `v` in DFS v = 0 for i in range(n): if not discovered[i]: DFS(graph, i, discovered) v = i # reset the discovered vertices discovered[:] = [False] * n # perform DFS on the graph from the last starting vertex `v` DFS(graph, v, discovered) # return -1 if all vertices are not reachable from vertex `v` for i in range(n): if not discovered[i]: return -1 # we reach here only if `v` is a root vertex return v if __name__ == '__main__': # List of graph edges as per the above diagram edges = [(0, 1), (1, 2), (2, 3), (3, 0), (4, 3), (4, 5), (5, 0)] # total number of nodes in the graph (0 to 5) n = 6 # build a directed graph from the given edges graph = Graph(edges, n) # find the root vertex in the graph root = findRootVertex(graph, n) if root != -1: print('The root vertex is', root) else: print('The root vertex does not exist') |
Output:
The root vertex is 4
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)