Please enable JavaScript.

Coggle requires JavaScript to display documents.

Recorriendo un grafo, image, image, image, image, image, image, image,…

- - - - Concepto de la travesía de gráficos
      - Importancia en la teoría de grafos
    - - Encontrar ciclos en gráficos
        
        Dirigidos
        
        No dirigidos
      - Identificar componentes conectados en gráficos no dirigidos
        
        Concepto de componentes conectados
        
        Uso de BFS y DFS
- - - - Estructura y procedimiento de BFS
        
        Inicialización y marcado de vértices
        
        Uso de una cola para mantener vértices "grises"
        
        Rastreo de parent[v] para el vértice descubridor
        
        Registro de d[v] para medir la longitud de la ruta desde s hasta v
      - Ejemplo de BFS (para gráficos dirigidos)
        
        Pasos detallados de la ejecución de BFS
      - Propiedades de BFS
        
        Clasificación de las aristas
        
        Aristas de árbol
        
        Aristas no de árbol (aristas cruzadas y de retroceso)
        
        Significado de la BFS-tree
        
        Definición de árbol BFS
        
        Importancia de la estructura del árbol BFS
        
        Alcanzabilidad en grafos dirigidos
        
        Garantía de que BFS alcanza todos los vértices
        
        Componentes conectados en grafos no dirigidos
        
        Aplicación de BFS en la identificación de componentes conectados
      - Análisis del tiempo de ejecución de BFS
        
        Cálculo del tiempo de ejecución en grafos dirigidos y no dirigidos
    - - Estructura y procedimiento de DFS
        
        Inicialización y marcado de vértices
        
        Uso de una pila para mantener vértices "grises"
        
        Registro de los tiempos de inicio (d[u]) y finalización (f[u]) de la visita a un vértice
      - Ejemplo de DFS (para gráficos dirigidos)
        
        Pasos detallados de la ejecución de DFS
      - Propiedades de DFS
        
        Alcanzabilidad y el árbol DFS
        
        Demostración de que DFS alcanza todos los vértices
        
        Anidación de descendientes en el árbol DFS
        
        Relación entre los tiempos de inicio y finalización
      - Análisis del tiempo de ejecución de DFS
        
        Cálculo del tiempo de ejecución en grafos dirigidos y no dirigidos
        
        Diferencias entre el tiempo de ejecución de BFS y DFS