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:
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])
