Dado un gráfico , G que consta de N Nodes, una fuente S y una array Edges[][2] de tipo {u, v} que denota que hay un borde no dirigido entre el Node u y v , la tarea es atravesar el graficar en orden lexicográfico usando DFS .
Ejemplos:
Entrada: N = 10, M = 10, S = ‘a’, Bordes[][2] = { { ‘a’, ‘y’ }, { ‘a’, ‘z’ }, { ‘a’, ‘ p’ }, { ‘p’, ‘c’ }, { ‘p’, ‘b’ }, { ‘y’, ‘m’ }, { ‘y’, ‘l’ }, { ‘z’, ‘ h’ }, { ‘z’, ‘g’ }, { ‘z’, ‘i’ } }
Salida: apbcylmzghiExplicación:
Para el primer nivel, visite el Node e imprímalo:
De manera similar, visitó el Node de segundo nivel p , que es lexicográficamente más pequeño como:
De manera similar visitó el tercer nivel para el Node p en orden lexicográfico como:
Ahora, el recorrido final se muestra en la imagen a continuación y se etiqueta como orden creciente de números:
Entrada: N = 6, S = ‘a’, Bordes[][2] = { { ‘a’, ‘e’ }, { ‘a’, ‘d’ }, { ‘e’, ’b’ }, { ‘e’, ’c’ }, { ‘d’, ‘f’ }, { ‘d’, ‘g’ } }
Salida: adfgebc
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice un mapa , diga G para almacenar todos los Nodes adyacentes de un Node según el orden lexicográfico de los Nodes.
- Inicialice un mapa , diga vis para verificar si un Node ya está atravesado o no.
- Recorra la array Edges[][2] y almacene todos los Nodes adyacentes de cada Node del gráfico en G .
- Finalmente, recorra el gráfico usando DFS e imprima los Nodes visitados del gráfico.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to traverse the graph in
// lexicographical order using DFS
void LexiDFS(map<char, set<char> >& G,
char S, map<char, bool>& vis)
{
// Mark S as visited nodes
vis[S] = true;
// Print value of visited nodes
cout << S << " ";
// Traverse all adjacent nodes of S
for (auto i = G[S].begin();
i != G[S].end(); i++) {
// If i is not visited
if (!vis[*i]) {
// Traverse all the nodes
// which is connected to i
LexiDFS(G, *i, vis);
}
}
}
// 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++) {
// Add the edges
G[Edges[i][0]].insert(
Edges[i][1]);
}
// Check if a node is already
// visited or not
map<char, bool> vis;
// Function Call
LexiDFS(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 for above approach
import java.util.*;
class Graph{
// Function to traverse the graph in
// lexicographical order using DFS
static void LexiDFS(HashMap<Character, Set<Character>> G,
char S, HashMap<Character, Boolean> vis)
{
// Mark S as visited nodes
vis.put(S, true);
// Print value of visited nodes
System.out.print(S + " ");
// Traverse all adjacent nodes of S
if (G.containsKey(S))
{
for(char i : G.get(S))
{
// If i is not visited
if (!vis.containsKey(i) || !vis.get(i))
{
// Traverse all the nodes
// which is connected to i
LexiDFS(G, i, vis);
}
}
}
}
// 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<>();
LexiDFS(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 for the above approach G = [[] for i in range(300)] vis = [0 for i in range(300)] # Function to traverse the graph in # lexicographical order using DFS def LexiDFS(S): global G, vis # Mark S as visited nodes vis[ord(S)] = 1 # Prvalue of visited nodes print (S,end=" ") # Traverse all adjacent nodes of S for i in G[ord(S)]: # If i is not visited if (not vis[i]): # Traverse all the nodes # which is connected to i LexiDFS(chr(i)) # Utility Function to traverse graph # in lexicographical order of nodes def CreateGraph(N, M, S, Edges): global G # Store all the adjacent nodes # of each node of a graph # Traverse Edges[][2] array for i in Edges: # Add the edges G[ord(i[0])].append(ord(i[1])) G[ord(i[0])] = sorted(G[ord(i[0])]) # Function Call LexiDFS(S) # Driver Code if __name__ == '__main__': N = 10 M = 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 mohitkumar29.
Javascript
<script>
// JavaScript program for the above approach
let G = new Array(300).fill(0).map(() => [])
let vis = new Array(300).fill(0)
// Function to traverse the graph in
// lexicographical order using DFS
function LexiDFS(S) {
// Mark S as visited nodes
vis[S.charCodeAt(0)] = 1
// Prvalue of visited nodes
document.write(S + " ")
// Traverse all adjacent nodes of S
for (let i of G[S.charCodeAt(0)]) {
// If i is not visited
if (!vis[i]) {
// Traverse all the nodes
// which is connected to i
LexiDFS(String.fromCharCode(i))
}
}
}
// 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
// Traverse Edges[][2] array
for (let i of Edges) {
// Add the edges
G[i[0].charCodeAt(0)].push(i[1].charCodeAt(0))
G[i[0].charCodeAt(0)] =
G[i[0].charCodeAt(0)].sort((a, b) => a - b)
}
// Function Call
LexiDFS(S)
}
// Driver Code
let N = 10
let M = 10
let S = 'a'
let 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 _saurabh_jaiswal
</script>
Producción:
a p b c y l m z g h i
Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(N)