Given a graph, G consisting of N nodes, a source S, and an array Edges[][2] of type {u, v} that denotes that there is an undirected edge between node u and v, the task is to traverse the graph in lexicographical order using DFS.
Examples:
Input: N = 10, M = 10, S = ‘a’, Edges[][2] = { { ‘a’, ‘y’ }, { ‘a’, ‘z’ }, { ‘a’, ‘p’ }, { ‘p’, ‘c’ }, { ‘p’, ‘b’ }, { ‘y’, ‘m’ }, { ‘y’, ‘l’ }, { ‘z’, ‘h’ }, { ‘z’, ‘g’ }, { ‘z’, ‘i’ } }
Output: a p b c y l m z g h iExplanation:
For the first level visit the node and print it:
Similarly visited the second level node p which is lexicographical smallest as:
Similarly visited the third level for node p in lexicographical order as:
Now the final traversal is shown in the below image and labelled as increasing order of number:
Input: N = 6, S = ‘a’, Edges[][2] = { { ‘a’, ‘e’ }, { ‘a’, ‘d’ }, { ‘e’, ‘b’ }, { ‘e’, ‘c’ }, { ‘d’, ‘f’ }, { ‘d’, ‘g’ } }
Output: a d f g e b c
Approach: Follow the steps below to solve the problem:
- Initialize a map, say G to store all the adjacent nodes of a node according to lexicographical order of the nodes.
- Initialize a map, say vis to check if a node is already traversed or not.
- Traverse the Edges[][2] array and store all the adjacent nodes of each node of the graph in G.
- Finally, traverse the graph using DFS and print the visited nodes of the graph.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to traverse the graph in// lexicographical order using DFSvoid LexiDFS(map<char, set<char> >& G, char S, map<char, bool>& vis){ // Mark S as visited nodes vis[S] = true; // Print value of visited nodes cout << S << " "; // Traverse all adjacent nodes of S for (auto i = G[S].begin(); i != G[S].end(); i++) { // If i is not visited if (!vis[*i]) { // Traverse all the nodes // which is connected to i LexiDFS(G, *i, vis); } }}// Utility Function to traverse graph// in lexicographical order of nodesvoid CreateGraph(int N, int M, int S, char Edges[][2]){ // Store all the adjacent nodes // of each node of a graph map<char, set<char> > G; // Traverse Edges[][2] array for (int i = 0; i < M; i++) { // Add the edges G[Edges[i][0]].insert( Edges[i][1]); } // Check if a node is already // visited or not map<char, bool> vis; // Function Call LexiDFS(G, S, vis);}// Driver Codeint main(){ int N = 10, M = 10, S = 'a'; char Edges[M][2] = { { 'a', 'y' }, { 'a', 'z' }, { 'a', 'p' }, { 'p', 'c' }, { 'p', 'b' }, { 'y', 'm' }, { 'y', 'l' }, { 'z', 'h' }, { 'z', 'g' }, { 'z', 'i' } }; // Function Call CreateGraph(N, M, S, Edges); return 0;} |
Java
// Java program for above approachimport java.util.*;class Graph{// Function to traverse the graph in// lexicographical order using DFSstatic void LexiDFS(HashMap<Character, Set<Character>> G, char S, HashMap<Character, Boolean> vis){ // Mark S as visited nodes vis.put(S, true); // Print value of visited nodes System.out.print(S + " "); // Traverse all adjacent nodes of S if (G.containsKey(S)) { for(char i : G.get(S)) { // If i is not visited if (!vis.containsKey(i) || !vis.get(i)) { // Traverse all the nodes // which is connected to i LexiDFS(G, i, vis); } } }}// Utility Function to traverse graph// in lexicographical order of nodesstatic void CreateGraph(int N, int M, char S, char[][] Edges){ // Store all the adjacent nodes // of each node of a graph HashMap<Character, Set<Character>> G = new HashMap<>(); // Traverse Edges[][2] array for(int i = 0; i < M; i++) { if (G.containsKey(Edges[i][0])) { Set<Character> temp = G.get(Edges[i][0]); temp.add(Edges[i][1]); G.put(Edges[i][0], temp); } else { Set<Character> temp = new HashSet<>(); temp.add(Edges[i][1]); G.put(Edges[i][0], temp); } } // Check if a node is already visited or not HashMap<Character, Boolean> vis = new HashMap<>(); LexiDFS(G, S, vis);}// Driver codepublic static void main(String[] args) { int N = 10, M = 10; char S = 'a'; char[][] Edges = { { 'a', 'y' }, { 'a', 'z' }, { 'a', 'p' }, { 'p', 'c' }, { 'p', 'b' }, { 'y', 'm' }, { 'y', 'l' }, { 'z', 'h' }, { 'z', 'g' }, { 'z', 'i' } }; // Function Call CreateGraph(N, M, S, Edges);}}// This code is contributed by hritikrommie |
Python3
# Python3 program for the above approachG = [[] for i in range(300)]vis = [0 for i in range(300)]# Function to traverse the graph in# lexicographical order using DFSdef LexiDFS(S): global G, vis # Mark S as visited nodes vis[ord(S)] = 1 # Prvalue of visited nodes print (S,end=" ") # Traverse all adjacent nodes of S for i in G[ord(S)]: # If i is not visited if (not vis[i]): # Traverse all the nodes # which is connected to i LexiDFS(chr(i))# Utility Function to traverse graph# in lexicographical order of nodesdef CreateGraph(N, M, S, Edges): global G # Store all the adjacent nodes # of each node of a graph # Traverse Edges[][2] array for i in Edges: # Add the edges G[ord(i[0])].append(ord(i[1])) G[ord(i[0])] = sorted(G[ord(i[0])]) # Function Call LexiDFS(S)# Driver Codeif __name__ == '__main__': N = 10 M = 10 S = 'a' Edges=[ ['a', 'y' ],[ 'a', 'z' ], [ 'a', 'p' ],[ 'p', 'c' ], [ 'p', 'b' ],[ 'y', 'm' ], [ 'y', 'l' ],[ 'z', 'h' ], [ 'z', 'g' ],[ 'z', 'i' ] ] # Function Call CreateGraph(N, M, S, Edges);# This code is contributed by mohitkumar29. |
Javascript
<script>// JavaScript program for the above approachlet G = new Array(300).fill(0).map(() => [])let vis = new Array(300).fill(0)// Function to traverse the graph in// lexicographical order using DFSfunction LexiDFS(S) { // Mark S as visited nodes vis[S.charCodeAt(0)] = 1 // Prvalue of visited nodes document.write(S + " ") // Traverse all adjacent nodes of S for (let i of G[S.charCodeAt(0)]) { // If i is not visited if (!vis[i]) { // Traverse all the nodes // which is connected to i LexiDFS(String.fromCharCode(i)) } }}// Utility Function to traverse graph// in lexicographical order of nodesfunction CreateGraph(N, M, S, Edges) { // Store all the adjacent nodes // of each node of a graph // Traverse Edges[][2] array for (let i of Edges) { // Add the edges G[i[0].charCodeAt(0)].push(i[1].charCodeAt(0)) G[i[0].charCodeAt(0)] = G[i[0].charCodeAt(0)].sort((a, b) => a - b) } // Function Call LexiDFS(S)}// Driver Codelet N = 10let M = 10let S = 'a'let Edges = [['a', 'y'], ['a', 'z'],['a', 'p'], ['p', 'c'],['p', 'b'], ['y', 'm'],['y', 'l'], ['z', 'h'],['z', 'g'], ['z', 'i']]// Function CallCreateGraph(N, M, S, Edges);// This code is contributed by _saurabh_jaiswal</script> |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class Graph { // Function to traverse the graph in // lexicographical order using DFS static void LexiDFS(List<int>[] G, int S, bool[] vis) { // Mark S as visited nodes vis[S] = true; // Print value of visited nodes Console.Write(Convert.ToChar(S) + " "); // Traverse all adjacent nodes of S foreach (int i in G[S]) { // If i is not visited if (!vis[i]) { // Traverse all the nodes // which is connected to i LexiDFS(G, i, vis); } } } // Utility Function to traverse graph // in lexicographical order of nodes static void CreateGraph(int N, int M, char S, char[][] Edges) { // Store all the adjacent nodes // of each node of a graph List<int>[] G = new List<int>[300]; for (int i = 0; i < G.Length; i++) { G[i] = new List<int>(); } // Traverse Edges[][2] array for (int i = 0; i < M; i++) { // Add the edges G[Edges[i][0]].Add(Edges[i][1]); G[Edges[i][0]].Sort(); } // Check if a node is already visited or not bool[] vis = new bool[300]; LexiDFS(G, S, vis); } // Driver code static void Main(string[] args) { int N = 10; int M = 10; char S = 'a'; char[][] Edges = { new char[] { 'a', 'y' }, new char[] { 'a', 'z' }, new char[] { 'a', 'p' }, new char[] { 'p', 'c' }, new char[] { 'p', 'b' }, new char[] { 'y', 'm' }, new char[] { 'y', 'l' }, new char[] { 'z', 'h' }, new char[] { 'z', 'g' }, new char[] { 'z', 'i' } }; // Function Call CreateGraph(N, M, S, Edges); }}// This code is contributed by Jay |
Output:
a p b c y l m z g h i
Time Complexity: O(N * log(N))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
