Unidad 9: Grafos

Definicion:

Un grafo dirigido G consiste en un conjunto de vértices V y un conjunto de arcos o aristas A. Los vertice se denominan también nodos o puntos.

Un arco, es un par ordenado de vértices(V,W) donde V es el vértice inicial y W es el vértice terminal del arco. Un arco se expresa como: V–>W y se representa de la siguiente manera:

711.jpg

Los vértice de un grafo pueden usarse para representar objetos. Los arcos se utilizan para representar relaciones entre estos objetos.

Las aplicaciones más importantes de los grafos son las siguientes:

Rutas entre ciudades.

Determinar tiempos máximos y mínimos en un proceso.

Flujo y control en un programa.

Operaciones Sobre Grafos:

En esta sección analizaremos algunas de las operaciones sobre grafos, como :

Creación.

Inserción.

Búsqueda.

Eliminación.

En esta sección, continuaremos utilizando los apuntadores que se usaron en las secciones anteriores. TOP para hacer referencia al primer nodo, LD para indicar liga derecha y LA para indicar liga abajo, por último usaremos los apuntadores P y Q para hacer referencia a los nuevos nodos que vayan a ser usados.

ALGORITMO DE CREACION.


repite

si top=NIL entonces

new(top)

top(la)←NIL

top(ld)←NIL

lee(top(dato))

q←top

en caso contrario

new(p)

p(ld)←NIL

p(la)←NIL

q(la)←p

lee(p(dato))

q←-p

mensaje(otro vertice ?)

lee(respuesta)

hasta repuesta=no

p←top

mientras p<>NIL haz

mensaje(tiene vértices adyacentes p(dato) ?)

lee(respuesta)

si respueta=si entonces

repite

new(q)

lee(q(dato))

q(ld)←p(ld)

p(ld)←q

mensaje(otro vértice ?)

lee(respuesta2)

hasta respuesta2=no

p←p(la)


ALGORITMO DE INSERCION


mensaje(valor a insertar ?)

lee(valor_a_insertar)

si top<>NIL entonces

p←top

mientras p(la)<>NIL haz

p←p(la)

new(q)

lee(q(dato))

p(la)←q

q(la)←NIL

mensaje(Hay vértices adyacentes?)

lee(respuesta)

si respuesta=si entonces

mensaje(Cuantos vértices?)

lee(número_vértices)

desde i=1 hasta número_vértices haz

new(p)

lee(p(dato))

q(ld)←p

q←q(ld)

en caso contrario

mensaje(no existe lista)


ALGORITMO DE BUSQUEDA


mensaje(vértice a buscar)

lee(vértice_a_buscar)

p←top

repite

si p(dato)=vértice_a_buscar entonces

repite

p←p(ld)

escribe(p(dato))

hasta p(ld)=NIL

en caso contrario

p←(la)

hasta p=NIL


ALGORITMO DE BORRADO


mensaje(vértice a borrar ?)

lee(vértice_a_borrar)

p←top

r←p

q←p

sw←falso

repite

si p(dato)=vértice_a_borrar entonces

si p=top entonces

top←top(la)

r←top

sw←verdadero

en caso contrario

r(la)←p(la)

repite

p←p(ld)

dispose(q)

q←p

hasta p=NIL

si sw=verdadero entonces

p←r

q←p

en caso contrario

p←r(la)

q←p

en caso contrario

r←p

repite

q←p(ld)

si q(dato)=vértice_a_borrar entonces

p(ld)←q(ld)

dispose(q)

q←p

en caso contrario

p←p(ld)

hasta p=NIL


Camino Mínimo:

Se denomina camino mínimo entre dos vértices V y W, al camino óptimo entre ambos vértices.Para determinar el camino mínimo entre dos vértices se utiliza el siguiente algoritmo:


desde i=1 hasta número_vértices haz

desde j=1 hasta número_vértices haz

si w[i,j]=0 entonces

q[[i,j]←infinito

en caso contrario

q[i,j]←w[i,j]

desde k=1 hasta número_vértices haz

desde i=1 hasta número_vértices haz

desde j=1 hasta número_vértices haz

q[i,j]←min(q[i,j], q[i,k] + q[k,j])


 


 


Driven by DokuWiki

Politica de Privacidad