Dado un árbol n-ario T , la tarea es encontrar un Node cuya eliminación minimice el tamaño máximo de todos los bosques ( componentes conectados ) generados. Ejemplos: Entrada: 1 / | \ … Continue reading «Node cuya eliminación minimiza el tamaño máximo del bosque de un árbol N-ario»
Dado el Node raíz de un árbol N-ario y un número entero K , la tarea es convertir el árbol dado en una representación de lista de adyacencia e imprimir el recorrido de orden de niveles considerando el vértice K como el Node raíz. Ejemplo: Entrada: Árbol en la imagen de abajo, K = 5 … Continue reading «Recorrido de orden de nivel al convertir N-ary Tree en una representación de lista de adyacencia con K como Node raíz»
Dado un gráfico dirigido y ponderado G , una array V[] que consta de vértices, la tarea es encontrar la ruta de costo mínimo que pasa por todos los vértices del conjunto V , desde una fuente S dada hasta un destino D . Ejemplos: Entrada: V = {7}, S = 0, D = 6 … Continue reading «Ruta de costo mínimo en un gráfico dirigido a través de un conjunto dado de Nodes intermedios»
Dado un grafo dirigido de N vértices y M aristas, la tarea es encontrar el número mínimo de aristas necesarias para hacer que el grafo dado sea fuertemente conectado . Ejemplos: Entrada: N = 3, M = 3, origen[] = {1, 2, 1}, destino[] = {2, 3, 3} Salida: 1 Explicación: Agregar un borde dirigido … Continue reading «Bordes mínimos requeridos para hacer un gráfico dirigido fuertemente conectado»
El recorrido de un gráfico es diferente del árbol porque (A) Puede haber un bucle en el gráfico, por lo que debemos mantener una marca visitada para cada vértice (B) El DFS de un gráfico usa la pila, pero en orden el recorrido de un árbol es recursivo (C) El BFS de un gráfico usa … Continue reading «Algoritmos | Gráficos transversales | Pregunta 2»
Dado un gráfico dirigido de N vértices valorados de 0 a N – 1 y el gráfico de array [] de tamaño K representa la lista de adyacencia del gráfico dado , la tarea es contar todos los caminos hamiltonianos que comienzan en el vértice 0 y finalizan en el (N – 1) vértice . … Continue reading «Cuente todos los caminos hamiltonianos en un gráfico dirigido dado»
Dado un gráfico acíclico dirigido que tiene V vértices y E aristas, donde cada arista {U, V} representa los trabajos U y V , de modo que el trabajo V solo puede iniciarse después de completar el trabajo U. La tarea es determinar el tiempo mínimo que tarda cada trabajo en completarse, donde cada trabajo … Continue reading «Tiempo mínimo que tarda cada trabajo en completarse dado por un gráfico acíclico dirigido»
Dado un gráfico acíclico conectado que consta de vértices V y aristas E , un vértice de origen src y un vértice de destino dest , la tarea es contar el número de vértices entre el origen y el vértice de destino dados en el gráfico. Ejemplos : Entrada: V = 8, E = 7, … Continue reading «Calcule el número de Nodes entre dos vértices en un gráfico acíclico mediante el método DFS»
¿Cuáles son las estructuras de datos apropiadas para los siguientes algoritmos? 1) Breadth First Search 2) Depth First Search 3) Prim’s Minimum Spanning Tree 4) Kruskal’ Minimum Spanning Tree … Continue reading «Algoritmos | Gráficos transversales | Pregunta 12»
Dado un gráfico ponderado dirigido que consta de N vértices y una array Edges[][] , donde cada fila representa dos vértices conectados por un borde y el peso de ese borde, la tarea es encontrar la ruta con la suma máxima de pesos de un vértice de origen dado src a un vértice de destino … Continue reading «Ruta de costo máximo desde el Node de origen hasta el Node de destino a través de un máximo de K Nodes intermedios»