Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 88 vistas

    Grafos en C

    Cargado por

    JuanPa Santander
    Un grafo es una representación matemática de objetos como redes y circuitos que consiste en vértices y aristas. Los grafos se usan comúnmente en computación para resolver problemas complejos. Existen dos tipos principales de grafos: dirigidos y no dirigidos. El algoritmo de Dijkstra encuentra el camino más corto entre dos vértices en un grafo dirigido usando una estrategia greedy en etapas.

    Copyright:

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

    Grafos en C

    Cargado por

    JuanPa Santander
    88 vistas5 páginas
    Un grafo es una representación matemática de objetos como redes y circuitos que consiste en vértices y aristas. Los grafos se usan comúnmente en computación para resolver problemas complejos. Existen dos tipos principales de grafos: dirigidos y no dirigidos. El algoritmo de Dijkstra encuentra el camino más corto entre dos vértices en un grafo dirigido usando una estrategia greedy en etapas.

    Descripción original:

    Como se forma y emplean los grafos en c

    Título original

    grafos en c

    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 representación matemática de objetos como redes y circuitos que consiste en vértices y aristas. Los grafos se usan comúnmente en computación para resolver problemas complejos. Existen dos tipos principales de grafos: dirigidos y no dirigidos. El algoritmo de Dijkstra encuentra el camino más corto entre dos vértices en un grafo dirigido usando una estrategia greedy en etapas.

    Copyright:

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

    Grafos en C

    Cargado por

    JuanPa Santander
    Un grafo es una representación matemática de objetos como redes y circuitos que consiste en vértices y aristas. Los grafos se usan comúnmente en computación para resolver problemas complejos. Existen dos tipos principales de grafos: dirigidos y no dirigidos. El algoritmo de Dijkstra encuentra el camino más corto entre dos vértices en un grafo dirigido usando una estrategia greedy en etapas.

    Copyright:

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

    Un grafo es un objeto matemtico que se utiliza para representar circuitos, redes, etc.

    Los grafos son muy utilizados en computacin, ya que permiten resolver problemas
    muy complejos.

    Imaginemos que disponemos de una serie de ciudades y de carreteras que las unen.
    De cada ciudad saldrn varias carreteras, por lo que para ir de una ciudad a otra se
    podrn tomar diversos caminos. Cada carretera tendr un coste asociado (por ejemplo,
    la longitud de la misma). Gracias a la representacin por grafos podremos elegir el
    camino ms corto que conecta dos ciudades, determinar si es posible llegar de una
    ciudad a otra, si desde cualquier ciudad existe un camino que llegue a cualquier otra,
    etc.

    Un grafo G=(V, E) est formado por un conjunto de elementos llamados vrtices V y un


    conjunto de aristas E que conectan a los distintos vrtices. En ocasiones los vrtices son
    llamados nodos y las aristas arcos. Las aristas se definen como el par de vrtices que
    conectan y pueden tener asociado un valor el cual representa el peso o dificultad para
    desplazarse de un vrtice a otro. Ejemplo grfico de un grafo:

    Dnde: Vrtices = {A, B, C, D, E} Aristas = {(A, B), (A, D), (B, C), (B, D), (B, E), (C, E),
    (D, E), (E, D)}

    Tipos de grafos.

    Existen dos tipos de grafos: los no dirigidos y los dirigidos.

    Grafos No dirigidos.

    Son aquellos en los cuales las aristas no estn orientadas (No son flechas). Cada lado
    se representa entre parntesis, separando sus vrtices por comas, y teniendo en
    cuenta que ambos vrtices son origen y destino a la vez: (Vi, Vj) = (Vj, Vi).

    Grafos Dirigidos.
    Son aquellos en los cuales las aristas estn orientadas (flechas). Cada arista se
    representa entre parntesis, separando sus vrtices por comas y teniendo en cuenta
    (Vi, Vj) (Vj, Vi).

    Los grafos pueden representarse de varias formas en una computadora:

    Listas adyacentes.

    Cada vrtice tiene una lista de vrtices los cuales son adyacentes a l. Representacin
    del ejemplo:

    (A) => B => D

    (B) => C => D => E

    (C) => E

    (D) => E

    (E) => D

    Listas de pares ordenados (incidentes).

    Las aristas se representan como un arreglo de pares ordenados.

    Matriz de adyacencia.

    El grafo se representa por una matriz de tamao VxV, donde V son los vrtices que
    unen a los nodos, la conjuncin de los dos vrtices representa la arista. Representacin
    del ejemplo:

    CAMINO MS CORTO: ALGORITMO DE DIJKSTRA

    Algoritmo de Dijkstra. Tambin llamado algoritmo de caminos mnimos, es un algoritmo


    para la determinacin del camino ms corto dado un vrtice origen al resto de vrtices en
    un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo
    describi por primera vez en 1959.

    Aplicaciones

    En mltiples aplicaciones donde se aplican los grafos, es necesario conocer el camino de menor
    costo entre dos vrtices dados:

    Distribucin de productos a una red de establecimientos comerciales.


    Distribucin de correos postales.
    Sea G = (V, A) un grafo dirigido ponderado.

    El problema del camino ms corto de un vrtice a otro consiste en determinar el camino de menor
    costo, desde un vrtice u a otro vrtice v. El costo de un camino es la suma de los costos (pesos)
    de los arcos que lo conforman.

    Caractersticas del algoritmo

    Es un algoritmo greddy.
    Trabaja por etapas, y toma en cada etapa la mejor solucin sin considerar consecuencias
    futuras.
    El ptimo encontrado en una etapa puede modificarse posteriormente si surge una
    solucin mejor.

    Resolver problemas de grafos

    En general, el proceso de resolver un problema de grafos se puede resumir de la


    siguiente manera:
    1. Identificar el tipo de problema y el algoritmo que se aplicar
    2. Escoger la representacin del grafo (normalmente depende del algoritmo)
    3. Decidir cmo nombrar los nodos del grafo (de 0 a N)
    4. Leer la entrada y construir la representacin del grafo
    5. Aplicar el algoritmo elegido
    6. Imprimir el resultado en el formato que se pide
    Grafos, ALGORITMIA, 07/01/2003, http://www.algoritmia.net/articles.php?id=18

    También podría gustarte