C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to traverse the graph in // lexicographical order using BFS void LexiBFS(map< char , set< char > >& G, char S, map< char , bool >& vis) { // Stores nodes of the graph // at each level queue< char > q; // Insert nodes of first level q.push(S); // Mark S as // visited node vis[S] = true ; // Traverse all nodes of the graph while (!q.empty()) { // Stores top node of queue char top = q.front(); // Print visited nodes of graph cout << top << " " ; // Insert all adjacent nodes // of the graph into queue for ( auto i = G[top].begin(); i != G[top].end(); i++) { // If i is not visited if (!vis[*i]) { // Mark i as visited node vis[*i] = true ; // Insert i into queue q.push(*i); } } // Pop top element of the queue q.pop(); } } // Utility Function to traverse graph // in lexicographical order of nodes void 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++) { G[Edges[i][0]].insert(Edges[i][1]); } // Check if a node is already visited or not map< char , bool > vis; LexiBFS(G, S, vis); } // Driver Code int 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 to implement // the above approach import java.util.*; class Graph{ // Function to traverse the graph in // lexicographical order using BFS static void LexiBFS(HashMap<Character, Set<Character>> G, char S, HashMap<Character, Boolean> vis) { // Stores nodes of the graph // at each level Queue<Character> q = new LinkedList<>(); // Insert nodes of first level q.add(S); // Mark S as // visited node vis.put(S, true ); // Traverse all nodes of the graph while (!q.isEmpty()) { // Stores top node of queue char top = q.peek(); // Print visited nodes of graph System.out.print(top + " " ); // Insert all adjacent nodes // of the graph into queue if (G.containsKey(top)) { for ( char i : G.get(top)) { // If i is not visited if (vis.containsKey(i)) { if (!vis.get(i)) { // Mark i as visited node vis.put(i, true ); // Insert i into queue q.add(i); } } else { // Mark i as visited node vis.put(i, true ); // Insert i into queue q.add(i); } } } // Pop top element of the queue q.remove(); } } // 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 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<>(); LexiBFS(G, S, vis); } // Driver code public 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 to implement # the above approach from collections import deque G = [[] for i in range ( 1000 )] vis = [ False for i in range ( 1000 )] # Function to traverse the graph in # lexicographical order using BFS def LexiBFS(S): global G, vis # Stores nodes of the graph # at each level q = deque() # Insert nodes of first level q.append( ord (S)) # Mark S as # visited node vis[ ord (S)] = True #a = [] # Traverse all nodes of the graph while ( len (q) > 0 ): # Stores top node of queue top = q.popleft() print ( chr (top), end = " " ) # Insert all adjacent nodes # of the graph into queue for i in G[top]: # If i is not visited if ( not vis[i]): #print(chr(i),end=" ") # Mark i as visited node vis[i] = True # Insert i into queue q.append(i) # Utility Function to traverse graph # in lexicographical order of nodes def CreateGraph(N, M, S,Edges): # Traverse Edges[][2] array for i in range (M): G[ ord (Edges[i][ 0 ])].append( ord (Edges[i][ 1 ])) for i in range ( 1000 ): G[i] = sorted (G[i]) LexiBFS(S) # Driver Code if __name__ = = '__main__' : N, M = 10 , 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 mohit kumar 29 |
Javascript
<script> // Javascript program to implement // the above approach // Function to traverse the graph in // lexicographical order using BFS function LexiBFS(G, S, vis) { // Stores nodes of the graph // at each level var q = []; // Insert nodes of first level q.push(S); // Mark S as // visited node vis.set(S, true ); // Traverse all nodes of the graph while (q.length != 0) { // Stores top node of queue var top = q[0]; // Print visited nodes of graph document.write( top + " " ); if (G.has(top)) { // Insert all adjacent nodes // of the graph into queue [...G.get(top)].sort().forEach(value => { // If i is not visited if (!vis.has(value)) { // Mark i as visited node vis.set(value, true ); // Insert i into queue q.push(value); } }); } // Pop top element of the queue q.shift(); } } // Utility Function to traverse graph // in lexicographical order of nodes function CreateGraph(N, M, S, Edges) { // Store all the adjacent nodes // of each node of a graph var G = new Map(); // Traverse Edges[][2] array for ( var i = 0; i < M; i++) { if (G.has(Edges[i][0])) { var tmp = G.get(Edges[i][0]); tmp.add(Edges[i][1]); G.set(Edges[i][0], tmp); } else { var tmp = new Set(); tmp.add(Edges[i][1]) G.set(Edges[i][0], tmp) } } // Check if a node is already visited or not var vis = new Map(); LexiBFS(G, S, vis); } // Driver Code var N = 10, M = 10, S = 'a' ; var 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 rutvik_56 </script> |
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; class Graph { // Function to traverse the graph in // lexicographical order using BFS static void LexiBFS(Dictionary< char , HashSet< char > > G, char S, Dictionary< char , bool > vis) { // Stores nodes of the graph // at each level Queue< char > q = new Queue< char >(); // Insert nodes of first level q.Enqueue(S); // Mark S as // visited node vis[S] = true ; // Traverse all nodes of the graph while (q.Count != 0) { // Stores top node of queue char top = q.Peek(); // Print visited nodes of graph Console.Write(top + " " ); // Insert all adjacent nodes // of the graph into queue if (G.ContainsKey(top)) { List< char > sortedAdjList = new List< char >(G[top]); sortedAdjList.Sort(); foreach ( char i in sortedAdjList) { // If i is not visited if (vis.ContainsKey(i)) { if (!vis[i]) { // Mark i as visited node vis[i] = true ; // Insert i into queue q.Enqueue(i); } } else { // Mark i as visited node vis[i] = true ; // Insert i into queue q.Enqueue(i); } } } // Pop top element of the queue q.Dequeue(); } } // 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 Dictionary< char , HashSet< char > > G = new Dictionary< char , HashSet< char > >(); // Traverse Edges[][2] array for ( int i = 0; i < M; i++) { char u = Edges[i, 0]; char v = Edges[i, 1]; if (G.ContainsKey(u)) { G[u].Add(v); } else { HashSet< char > temp = new HashSet< char >(); temp.Add(v); G[u] = temp; } if (!G.ContainsKey(v)) { G[v] = new HashSet< char >(); } } // Check if a node is already visited or not Dictionary< char , bool > vis = new Dictionary< char , bool >(); LexiBFS(G, S, vis); } // Driver code public static void Main() { 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 Prajwal Kandekar |
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!