Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 112 vistas

    Estructura de Datos - Grafos

    Cargado por

    JimenaFagua
    Este documento describe los grafos y su implementación en Java. Explica que los grafos son una estructura de datos útil para el análisis de circuitos eléctricos, determinación de caminos más cortos, análisis de planificación de proyectos e identificación de compuestos químicos. También define los conceptos básicos de los grafos como vértices, aristas y representaciones como matrices de adyacencia y listas de adyacencia.

    Copyright:

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

    Estructura de Datos - Grafos

    Cargado por

    JimenaFagua
    112 vistas1 página
    Este documento describe los grafos y su implementación en Java. Explica que los grafos son una estructura de datos útil para el análisis de circuitos eléctricos, determinación de caminos más cortos, análisis de planificación de proyectos e identificación de compuestos químicos. También define los conceptos básicos de los grafos como vértices, aristas y representaciones como matrices de adyacencia y listas de adyacencia.

    Descripción original:

    QUE SON LOS GRAFOS EN PROGRAMACIÓN Y JAVA

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento describe los grafos y su implementación en Java. Explica que los grafos son una estructura de datos útil para el análisis de circuitos eléctricos, determinación de caminos más cortos, análisis de planificación de proyectos e identificación de compuestos químicos. También define los conceptos básicos de los grafos como vértices, aristas y representaciones como matrices de adyacencia y listas de adyacencia.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    112 vistas1 página

    Estructura de Datos - Grafos

    Cargado por

    JimenaFagua
    Este documento describe los grafos y su implementación en Java. Explica que los grafos son una estructura de datos útil para el análisis de circuitos eléctricos, determinación de caminos más cortos, análisis de planificación de proyectos e identificación de compuestos químicos. También define los conceptos básicos de los grafos como vértices, aristas y representaciones como matrices de adyacencia y listas de adyacencia.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    Está en la página 1de 1

    USOS

    GRAFOS Y SU Veamos algunos ejemplos donde la estructura


    de datos grafos puede ser muy útil :

    IMPLEMENTACIÓN Análisis de circuitos eléctricos.


    Determinación del camino más corto.

    EN JAVA Análisis de planificación de proyectos.


    Identificación de compuestos químicos.

    Entre muchos más, ya que grafos es la


    estructura matemática más usada.

    ¿QUE SON?

    Un grafo es un conjunto de puntos y un conjunto de líneas, cada una de las cuales une un punto con otro. Los puntos se llaman nodos o vértices
    de un grafo y las líneas se llaman aristas o arcos. Se representan el conjunto de vértices de un grafo dado G, por Vg, y el conjunto de arcos, por
    Ag.

    Un grafo, G, consiste de dos conjuntos V y E. V es un conjunto finito no vacio de vértices. E es un conjunto de pares de vértices. Estos pares
    de vértices se llaman arcos. V(G) y E(G) representan los conjuntos de vértices y arcos del grafo G. Para representar un grafo usaremos la
    notación G=(V,E).
    Un grafo, propiamente dicho, no acepta que un arco comience en un vértice y termine en el mismo vértice.
    Un grafo, propiamente dicho, no acepta que existan más de un arco entre dos vértices.

    TERMINOLOGÍA

    Según la conectividad Conceptos Básicos

    a. Componentes Conectados ( Connected Component ) a. Vértice ( Vertex )


    b. Fuertemente Conectado ( Strongly Connected ) b. Arco ( Edge )
    c. Cabeza ( Head )
    Conceptos vinculados al grado d. Cola ( Tail )
    e. Vértices Adjacentes ( Adjancent Edges )
    a. Grado de un Vértice ( Vertex Degree )
    b. Grado Entrante de un Vértice ( Vertex In Degree ) Según el tipo y cantidad de arcos
    c. Grado Saliente de un Vértice ( Vertex Out Degree )
    a. Grafo No Direccionado ( Undirected Graph )
    Conceptos vinculados al paso b. Grafo ( Graph )
    c. Grafo Completo ( Completed Graph )
    a. Paso ( Path ) d. Grafo Direccionado ( Directed Graph )
    b. Paso Simple ( Simple Path ) e. Digrafo ( Digraph )
    c. Paso Ciclo ( Cycle Path ) f. Digrafo Completo ( Completed Digraph )
    d. Longitud del Paso ( Path Length ) g. Multigrafo ( Multigraph )
    h. Subgrafo ( Subgraph )

    REPRESENTACIONES

    Matrices de Adyacencia ( Adjacency Matrices )


    Son matrices cuadradas de tantas filas y columnas como vértices tenga el grafo Multilistas de Adyacencia ( Adjacency
    a representar. En las celdas de la matriz se indica si existe un arco entre los Multilist )
    vértices que determinan la celda.
    Los nodos de una multilista de adyacencia tiene
    Listas de Adyacencia ( Adjacency Matrices ) enlaces a varias listas, hecho del cual proviene
    Partiendo de los nodos de cada vértice, evoluciona una lista que informa los su nombre. Esta representación se basa en que
    nodos que son adyacentes del inicial. existe un nodo, y solo uno, por cada arco,
    aunque este nodo enlace varias listas. La
    estructura del nodo es :
    +--------------------------------------------------+
    | M | v1 | v2 | Enlace por v1 | Enlace por v2 |
    +--------------------------------------------------+
    donde M es un campo de marcado, un bit, que
    puede ser usado para señalar, por ejemplo, que
    el arco fué visitado. Este nodo también podría
    tener campos para la información asociada a los
    arcos, como ocurre en los grafos ponderados,
    donde los arcos tienen un peso.

    REPRESENTACIÓN DE GRAFOS ORIENTADA A OBJETOS

    Las entidades que participan en un grafo son : los grafos, los vértices y los arcos. El siguiente bosquejo asocia a cada una de estas entidades con
    una clase, siendo estas clases capaces de producir ocurrencias de objetos de dichas clases.

    POR: Tania Figueredo y Jimena Fagua


    Fuente: Lecturas Complementarias GRAFOS Y SU IMPLEMENTACIÓN EN JAVA
    Estructura de Datos : Grafos - Fundamentos. (2018). Estructura de Datos : Grafos - Fundamentos.
    https://www.fceia.unr.edu.ar/estruc/2005/graffund.htm

    También podría gustarte