Dado un grafo conexo con N vértices y M aristas . La tarea es imprimir el recorrido DFS lexicográficamente más pequeño del gráfico a partir de 1. Tenga en cuenta que los vértices están numerados de 1 a N . Ejemplos: Entrada: N = 5, M = 5, bordes[] = {{1, 4}, {3, 4}, {5, … Continue reading «Imprima el DFS lexicográficamente más pequeño del gráfico a partir de 1»
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 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»
¿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»
Hay n Nodes y m puentes entre estos Nodes. Imprima la ruta posible a través de cada Node usando cada borde (si es posible), viajando a través de cada borde solo una vez. Ejemplos: Input : [[0, 1, 0, 0, 1], [1, 0, 1, 1, 0], [0, 1, 0, 1, 0], [0, 1, 1, 0, … Continue reading «Caminos para recorrer cada Node usando cada borde (Siete Puentes de Königsberg)»
¿La siguiente declaración es verdadera/falsa? Si un DFS de un gráfico dirigido contiene un borde posterior, cualquier otro DFS del mismo gráfico también contendrá al menos un borde posterior. Fuente: http://courses.csail.mit.edu/6.006/oldquizzes/solutions/q2-s2009-sol.pdf (A) Verdadero (B) Falso Respuesta: (A) Explicación: Un borde posterior significa un ciclo en el gráfico . Entonces, si hay un ciclo, todos los … Continue reading «Algoritmos | Gráficos transversales | Pregunta 12 – Part 1»
El teorema de paréntesis se usa en DFS de gráfico . Establece que los descendientes en un árbol de búsqueda primero en profundidad tienen una propiedad interesante. Si v es un descendiente de u , entonces el tiempo de descubrimiento de v es posterior al tiempo de descubrimiento de u . En cualquier recorrido DFS de … Continue reading «Teorema de paréntesis»
Make es una utilidad que crea automáticamente bibliotecas y programas ejecutables a partir del código fuente mediante la lectura de archivos llamados makefiles que especifican cómo derivar el programa de destino. ¿Cuál de los siguientes algoritmos gráficos estándar utiliza Make. (A) Componentes fuertemente conectados (B) Ordenación topológica (C) Búsqueda primero en amplitud (D) Ruta más … Continue reading «Algoritmos | Gráficos transversales | Pregunta 9»
Dado un gráfico no dirigido que tiene N vértices y M aristas y cada vértice está asociado con un costo y se da un vértice fuente S. La tarea es encontrar la ruta de costo máximo desde el vértice de origen S de modo que no se visite ningún borde consecutivamente 2 o más veces. … Continue reading «Ruta de costo máximo en un gráfico no dirigido de modo que ningún borde se visite dos veces seguidas»
Dados dos vértices en un gráfico s y t, ¿cuál de los dos recorridos (BFS y DFS) se puede usar para encontrar si hay un camino de s a t? (A) Solo BFS (B) Solo DFS (C) Tanto BFS como DFS (D) Ni BFS ni DFS Respuesta: (C) Explicación: Podemos usar ambos recorridos para encontrar … Continue reading «Algoritmos | Gráficos transversales | Pregunta 8»