El recorrido primero en amplitud (o búsqueda) para un gráfico es similar al recorrido primero en amplitud de un árbol (consulte el método 2 de esta publicación ). El único problema aquí es que, a diferencia de los árboles, los gráficos pueden contener ciclos, por lo que podemos volver al mismo Node. Para evitar … Continue reading «Búsqueda primero en amplitud o BFS para un gráfico»
Breadth-First Search: BFS, Breadth-First Search, es una técnica basada en vértices para encontrar la ruta más corta en el gráfico. Utiliza una estructura de datos de cola que sigue primero en entrar, primero en salir. En BFS, se selecciona un vértice a la vez cuando se visita y se marca, luego se visitan sus adyacentes … Continue reading «Diferencia entre BFS y DFS»
Dado un árbol con N Nodes numerados del 1 al N y una array de permutación de números del 1 al N. Compruebe si es posible obtener la array de permutación dada aplicando BFS (Breadth First Traversal) en el árbol dado. Nota: El recorrido siempre comenzará desde 1. Ejemplo: Entrada: arr[] = { 1 5 … Continue reading «Verifique si la permutación dada es un BFS válido de un árbol dado»
Dado un gráfico no dirigido, ¿cómo verificar si hay un ciclo en el gráfico? Ejemplo, Haga clic aquí para el curso completo! C++ // A C++ Program to detect // cycle in an undirected graph #include <iostream> #include <limits.h> #include <list> using namespace std; // Class for an undirected graph class Graph { … Continue reading «Detectar ciclo en un gráfico no dirigido»
Dado un gráfico donde cada borde tiene peso como 0 o 1. También se proporciona un vértice fuente en el gráfico. Encuentre la ruta más corta desde el vértice de origen hasta todos los demás vértices. Ejemplo: Input : Source Vertex = 0 and below graph Output : Shortest distances from given source 0 0 1 … Continue reading «0-1 BFS (ruta más corta en un gráfico de peso binario)»
Dado un árbol genérico que consta de N Nodes y (N – 1) aristas y una array de consultas consulta[] de tamaño Q que consta del tipo {A, B} , la tarea de cada consulta es verificar si la longitud de la ruta entre dos dados los Nodes A y B es par o impar. … Continue reading «Encuentre si la longitud de la ruta es par o impar entre los Nodes de árbol dados para consultas Q»
Dada una array arr[] de N enteros positivos y dos enteros positivos S y K , la tarea es alcanzar la posición de la array cuyo valor es K del índice S . Solo podemos pasar del índice actual i al índice (i + arr[i]) o (i – arr[i]) . Si hay una forma de … Continue reading «Compruebe si es posible llegar al índice con el valor K cuando se proporciona el índice de inicio»
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 … Continue reading «Imprima el BFS lexicográficamente más pequeño del gráfico a partir de 1»
Dada una array grid[][] de dimensiones M * N , tres enteros X, Y y K , la tarea es verificar si existe algún camino desde la celda (X, Y) a cualquier celda límite de la array tal que la suma de los elementos de la array presentes en el camino es como máximo K … Continue reading «Verifique si existe una ruta desde una celda dada a cualquier elemento límite de Matrix con una suma de elementos que no exceda K»
¿Cómo diseñaría las estructuras de datos para una red social muy grande como Facebook o Linkedln? Describa cómo diseñaría un algoritmo para mostrar el camino más corto entre dos personas (p. ej., Yo-> Bob-> Susan-> Jason-> Usted). Preguntado en: entrevista de Google Una buena forma de abordar este problema es eliminar algunas de las restricciones y … Continue reading «Diseñe estructuras de datos para una red social muy grande como Facebook o Linkedln»