Categoría: Graph Traversals

Encuentre un conjunto de como máximo N/2 Nodes de un gráfico de modo que todos los Nodes restantes estén conectados directamente a uno de los Nodes elegidos

Posted on by Rudeus Greyrat

Dado un número entero N , que representa el número de Nodes presentes en un gráfico no dirigido, con cada Node valorado de 1 a N, y una array 2D Edges[][] , que representa el par de vértices conectados por un borde, la tarea es encontrar un conjunto de como máximo N/2 Nodes tales que … Continue reading «Encuentre un conjunto de como máximo N/2 Nodes de un gráfico de modo que todos los Nodes restantes estén conectados directamente a uno de los Nodes elegidos»

Altura máxima de una elevación posible de modo que las celdas de array adyacentes tengan una diferencia de altura máxima de 1

Posted on by Rudeus Greyrat

Dada una array mat][][] de tamaño M x N que representa el mapa topográfico de una región, y 0 denota tierra y 1 denota elevación, la tarea es maximizar la altura en la array asignando a cada celda un valor no negativo. altura tal que la altura de una celda terrestre es 0 y dos … Continue reading «Altura máxima de una elevación posible de modo que las celdas de array adyacentes tengan una diferencia de altura máxima de 1»

Algoritmos | Gráficos transversales | Pregunta 12 – Part 5

Posted on by Rudeus Greyrat

Si el tiempo de terminación del DFS f[u] > f[v] para dos vértices u y v en un grafo dirigido G, y u y v están en el mismo árbol DFS en el bosque DFS, entonces u es un ancestro de v en el profundidad primer árbol. (Fuente http://courses.csail.mit.edu/6.006/oldquizzes/solutions/q2-f2007-sol.pdf ) (A) Verdadero (B) Falso Respuesta: … Continue reading «Algoritmos | Gráficos transversales | Pregunta 12 – Part 5»

Nodes con grado primo en un grafo no dirigido

Posted on by Rudeus Greyrat

Dado un grafo no dirigido con N vértices y M aristas, la tarea es imprimir todos los Nodes del grafo dado cuyo grado sea un Número Primo . Ejemplos:  Entrada: N = 4, arr[][] = { { 1, 2 }, { 1, 3 }, { 1, 4 }, { 2, 3 }, { 2, 4 … Continue reading «Nodes con grado primo en un grafo no dirigido»

Suma de todos los pares de caminos más cortos en un árbol

Posted on by Rudeus Greyrat

Dado un grafo no dirigido ponderado T que consta de Nodes valorados [0, N – 1] y una array Edges[][3] de tipo { u , v , w } que denota un borde entre los vértices u y v que tiene un peso w . La tarea es encontrar la suma de todos los pares … Continue reading «Suma de todos los pares de caminos más cortos en un árbol»

Encontrar si un Node X está presente en el subárbol de otro Node Y o viceversa para consultas Q

Posted on by Rudeus Greyrat

Dado un árbol con N Nodes y (N-1) aristas y el Node de origen está en la primera posición . Hay consultas Q , cada una del tipo {pos, X, Y} . Realice la siguiente operación según el tipo de consulta: Si pos = 0 , encuentre si Y está presente en el subárbol de … Continue reading «Encontrar si un Node X está presente en el subárbol de otro Node Y o viceversa para consultas Q»

Convertir lista de adyacencia en representación de array de adyacencia de un gráfico

Posted on by Rudeus Greyrat

Dada una representación de lista de adyacencia de un gráfico , la tarea es convertir la lista de adyacencia dada en una representación de array de adyacencia . Ejemplos:   Entrada: adjList[] = {{0 –> 1 –> 3}, {1 –> 2}, {2 –> 3}}  Salida:  0 1 0 1 0 0 1 0 0 0 0 … Continue reading «Convertir lista de adyacencia en representación de array de adyacencia de un gráfico»

Grado mínimo de tres Nodes formando un triángulo en un Gráfico dado

Posted on by Rudeus Greyrat

Dado un grafo no dirigido que consta de N vértices y M aristas y una array edge [][] , en la que cada fila representa dos vértices conectados por una arista, la tarea es encontrar el grado mínimo de tres Nodes que forman un triángulo en el gráfico . Si no existe ningún triángulo en … Continue reading «Grado mínimo de tres Nodes formando un triángulo en un Gráfico dado»

Algoritmos | Gráficos transversales | Pregunta 12 – Part 6

Posted on by Rudeus Greyrat

El algoritmo Breadth First Search se implementó utilizando la estructura de datos de la cola. Un orden posible para visitar los Nodes del siguiente gráfico es (A) MNOPQR (B) NQMPOR (C) QMNPRO (D) QMNPOR Respuesta: (C) Explicación: La opción (A) es MNOPQR. No puede ser un BFS ya que el recorrido comienza con M, pero … Continue reading «Algoritmos | Gráficos transversales | Pregunta 12 – Part 6»

Divide el gráfico dado en conjuntos bipartitos

Posted on by Rudeus Greyrat

Dado un gráfico G(V, E) , divídalo en dos conjuntos de manera que no haya dos vértices en un conjunto conectados directamente. Si no es posible, escriba «No posible». Ejemplos: Entrada: V = 7, E = 6,   Flanco = {{1, 2}, {2, 3}, {3, 4}, {3, 6}, {5, 6}, {6, 7}} Salida :  7 … Continue reading «Divide el gráfico dado en conjuntos bipartitos»