Given a connected graph with N vertices and M edges. The task is to print the lexicographically smallest DFS traversal of the graph starting from 1. Note that the vertices are numbered from 1 to N.
Examples:
Input: N = 5, M = 5, edges[] = {{1, 4}, {3, 4}, {5, 4}, {3, 2}, {1, 5}}
Output: 1 4 3 2 5
Input: N = 5, M = 8, edges[] = {{1, 4}, {3, 4}, {5, 4}, {3, 2}, {1, 5}, {1, 2}, {1, 3}, {3, 5}}
Output: 1 2 3 4 5
Approach: Instead of doing a normal DFS, first we have to sort the edges of each vertex, so that in each turn only the smallest edge is picked first. After sorting, just perform a normal DFS which will give the lexicographically smallest DFS traversal.
Below is the implementation of the above approach:
C++
// C++ program to find the lexicographically// smallest traversal of a graph#include <bits/stdc++.h>using namespace std;// Utility function to add an// edge to the graphvoid insertEdges(int u, int v, vector<int>* adj){ adj[u].push_back(v); adj[v].push_back(u);}// Function to perform DFS traversalvoid dfs(vector<int>* adj, int src, int n, bool* visited){ // Print current vertex cout << src << " "; // Mark it as visited visited[src] = true; // Iterate over all the edges connected // to this vertex for (int i = 0; i < adj[src].size(); i++) { // If this vertex is not visited, /// call dfs from this node if (!visited[adj[src][i]]) dfs(adj, adj[src][i], n, visited); }}// Function to print the lexicographically// smallest DFSvoid printLexoSmall(vector<int>* adj, int n){ // A boolean array to keep track of // nodes visited bool visited[n + 1] = { 0 }; // Sort the edges of each vertex in // ascending order for (int i = 0; i < n; i++) sort(adj[i].begin(), adj[i].end()); // Call DFS for (int i = 1; i < n; i++) { if (!visited[i]) dfs(adj, i, n, visited); }}// Driver codeint main(){ int n = 5, m = 5; vector<int> adj[n + 1]; insertEdges(1, 4, adj); insertEdges(3, 4, adj); insertEdges(5, 4, adj); insertEdges(3, 2, adj); insertEdges(1, 5, adj); insertEdges(1, 2, adj); insertEdges(3, 5, adj); insertEdges(1, 3, adj); printLexoSmall(adj, n); return 0;} |
Java
// Java program to find the lexicographically// smallest traversal of a graphimport java.util.*;class GFG{ static boolean visited[]; static Vector<Vector<Integer>> adj = new Vector<Vector<Integer>>(); // Utility function to add an// edge to the graphstatic void insertEdges(int u, int v){ adj.get(u).add(v); adj.get(v).add(u);}// Function to perform DFS traversalstatic void dfs( int src, int n){ // Print current vertex System.out.print( src + " "); // Mark it as visited visited[src] = true; // Iterate over all the edges connected // to this vertex for (int i = 0; i < adj.get(src).size(); i++) { // If this vertex is not visited, /// call dfs from this node if (!visited[adj.get(src).get(i)]) dfs( adj.get(src).get(i), n); }}// Function to print the lexicographically// smallest DFSstatic void printLexoSmall( int n){ // A boolean array to keep track of // nodes visited visited= new boolean[n + 1]; // Sort the edges of each vertex in // ascending order for (int i = 0; i < n; i++) Collections.sort(adj.get(i)); // Call DFS for (int i = 1; i < n; i++) { if (!visited[i]) dfs( i, n); }}// Driver codepublic static void main(String args[]){ int n = 5, m = 5; for(int i = 0; i < n + 1; i++) adj.add(new Vector<Integer>()); insertEdges(1, 4); insertEdges(3, 4); insertEdges(5, 4); insertEdges(3, 2); insertEdges(1, 5); insertEdges(1, 2); insertEdges(3, 5); insertEdges(1, 3); printLexoSmall( n);}}// This code is contributed by Arnab Kundu |
Python3
# Python3 program to find the lexicographically # smallest traversal of a graph # Utility function to add an edge# to the graph def insertEdges(u, v, adj): adj[u].append(v) adj[v].append(u) # Function to perform DFS traversal def dfs(adj, src, n, visited): # Print current vertex print(src, end = " ") # Mark it as visited visited[src] = True # Iterate over all the edges # connected to this vertex for i in range(0, len(adj[src])): # If this vertex is not visited, # call dfs from this node if not visited[adj[src][i]]: dfs(adj, adj[src][i], n, visited) # Function to print the lexicographically # smallest DFS def printLexoSmall(adj, n): # A boolean array to keep track # of nodes visited visited = [0] * (n + 1) # Sort the edges of each vertex # in ascending order for i in range(0, n): adj[i].sort() # Call DFS for i in range(1, n): if not visited[i]: dfs(adj, i, n, visited) # Driver code if __name__ == "__main__": n, m = 5, 5 adj = [[] for i in range(n + 1)] insertEdges(1, 4, adj) insertEdges(3, 4, adj) insertEdges(5, 4, adj) insertEdges(3, 2, adj) insertEdges(1, 5, adj) insertEdges(1, 2, adj) insertEdges(3, 5, adj) insertEdges(1, 3, adj) printLexoSmall(adj, n) # This code is contributed by Rituraj Jain |
C#
// C# program to find the lexicographically // smallest traversal of a graph using System;using System.Collections.Generic;class GFG{ public static bool[] visited; public static List<List<int>> adj = new List<List<int>>();// Utility function to add an // edge to the graph public static void insertEdges(int u, int v){ adj[u].Add(v); adj[v].Add(u);}// Function to perform DFS traversal public static void dfs(int src, int n){ // Print current vertex Console.Write(src + " "); // Mark it as visited visited[src] = true; // Iterate over all the edges connected // to this vertex for (int i = 0; i < adj[src].Count; i++) { // If this vertex is not visited, /// call dfs from this node if (!visited[adj[src][i]]) { dfs(adj[src][i], n); } }}// Function to print the lexicographically // smallest DFS public static void printLexoSmall(int n){ // A boolean array to keep track of // nodes visited visited = new bool[n + 1]; // Sort the edges of each vertex in // ascending order for (int i = 0; i < n; i++) { adj[i].Sort(); } // Call DFS for (int i = 1; i < n; i++) { if (!visited[i]) { dfs(i, n); } }}// Driver code public static void Main(string[] args){ int n = 5, m = 5; for (int i = 0; i < n + 1; i++) { adj.Add(new List<int>()); } insertEdges(1, 4); insertEdges(3, 4); insertEdges(5, 4); insertEdges(3, 2); insertEdges(1, 5); insertEdges(1, 2); insertEdges(3, 5); insertEdges(1, 3); printLexoSmall(n);}}// This code is contributed by shrikanth13 |
Javascript
<script>// Javascript program to find the lexicographically// smallest traversal of a graphlet visited;let adj =[] ;// Utility function to add an// edge to the graphfunction insertEdges(u,v){ adj[u].push(v); adj[v].push(u);}// Function to perform DFS traversalfunction dfs(src,n){ // Print current vertex document.write( src + " "); // Mark it as visited visited[src] = true; // Iterate over all the edges connected // to this vertex for (let i = 0; i < adj[src].length; i++) { // If this vertex is not visited, /// call dfs from this node if (!visited[adj[src][i]]) dfs( adj[src][i], n); }}// Function to print the lexicographically// smallest DFSfunction printLexoSmall(n){ // A boolean array to keep track of // nodes visited visited= new Array(n + 1); // Sort the edges of each vertex in // ascending order for (let i = 0; i < n; i++) adj[i].sort(function(a,b){return a-b;}); // Call DFS for (let i = 1; i < n; i++) { if (!visited[i]) dfs( i, n); }}// Driver codelet n = 5, m = 5; for(let i = 0; i < n + 1; i++) adj.push([]);insertEdges(1, 4);insertEdges(3, 4);insertEdges(5, 4);insertEdges(3, 2);insertEdges(1, 5);insertEdges(1, 2);insertEdges(3, 5);insertEdges(1, 3);printLexoSmall( n);// This code is contributed by avanitrachhadiya2155</script> |
Output:
1 2 3 4 5
Approach#2: Using DFS Algorithm with Priority Queue
This Approach builds a graph from the given edges, then performs a DFS traversal starting from node 1 using a priority queue to keep track of the lexicographically smallest path. The resulting path is returned as a list.
Algorithm
1. Build the adjacency list of the graph using the given edges.
2. Start the DFS from node 1 and push it into a priority queue.
3. While the priority queue is not empty, pop the node with the smallest value and visit it.
4. For each unvisited neighbor of the current node, push it into the priority queue.
5. Repeat steps 3-4 until all nodes are visited.
C++
#include<bits/stdc++.h>using namespace std;vector<vector<int>> build_graph(vector<vector<int>>& edges) { vector<vector<int>> graph(edges.size() + 1); for (auto& edge : edges) { graph[edge[0]].push_back(edge[1]); graph[edge[1]].push_back(edge[0]); } return graph;}vector<int> dfs(vector<vector<int>>& graph, int start) { set<int> visited; priority_queue<int, vector<int>, greater<int>> pq; vector<int> result; pq.push(start); while (!pq.empty()) { int node = pq.top(); pq.pop(); if (visited.count(node)) { continue; } visited.insert(node); result.push_back(node); for (auto& neighbor : graph[node]) { if (!visited.count(neighbor)) { pq.push(neighbor); } } } return result;}vector<int> lex_smallest_dfs(int n, int m, vector<vector<int>>& edges) { auto graph = build_graph(edges); return dfs(graph, 1);}int main() { int n = 5; int m = 5; vector<vector<int>> edges{{1, 4}, {3, 4}, {5, 4}, {3, 2}, {1, 5}}; auto result = lex_smallest_dfs(n, m, edges); for (auto& node : result) { cout << node << " "; } cout << endl; return 0;}// This code is contributed by Prajwal Kandekar |
Java
import java.util.*;public class Main { public static List<List<Integer> > buildGraph(List<List<Integer> > edges) { List<List<Integer> > graph = new ArrayList<>(edges.size() + 1); for (int i = 0; i < edges.size() + 1; i++) { graph.add(new ArrayList<Integer>()); } for (List<Integer> edge : edges) { int u = edge.get(0); int v = edge.get(1); graph.get(u).add(v); graph.get(v).add(u); } return graph; } public static List<Integer> dfs(List<List<Integer> > graph, int start) { Set<Integer> visited = new HashSet<>(); PriorityQueue<Integer> pq = new PriorityQueue<>( Comparator.comparingInt(a -> a)); List<Integer> result = new ArrayList<>(); pq.offer(start); while (!pq.isEmpty()) { int node = pq.poll(); if (visited.contains(node)) { continue; } visited.add(node); result.add(node); for (int neighbor : graph.get(node)) { if (!visited.contains(neighbor)) { pq.offer(neighbor); } } } return result; } public static List<Integer> lexSmallestDfs(int n, int m, List<List<Integer> > edges) { List<List<Integer> > graph = buildGraph(edges); return dfs(graph, 1); } public static void main(String[] args) { int n = 5; int m = 5; List<List<Integer> > edges = new ArrayList<>(); edges.add(Arrays.asList(1, 4)); edges.add(Arrays.asList(3, 4)); edges.add(Arrays.asList(5, 4)); edges.add(Arrays.asList(3, 2)); edges.add(Arrays.asList(1, 5)); List<Integer> result = lexSmallestDfs(n, m, edges); for (int node : result) { System.out.print(node + " "); } System.out.println(); }} |
Python3
import heapqdef build_graph(edges): graph = [[] for _ in range(len(edges)+1)] for a, b in edges: graph[a].append(b) graph[b].append(a) return graphdef dfs(graph, start): visited = set() pq = [start] result = [] while pq: node = heapq.heappop(pq) if node in visited: continue visited.add(node) result.append(node) for neighbor in graph[node]: if neighbor not in visited: heapq.heappush(pq, neighbor) return resultdef lex_smallest_dfs(n, m, edges): graph = build_graph(edges) return dfs(graph, 1)# Example usage:n = 5m = 5edges = [[1, 4], [3, 4], [5, 4], [3, 2], [1, 5]]print(lex_smallest_dfs(n, m, edges)) |
Javascript
function buildGraph(edges) { // create an empty array to hold graph nodes let graph = new Array(edges.length + 1).fill().map(() => []); for (let [u, v] of edges) {// add the edge to the graph (undirected, so add it in both directions) graph[u].push(v); graph[v].push(u); } return graph;}function dfs(graph, start) {// set to track visited nodes let visited = new Set(); // priority queue () to store nodes to be visited let pq = [start]; // list to store the result in the order of visitation let result = []; while (pq.length > 0) { // remove the node with the smallest label from the queue let node = pq.shift(); // if it's already been visited, skip it if (visited.has(node)) continue; // mark the node as visited visited.add(node); // add the node to the result list result.push(node); for (let neighbor of graph[node]) { if (!visited.has(neighbor)) pq.push(neighbor); } pq.sort((a, b) => a - b); // sort the priority queue } return result;}function lexSmallestDfs(n, m, edges) { let graph = buildGraph(edges); return dfs(graph, 1);}// Example usage:let n = 5;let m = 5;let edges = [[1, 4], [3, 4], [5, 4], [3, 2], [1, 5]];console.log(lexSmallestDfs(n, m, edges)); // output: [1, 4, 3, 2, 5] |
Output
[1, 4, 3, 2, 5]
Time Complexity: O(m log n) where m is the number of edges and n is the number of nodes in the graph.
Auxiliary Space: O(n+m)
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!
