Topological Sorting – Página 2

Clasificación topológica de un gráfico utilizando el tiempo de salida del vértice

julio 5, 2022 Rudeus Greyrat

Dado un gráfico acíclico dirigido (DAG), encuentre la ordenación topológica del gráfico. La ordenación topológica para el gráfico acíclico dirigido (DAG) es una ordenación lineal de vértices tal que para cada arista dirigida uv, el vértice u viene antes que v en la ordenación. La clasificación topológica de un gráfico no es posible si el … Continue reading «Clasificación topológica de un gráfico utilizando el tiempo de salida del vértice»

Ordenamiento topológico lexicográficamente más pequeño

julio 5, 2022 Rudeus Greyrat

Dado un grafo dirigido con N vértices y M aristas que pueden contener ciclos, la tarea es encontrar el ordenamiento topológico lexicográficamente más pequeño del grafo si existe; de lo contrario, imprima -1 (si el grafo tiene ciclos). El ordenamiento topológico lexigráficamente más pequeño significa que si dos vértices en un gráfico no tienen ningún borde … Continue reading «Ordenamiento topológico lexicográficamente más pequeño»

ruta más larga en un gráfico acíclico dirigido | conjunto 2

julio 5, 2022 Rudeus Greyrat

Dado un gráfico acíclico dirigido ponderado (DAG) y un vértice de origen en él, encuentre las distancias más largas desde el vértice de origen hasta todos los demás vértices en el gráfico dado. Ya hemos discutido cómo podemos encontrar la ruta más larga en el gráfico acíclico dirigido (DAG) en el Conjunto 1. En esta … Continue reading «ruta más larga en un gráfico acíclico dirigido | conjunto 2»

Detectar ciclo en gráfico dirigido usando clasificación topológica

julio 5, 2022 Rudeus Greyrat

Dado un grafo dirigido que consta de N vértices y M aristas y un conjunto de Aristas[][] , la tarea es comprobar si el grafo contiene un ciclo o no utilizando la ordenación topológica . El tipo topológico de gráfico dirigido es una ordenación lineal de sus vértices, de modo que, para cada borde dirigido … Continue reading «Detectar ciclo en gráfico dirigido usando clasificación topológica»

Algoritmo de Kahn para clasificación topológica

julio 5, 2022 Rudeus Greyrat

La ordenación topológica para un gráfico cíclico dirigido ( DAG ) es una ordenación lineal de vértices tal que para cada arista dirigida uv, el vértice u viene antes que v en la ordenación. La clasificación topológica de un gráfico no es posible si el gráfico no es un DAG. Por ejemplo, una ordenación topológica … Continue reading «Algoritmo de Kahn para clasificación topológica»

Verifique si la array dada se puede construir de forma única a partir del conjunto dado de subsecuencias

julio 5, 2022 Rudeus Greyrat

Dada una array de elementos distintos y una lista de secuencias de subsecuencias de la array, la tarea es verificar si la array dada se puede construir de manera única a partir del conjunto dado de subsecuencias. Ejemplos: Entrada: arr[] = {1, 2, 3, 4}, seqs[][] = {{1, 2}, {2, 3}, {3, 4}} Salida: Sí … Continue reading «Verifique si la array dada se puede construir de forma única a partir del conjunto dado de subsecuencias»

Los 10 mejores algoritmos y estructuras de datos para la programación competitiva

julio 5, 2022 Rudeus Greyrat

En esta publicación, discutiremos los 10 algoritmos y estructuras de datos más importantes para la codificación competitiva. Temas: Algoritmos gráficos Programación dinámica Buscando y Ordenando: Teoría de Números y Otras Matemáticas Algoritmos de flujo geométrico y de red Estructuras de datos Los enlaces a continuación cubren los algoritmos más importantes y los temas de … Continue reading «Los 10 mejores algoritmos y estructuras de datos para la programación competitiva»

Programación serial equivalente de conflicto Programación serializable en DBMS

julio 5, 2022 Rudeus Greyrat

Requisito previo: serialización de conflictos, gráfico de precedencia Programación serializable en conflicto: una programación se denomina serializable en conflicto si se puede transformar en una programación en serie mediante el intercambio de operaciones que no están en conflicto. El programa de serie del Programa serializable de conflicto se puede encontrar aplicando la ordenación topológica en … Continue reading «Programación serial equivalente de conflicto Programación serializable en DBMS»

Detectar ciclo en un gráfico dirigido usando BFS

julio 5, 2022 Rudeus Greyrat

Dado un gráfico dirigido, compruebe si el gráfico contiene un ciclo o no. Su función debería devolver verdadero si el gráfico dado contiene al menos un ciclo, de lo contrario devolverá falso. Por ejemplo, el siguiente gráfico contiene dos ciclos 0->1->2->3->0 y 2->4->2, por lo que su función debe devolver verdadero. Hemos discutido una solución … Continue reading «Detectar ciclo en un gráfico dirigido usando BFS»

Encuentra el orden de las tareas de las dependencias dadas

julio 5, 2022 Rudeus Greyrat

Hay un total de n tareas que debe elegir, etiquetadas de 0 a n-1. Algunas tareas pueden tener tareas de requisitos previos, por ejemplo, para elegir la tarea 0, primero debe terminar la tarea 1, que se expresa como un par: [0, 1] Dada la cantidad total de tareas y una lista de pares de … Continue reading «Encuentra el orden de las tareas de las dependencias dadas»