Traversal of a Graph in lexicographical order using BFS
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to traverse the graph in// lexicographical order using BFSvoid 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 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++) { 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 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 to implement// the above approachimport java.util.*;class Graph{// Function to traverse the graph in// lexicographical order using BFSstatic 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 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<>(); LexiBFS(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 to implement# the above approachfrom collections import dequeG = [[] for i in range(1000)]vis = [False for i in range(1000)]# Function to traverse the graph in# lexicographical order using BFSdef 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 nodesdef 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 Codeif __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 BFSfunction 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 nodesfunction 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 Codevar 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 CallCreateGraph(N, M, S, Edges);// This code is contributed by rutvik_56</script> |
C#
// C# program to implement// the above approachusing 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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
