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 |
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!