Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 162 vistas

    TDA Grafo - Estructura No Lineal

    Cargado por

    ET
    Un grafo es una estructura de datos no lineal compuesta por un conjunto de vértices y aristas. Existen diferentes tipos de grafos como dirigidos, no dirigidos, valorados y no valorados. Un grafo se puede modelar como una pareja formada por un conjunto de vértices y uno de aristas. Algunos algoritmos para grafos incluyen recorridos en profundidad y anchura, y métodos para encontrar caminos más cortos como Dijkstra, Floyd y los árboles de recubrimiento mínimo de Prim y Kruskal.

    Copyright:

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

    TDA Grafo - Estructura No Lineal

    Cargado por

    ET
    162 vistas2 páginas
    Un grafo es una estructura de datos no lineal compuesta por un conjunto de vértices y aristas. Existen diferentes tipos de grafos como dirigidos, no dirigidos, valorados y no valorados. Un grafo se puede modelar como una pareja formada por un conjunto de vértices y uno de aristas. Algunos algoritmos para grafos incluyen recorridos en profundidad y anchura, y métodos para encontrar caminos más cortos como Dijkstra, Floyd y los árboles de recubrimiento mínimo de Prim y Kruskal.

    Descripción original:

    TDA Grafo - Estructura no lineal conceptos basicos

    Título original

    TDA Grafo - Estructura no lineal

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

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

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Un grafo es una estructura de datos no lineal compuesta por un conjunto de vértices y aristas. Existen diferentes tipos de grafos como dirigidos, no dirigidos, valorados y no valorados. Un grafo se puede modelar como una pareja formada por un conjunto de vértices y uno de aristas. Algunos algoritmos para grafos incluyen recorridos en profundidad y anchura, y métodos para encontrar caminos más cortos como Dijkstra, Floyd y los árboles de recubrimiento mínimo de Prim y Kruskal.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    162 vistas2 páginas

    TDA Grafo - Estructura No Lineal

    Cargado por

    ET
    Un grafo es una estructura de datos no lineal compuesta por un conjunto de vértices y aristas. Existen diferentes tipos de grafos como dirigidos, no dirigidos, valorados y no valorados. Un grafo se puede modelar como una pareja formada por un conjunto de vértices y uno de aristas. Algunos algoritmos para grafos incluyen recorridos en profundidad y anchura, y métodos para encontrar caminos más cortos como Dijkstra, Floyd y los árboles de recubrimiento mínimo de Prim y Kruskal.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    de 2

    Estructura de Datos no Lineales - Grafos

    Un Grafo es una estructura de datos no lineal. En principio puede considerarse como una dupla que
    contiene 2 conjuntos.
    Un grafo est compuesto por un conjunto de vrtices (o nodos) y un conjunto de aristas (arcos en
    los grafos dirigidos) que definen conexiones entre los vrtices. A partir de esta idea bsica, se
    definen distintos tipos de grafos:
    Dirigidos o no dirigidos. Segn que las aristas estn o no orientadas.
    Valorados y no valorados. Segn que las aristas tengan o no peso.
    Simples o multigrafos. Segn que se permita una o ms aristas entre dos vrtices.

    Un grafo se puede modelar como una pareja formada por un conjunto de vrtices y un conjunto de
    aristas:
    G = (V, A) V: conjunto de vrtices no vaco, finito
    A: conjunto de aristas o arcos finito. (puede ser vaco)
    Segn si el grafo est dirigido o no, A es una relacin o un conjunto de conjuntos de dos elementos.
    Tcnica de Implementacin:

    Recorrido de un Grafo:
    Recorrido en Profundidad (Depth First Search): Dado un Grafo G = (V, A) y un vrtice
    v, perteneciente a V, DFS recorre el grafo desde el primer adyacente no visitado de v.
    Recorrido en Ancho (Breadth First Search): Dado un Grafo G = (V, A) y un vrtice v,
    perteneciente a V, BFS recorre el grafo visitando primero todos los adyacentes de v.

    Ciclos en un Grafo:
    Ciclos simples: Un grafo tiene ciclos, si cuando lo recorremos por medio de un
    recorrido en profundidad partiendo de algn vrtice, podemos llegar al vrtice del que
    partimos. Ejemplo:

    Ciclo Hamiltoniano: Un grafo tiene ciclo hamiltoniano cuando lo recorremos por


    medio de un recorrido en profundidad partiendo de algn vrtice y podemos llegar al
    vrtice del que partimos pasando exactamente 1 vez por cada uno de los vrtices.
    Ejemplo:
    Ciclo Euleriano: Un grafo tiene ciclo Euleriano cuando lo recorremos por medio de un
    recorrido en profundidad partiendo de algn vrtice y podemos llegar al vrtice del que
    partimos pasando exactamente 1 vez por cada uno de los arcos, pudiendo pasar ms de
    una vez por cada vrtice. Ejemplo:

    Bsquedas de Caminos Ms Cortos:


    Algoritmo de Dijkstra: Devuelve un arreglo con los costos de los caminos mas cortos
    entre un vrtice v dado y el resto. Utiliza tcnica Greedy, incorporando un vrtice a un
    conjunto S cuya distancia al vrtice dado sea la mas corta posible. Ademas utiliza otro
    arreglo padre, donde se guarda el camino seguido para obtener el menor costo.
    Algoritmo de Floyd: Devuelve una Matriz A[N][N] con los costos de los caminos ms
    cortos entre todo par de vrtices, a partir de una matriz de costos C[N][N]. Donde
    C[i][j] es el costo de i j = j i, y C[i][i] = 0. Utiliza Programacin dinmica.
    rbol de Recubrimiento Mnimo: Dado un grafo conexo no dirigido G = (V, A), el
    problema es encontrar un grafo tal que la suma de los costos de las aristas sea mnima,
    y no queden vrtices sin conectar. Para esto se presentan 2 algoritmos.
    Algoritmo de Prim: Este algoritmo, utiliza un conjunto solucin S, donde ya estn los
    vrtices cuyo costo es mnimo, y un conjunto de vrtices V en el cual se encuentran
    todos los vrtices. La idea principal es, elegir un vrtice cualquiera de V, agregarlo a S,
    seleccionar un vrtice de V cuyo costo con cualquiera de los vrtices de S sea mnimo,
    y agregarlo al conjunto solucin hasta que me quede sin vrtices. Siempre teniendo en
    cuenta de no repetir vrtices.
    Algoritmo de Kruskal: Este algoritmo, utiliza un conjunto de aristas A donde se van
    guardando las aristas de mnimo costo, y una fila de aristas fila, en el cual se
    encuentran todas las aristas ordenadas ascendentemente segn costo. La idea principal
    es, elegir la arista de mnimo costo perteneciente a fila y agregarla a A, siempre que
    no se genere ciclo, hasta que la cantidad de aristas de A sea la cantidad de vertices -1.

    También podría gustarte