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&Lt--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)

p<--p

en caso contrario

p<--p(ld)

hasta p=NIL