Operaciones sobre grafos

Publicado en Estructura de datos

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 creación

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 inserción

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 búsqueda

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)
                q<--p
             en caso contrario
                p<--p(ld)
hasta p=NIL

Fuente: Apunte de Estructura de Datos del Instituto tecnológico de la Paz