Dado un grafo conexo con N vértices y M aristas. La tarea es imprimir el recorrido BFS lexicográficamente más pequeño del gráfico a partir de 1.
Nota : Los vértices están numerados del 1 al N.
Ejemplos:
Input: N = 5, M = 5
Edges:
1 4
3 4
5 4
3 2
1 5
Output: 1 4 3 2 5
Start from 1, go to 4, then to 3 and then to 2 and to 5.
Input: N = 3, M = 2
Edges:
1 2
1 3
Output: 1 2 3
Enfoque: en lugar de hacer un recorrido BFS normal en el gráfico, podemos usar una cola de prioridad (min-heap) en lugar de una cola simple. Cuando se visita un Node, agregue sus Nodes adyacentes a la cola de prioridad. Cada vez que visitemos un nuevo Node, será el que tenga el índice más pequeño en la cola de prioridad. Imprima los Nodes cada vez que los visitemos a partir de 1.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ program to print the lexcicographically
// smallest path starting from 1
#include <bits/stdc++.h>
using namespace std;
// Function to print the smallest lexicographically
// BFS path starting from 1
void printLexoSmall(vector<int> adj[], int n)
{
// Visited array
bool vis[n + 1];
memset(vis, 0, sizeof vis);
// Minimum Heap
priority_queue<int, vector<int>, greater<int> > Q;
// First one visited
vis[1] = true;
Q.push(1);
// Iterate till all nodes are visited
while (!Q.empty()) {
// Get the top element
int now = Q.top();
// Pop the element
Q.pop();
// Print the current node
cout << now << " ";
// Find adjacent nodes
for (auto p : adj[now]) {
// If not visited
if (!vis[p]) {
// Push
Q.push(p);
// Mark as visited
vis[p] = true;
}
}
}
}
// Function to insert edges in the graph
void insertEdges(int u, int v, vector<int> adj[])
{
adj[u].push_back(v);
adj[v].push_back(u);
}
// Driver Code
int main()
{
int n = 5, m = 5;
vector<int> adj[n + 1];
// Insert edges
insertEdges(1, 4, adj);
insertEdges(3, 4, adj);
insertEdges(5, 4, adj);
insertEdges(3, 2, adj);
insertEdges(1, 5, adj);
// Function call
printLexoSmall(adj, n);
return 0;
}
Java
// Java program to print the lexcicographically
// smallest path starting from 1
import java.util.*;
public class GFG
{
// Function to print the smallest lexicographically
// BFS path starting from 1
static void printLexoSmall(Vector<Vector<Integer>> adj, int n)
{
// Visited array
boolean[] vis = new boolean[n + 1];
// Minimum Heap
Vector<Integer> Q = new Vector<Integer>();
// First one visited
vis[1] = true;
Q.add(1);
// Iterate till all nodes are visited
while (Q.size() > 0) {
// Get the top element
int now = Q.get(0);
// Pop the element
Q.remove(0);
// Print the current node
System.out.print(now + " ");
// Find adjacent nodes
for(int p : adj.get(now)) {
// If not visited
if (!vis[p]) {
// Push
Q.add(p);
Collections.sort(Q);
// Mark as visited
vis[p] = true;
}
}
}
}
// Function to insert edges in the graph
static void insertEdges(int u, int v, Vector<Vector<Integer>> adj)
{
adj.get(u).add(v);
adj.get(v).add(u);
}
// Driver code
public static void main(String[] args) {
int n = 5;
Vector<Vector<Integer>> adj = new Vector<Vector<Integer>>();
for(int i = 0; i < n + 1; i++)
{
adj.add(new Vector<Integer>());
}
// Insert edges
insertEdges(1, 4, adj);
insertEdges(3, 4, adj);
insertEdges(5, 4, adj);
insertEdges(3, 2, adj);
insertEdges(1, 5, adj);
// Function call
printLexoSmall(adj, n);
}
}
// This code is contributed by divyeshrabadiya07.
Python3
# Python program to print the lexcicographically # smallest path starting from 1 # Function to print the smallest lexicographically # BFS path starting from 1 def printLexoSmall(adj, n): # Visited array vis = [False for i in range(n + 1)] # Minimum Heap Q = [] # First one visited vis[1] = True; Q.append(1) # Iterate till all nodes are visited while(len(Q) != 0): # Get the top element now = Q[0] # Pop the element Q.pop(0) # Print the current node print(now, end = " ") # Find adjacent nodes for p in adj[now]: # If not visited if(not vis[p]): # Push Q.append(p) Q.sort() # Mark as visited vis[p] = True # Function to insert edges in the graph def insertEdges(u, v, adj): adj[u].append(v) adj[v].append(u) # Driver code n = 5 m = 5 adj = [[] for i in range(n + 1)] # Insert edges insertEdges(1, 4, adj) insertEdges(3, 4, adj) insertEdges(5, 4, adj) insertEdges(3, 2, adj) insertEdges(1, 5, adj) # Function call printLexoSmall(adj, n) # This code is contributed by avanitrachhadiya2155
C#
// C# program to print the lexcicographically
// smallest path starting from 1
using System;
using System.Collections.Generic;
class GFG {
// Function to print the smallest lexicographically
// BFS path starting from 1
static void printLexoSmall(List<List<int>> adj, int n)
{
// Visited array
bool[] vis = new bool[n + 1];
// Minimum Heap
List<int> Q = new List<int>();
// First one visited
vis[1] = true;
Q.Add(1);
// Iterate till all nodes are visited
while (Q.Count > 0) {
// Get the top element
int now = Q[0];
// Pop the element
Q.RemoveAt(0);
// Print the current node
Console.Write(now + " ");
// Find adjacent nodes
foreach (int p in adj[now]) {
// If not visited
if (!vis[p]) {
// Push
Q.Add(p);
Q.Sort();
// Mark as visited
vis[p] = true;
}
}
}
}
// Function to insert edges in the graph
static void insertEdges(int u, int v, List<List<int>> adj)
{
adj[u].Add(v);
adj[v].Add(u);
}
// Driver code
static void Main()
{
int n = 5;
List<List<int>> adj = new List<List<int>>();
for(int i = 0; i < n + 1; i++)
{
adj.Add(new List<int>());
}
// Insert edges
insertEdges(1, 4, adj);
insertEdges(3, 4, adj);
insertEdges(5, 4, adj);
insertEdges(3, 2, adj);
insertEdges(1, 5, adj);
// Function call
printLexoSmall(adj, n);
}
}
// This code is contributed by divyesh072019.
Javascript
<script>
// JavaScript program to print the lexcicographically
// smallest path starting from 1
// Function to print the smallest lexicographically
// BFS path starting from 1
function printLexoSmall(adj,n)
{
// Visited array
let vis = new Array(n + 1);
for(let i=0;i<n+1;i++)
{
vis[i]=false;
}
// Minimum Heap
let Q = [];
// First one visited
vis[1] = true;
Q.push(1);
// Iterate till all nodes are visited
while (Q.length > 0) {
// Get the top element
let now = Q[0];
// Pop the element
Q.shift();
// Print the current node
document.write(now + " ");
// Find adjacent nodes
for(let p=0;p< adj[now].length;p++) {
// If not visited
if (!vis[adj[now][p]]) {
// Push
Q.push(adj[now][p]);
Q.sort(function(a,b){return a-b;});
// Mark as visited
vis[adj[now][p]] = true;
}
}
}
}
// Function to insert edges in the graph
function insertEdges(u,v,adj)
{
adj[u].push(v);
adj[v].push(u);
}
n = 5;
let adj = [];
for(let i = 0; i < n + 1; i++)
{
adj.push([]);
}
// Insert edges
insertEdges(1, 4, adj);
insertEdges(3, 4, adj);
insertEdges(5, 4, adj);
insertEdges(3, 2, adj);
insertEdges(1, 5, adj);
// Function call
printLexoSmall(adj, n);
// This code is contributed by ab2127
</script>
Producción:
1 4 3 2 5
Complejidad de tiempo: O (N * logN), ya que estamos usando un bucle para atravesar N veces y en cada recorrido, estamos haciendo una operación de cola de prioridad que costará logN tiempo. Donde N es el número total de Nodes en el árbol.
Espacio auxiliar: O(N), ya que estamos usando espacio adicional para vis y cola de prioridad.