Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 29 vistas

    OT - Kahn

    Cargado por

    Horacio Abalos

    Copyright:

    © All Rights Reserved
    Descargue como PPTX, PDF, TXT o lea en línea desde Scribd

    OT - Kahn

    Cargado por

    Horacio Abalos
    29 vistas10 páginas

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PPTX, PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Copyright:

    © All Rights Reserved
    Descargue como PPTX, PDF, TXT o lea en línea desde Scribd
    Descargar como pptx, pdf o txt
    29 vistas10 páginas

    OT - Kahn

    Cargado por

    Horacio Abalos

    Copyright:

    © All Rights Reserved
    Descargue como PPTX, PDF, TXT o lea en línea desde Scribd
    Descargar como pptx, pdf o txt
    de 10

    Orden Topológico

    Ordenación Topológica
    ● Es una forma de ordenar linealmente los vértices de manera que sea
    fácilmente observable la relación de dependencia
    ● Por ejemplo, una ordenación topológica del siguiente grafo puede ser 5, 4, 2,
    3, 1, 0
    ● Es útil para resolver problemas que presentan dependencias entre elementos
    (Tarea 1 debe ser ejecutada antes que Tarea 2)
    ● Se aplica a grafos dirigidos y acíclicos
    ○ Si existe un ciclo no se puede obtener un orden topológico
    ● Un grafo puede tener varias Ordenaciones Topológicas
    ● Se basa en el concepto de grado de entrada (inDegree)
    Determinar una Ordenación Topológica
    Determinar una Ordenación Topológica
    Ejemplos de uso
    Grado de entrada
    ● El grado de entrada de un vértice es la cantidad de vértices de los cuales es
    adyacente.
    ● Representa “la cantidad de flechas que llegan al vértice”

    Vértice Grado de entrada

    M 2

    E 1

    B 1

    L 2

    P 0
    Pseudocódigo
    Encontrar nodos sin aristas entrantes
    Agregar al conjunto S los nodos que tengan grado de entrada 0
    Mientras S no esté vacío
    Elegir un nodo N de S
    Proceso el nodo, añadirlo a la lista L de retorno
    Para cada adyacente A de N (decrementar el grado de entrada a los vecinos)
    Si el grado de A es 0
    Añadirlo a S
    Si todas las aristas se procesaron L es el orden topológico
    Observaciones
    ● Los elementos de S son los que están disponibles para ser procesados
    ○ tienen grado de entrada 0
    ● S puede ser cualquier cosa desde que no afecte el orden de ejecución
    ○ Nos interesa agregar y quitar elementos de S en orden 1
    ○ Pila o Cola resuelve el problema
    ○ Lista también
    ● En general, no me interesa el orden en que los elementos de S son procesados
    ● L es el resultado del orden topológico basado en la implementación elegida, no es única
    ● El costo de procesar un vértice es
    ○ |A| de ese vertice, si el grafo está implementado con LA
    ○ V si está implementado con MA
    ● Una forma de ver si se ejecutó bien es dibujar el grafo resultante y observar que todas las
    aristas tengan la misma dirección
    ● Visualizador
    ¿Qué pasa con los ciclos?
    ● Ver ejemplo

    Observaciones
    ● Si al finalizar la ejecución de OT el largo de L (lista retorno) es menor que V,
    entonces hay ciclo(s)
    ● Algoritmo de Kahn
    ● Es una manera de saber si el grafo tiene ciclos con O(V + A) -> buen orden!
    Links
    ● Visualizador
    ● Geeksforgeeks

    También podría gustarte