Carrera: Analista de Sistemas y Licenciatura en Sistemas

Asignatura: Estructuras de Datos

Apunte de Cátedra

GRAFOS
1.- INTRODUCCION
Hemos hablado de tipos de datos lineales como una colección de elementos donde cada uno de ellos tiene un
elemento siguiente y uno anterior. Los árboles son tipos de datos no lineales, en donde la restricción anterior
se relaja y cada elemento puede tener más de un elemento siguiente (hijos), pero solo tienen un elemento
anterior (padre del nodo). Ahora vamos a generalizar más la estructura de árbol para permitir que un
elemento pueda tener más de un elemento anterior. Un grafo es una estructura donde cada elemento pueda
tener cero, uno o muchos elementos anteriores y siguientes. Esta generalización permite utilizar esta
estructura para reflejar muchas situaciones del mundo real.

2.- TERMINOLOGIA FUNDAMENTAL

Existen dos teorías paralelas, la de grafos dirigidos y la de grafos no dirigidos.
Un grafo dirigido o digrafo G se define como un par (V, A) donde V es un conjunto de elementos, y A es
una relación binaria definida sobre V. Los elementos de V se denominan nodos o vértices, y los elementos
de A arcos. Dado un arco (x, y) de A, se dice que x es el origen e y el destino del arco.

Ejemplo:
V= {v1, v2, v3, v4}
A= {(v1, v2), (v2, v1), (v3, v2), (v3, v3)}

Cada par (x, y) de A es un par ordenado (por ser A una relación) y es esto lo que determina que el grafo sea
dirigido (cada arco tiene un sentido). Si el par (x, y) no fuera considerado ordenado el grafo sería un grafo no
dirigido. En este último caso el par (x, y) es igual al par (y, x). Si G es un grafo no dirigido los elementos de
A se denominan aristas.

2.1.- Representación gráfica de grafos

Para representar gráficamente un digrafo generalmente se utilizan círculos para los vértices y flechas para
los arcos. En un grafo no dirigido los vértices también se representan con círculos, pero las aristas se
representan con segmentos.

Ejemplos:
G1 = (V, A) grafo dirigido
V = {v1, v2, v3, v4, v5}
A = {(v1, v2), (v2, v1), (v2, v3), (v2, v5), (v3, v3), (v3, v5)}

v1 v2 v4

v3 v5

- Página 79 de 101 -
 Carrera: Analista de Sistemas y Licenciatura en Sistemas
Asignatura: Estructuras de Datos

Apunte de Cátedra

G2 = (V, A) grafo no dirigido

V = {v1, v2, v3, v4}
A = {(v1, v2), (v2, v3), (v2, v4), (v3, v4)}

v1 v2

v4

v3

En G2 no podemos tener como elemento de A a la arista (v2, v1) dado que es igual a la arista (v1, v2). Si la
agregamos, A tendría elementos repetidos y esto no está permitido porque A es un conjunto.

Los vértices y arcos (o aristas) de un grafo pueden ser elementos con información adicional unida a ellos.
Tales grafos se llaman grafos etiquetados o ponderados. Por ejemplo:

Ciudad2
2
120 95

Ciudad1 1 154 4 Ciudad4

101 175
94
3

Ciudad3

2.2.- Definiciones básicas en grafos dirigidos

Se dan a continuación una serie de conceptos definidos sobre digrafos. Para ejemplificar los mismos
usaremos el siguiente grafo:

v2 v3 v6

v1

v4 v5 v7

- Página 80 de 101 -
 Carrera: Analista de Sistemas y Licenciatura en Sistemas
Asignatura: Estructuras de Datos

Apunte de Cátedra

Bucle
Un bucle es un arco de la forma (x, x), es decir es un arco que tiene por origen y destino al mismo vértice.

Ejemplo:
En el grafo dado existen dos bucles: el (v2, v2) y el (v7, v7).

Sucesor
Se dice que el nodo y es sucesor o adyacente del nodo x si existe un arco que tenga por origen a x y por
destino a y, es decir sí el arco (x, y)  A.
Al conjunto de nodos sucesores de x lo denotaremos con S(x).

Ejemplo:
Calculemos el conjunto de sucesores de v4. Existen dos arcos que tienen como origen a v4: (v4, v3) y (v4, v5),
por lo tanto el conjunto de sucesores de v4 lo forman los vértices v3 y v5.
S(v4) = {v3, v5}

Si hacemos el mismo análisis para v2, existen cuatro arcos que tienen como origen a v2: (v2, v2), (v2, v3), (v2,
v4) y (v2, v5), por lo tanto el conjunto de sucesores de v2 lo forman los vértices v2, v3, v4 y v5.
S(v2) = {v2, v3, v4, v5}

Sin embargo no existe ningún arco que tenga como origen a v3, por lo que el conjunto de sucesores de v3 es
vacío. Algo similar ocurre con v6.
S(v3) = S(v6) = 

Predecesor
Se dice que el nodo y es predecesor del nodo x si existe un arco que tenga por origen a y y por destino a x, es
decir sí el arco (y, x)  A.
Al conjunto de nodos predecesores de x lo denotaremos con P(x).

Ejemplo:
El vértice v4 es destino de tres arcos (v1, v4), (v2, v4) y (v5, v4), por lo que el conjunto de predecesores de v4
lo forman v1, v2 y v5.
P(v4) = {v1, v2, v5}

El vértice v2 es destino de dos arcos (v1, v2) y (v2, v2), por lo tanto el conjunto de predecesores de v2 lo
forman v1 y v2.
P(v2) ={v1, v2}

Notar que en el caso v2, el mismo v2 forma parte de su conjunto de predecesores y de su conjunto de
sucesores. Esto se debe a que existe un bucle en v2.

Grado
Grado de entrada del nodo x:
g-(x) = |P(x)|

Grado de salida del nodo x:

g+(x) = |S(X)|

Grado del nodo x:

g(x) = |P(x)  S(X)|

- Página 81 de 101 -
 Carrera: Analista de Sistemas y Licenciatura en Sistemas
Asignatura: Estructuras de Datos

Apunte de Cátedra

Ejemplo:
Si hacemos el cálculo de grados para v4:
g-(v4) = |{v1, v2, v5}| = 3
g+(v4) = |{v3, v5}| = 2
g(v4) = |{v1, v2, v5}  {v3, v5}| = 5

Hacemos el mismo cálculo para v2:

g-(v2) = |{v1, v2}| = 2
g+(v2) = |{v2, v3, v4, v5}| = 4
g(v2) = |{v1, v2}  {v2, v3, v4, v5}| = 5

Notar que si el vértice no tiene un bucle, el grado del mismo es igual a la suma de los grados de entrada y de
salida.

Vértice aislado
Se dice que un vértice x es aislado sí g(x)=0.

Ejemplo:
En el grafo anterior el único vértice aislado es v6:
g(v6) = |P(v6)  S(v6)| = || = 0

El vértice v7 no puede ser considerado como aislado, dado que al tener un bucle su grado es 1.
En general, con la definición de grado que hemos visto, para que un vértice se considere aislado no tiene que
ser origen ni destino de ningún arco, ni siquiera un bucle.

Camino
Informalmente decimos que existe un camino del vértice x al vértice y, si podemos llegar de x a y siguiendo
los arcos y en el sentido en que estos están.
En el grafo del ejemplo existe un camino de v1 a v5 siguiendo los arcos (v1, v2), (v2, v4) y (v4, v5). También
existe otro camino entre los mismos vértices siguiendo los arcos (v1, v4) y (v4, v5).
Formalmente, dado un grafo G = (V, A) decimos que existe un camino del vértice x al vértice y, si existe
una secuencia <v0, v1, ..., vn-1> tal que:
a) v0 = x  vn-1 = y
b) (vi-1, vi)  A con i=1...n-1

La longitud del camino es igual a la cantidad de arcos que lo forman; en la definición anterior sería n-1.
Como caso especial la secuencia <v> es un camino de longitud cero. Esto nos dice que siempre existe un
camino de longitud cero entre un nodo y sí mismo.
Un camino se dice simple o elemental si no pasa dos veces por un mismo vértice.
Un ciclo es un camino simple de longitud mayor que 1, en donde coinciden los vértices primero y último.

Ejemplo:
Existe un camino de v1 a v5 dado que la secuencia <v1, v2, v4, v5> cumple con la definición. La longitud de
este camino es 3.
No existe ningún camino con origen en v3 (de v3 no se puede llegar a ningún otro vértice del grafo).
La secuencia <v2, v2> también cumple con la definición de camino; en general un bucle es un camino de
longitud uno. Pero este camino no puede ser considerado un ciclo (por su longitud).
El camino <v1, v2, v4, v5, v4, v5, v1> tampoco es un ciclo dado que no es simple.
La secuencia <v1, v2, v4, v5, v1> si es un ciclo y su longitud es 4.

- Página 82 de 101 -
 Carrera: Analista de Sistemas y Licenciatura en Sistemas
Asignatura: Estructuras de Datos

Apunte de Cátedra

Cadena
Un concepto similar al de camino pero menos restrictivo es el de cadena.
Informalmente decimos que existe una cadena del vértice x al vértice y, si podemos llegar de x a y siguiendo
los arcos pero sin tener en cuenta el sentido de los mismos.
Habíamos visto que no existía ningún camino con origen en v3. Pero si existen cadenas con inicio en ese
vértice, por ejemplo v3, v4, v5.
Formalmente, dado un grafo G = (V, A) decimos que existe una cadena del vértice x al vértice y, si existe
una secuencia v0, v1, ..., vn-1 tal que:
a) v0 = x  vn-1 = y
b) (vi-1, vi)  A con i=1...n-1

La longitud de la cadena es igual a la cantidad de arcos que la forman; en la definición anterior sería n-1.
Una cadena se dice simple si no pasa dos veces por un mismo vértice.
Un circuito es una cadena simple de longitud mayor que 1, en donde coinciden los vértices primero y último.
De las definiciones dadas se deduce que:
a) Todo camino es una cadena, pero no toda cadena es un camino.
b) Todo ciclo es un circuito, pero no todo circuito es un ciclo.
c) Existe una cadena de x a y si y sólo si existe una cadena de y a x.

Ejemplo:
Las siguientes secuencias son ejemplos de cadena: <v1, v2, v4, v5>, <v2, v1, v4>, <v3, v2, v4, v5>, <v2, v2>.
Las siguientes secuencias además de cadenas son circuitos: <v5, v2, v4, v5>, <v1, v2, v4, v5, v1>, <v3, v4, v2,
v3>.
No existe ninguna cadena con origen en v6. Esto se debe a que v6 es un vértice aislado.
Existe una sola cadena con inicio en v7: <v7, v7> (el único arco con origen en v7 es el bucle).

Conectividad
Un grafo se dice conectado o conexo si existe una cadena entre cualquier par de vértices del grafo.
Un grafo se dice fuertemente conectado o fuertemente conexo si existe un camino entre cualquier par de
vértices del grafo.
Nuevamente a partir de estas definiciones podemos sacar algunas conclusiones:
a) Si G es un grafo fuertemente conectado entonces G es un grafo conectado (el recíproco no se da).
b) Si G no es un grafo conectado entonces G no es un grafo fuertemente conectado.
c) Si G tiene vértices aislados entonces G no es conectado.

Ejemplos:
G1: el grafo que hemos usado en los ejemplos anteriores no es un grafo conectado, y por lo tanto tampoco es
fuertemente conectado

G2:

v2

Es un grafo conectado, pero no es fuertemente

v1
conectado: (no existe camino entre v3 y v2)

v3

- Página 83 de 101 -
 Carrera: Analista de Sistemas y Licenciatura en Sistemas
Asignatura: Estructuras de Datos

Apunte de Cátedra

G3:

v2

Es un grafo conectado y también es fuertemente

v1
conectado (ciclo)

v3

G4:

v2 v4

No es conectado, porque por ejemplo

v1
no existe un camino entre v5 y v3, por
consiguiente tampoco es fuertemente
conectado
v3 v5

3.- TDA GRAFO

Como tipo de dato abstracto un grafo G = (V, A) consta de un conjunto de vértices V, de un conjunto de
arcos A, y operaciones actuando sobre estos dos conjuntos.
Esto implica la necesidad de definir dos nuevas clases llamadas Vertice y Arco. Un vértice es un objeto
compuesto de una etiqueta. Un arco es un objeto compuesto de dos vértices y opcionalmente de una etiqueta.

4.- IMPLEMENTACIONES DE GRAFOS

Para representar un grafo se pueden emplear varias estructuras de datos. La selección apropiada depende de
las operaciones que se realizarán sobre los vértices y sobre los arcos del grafo.

Vamos a ver dos posibles implementaciones:

 Mediante matrices de adyacencia.
 Mediante listas de adyacencia.

4.1.- Mediante matrices de adyacencia

Esta representación utiliza, una secuencia de vértices, y una matriz (array bidimensional) que permite
determinar la existencia de adyacencias entre pares de vértices en un tiempo constante. Esta mejora se ve
contrarrestada por el incremento en el espacio utilizado, que es del O(n2).
Cada vértice tiene asociado un índice.
Para un grafo con n vértices, dispondremos de una matriz M de NxN, tal que M[i , j] contiene la referencia al
arco A que tiene como origen el vértice i-ésimo y como destino el vértice j-ésimo. Si no hay un arco entre
los vértices i y j , entonces M[i , j] almacena una referencia null.
Si el grafo es no dirigido, entonces la referencia a la arista a se almacena en M[i , j] y M[j , i]. Es decir, se
trata de una matriz simétrica.
La representación gráfica es de la siguiente forma:

- Página 84 de 101 -
 Carrera: Analista de Sistemas y Licenciatura en Sistemas
Asignatura: Estructuras de Datos

Apunte de Cátedra

v2 v2

v1 v4 v1 v4

v3 v3

1 F T F F 1 F T F F
2 F F F T 2 T F T T
3 F T F F 3 F T F T
4 F F T F 4 F T T F

La implementación básica para un grafo dirigido es la siguiente:

public class Graph

{
private Vertex[] vertices;
private int vertexPosition;
private boolean[][] edges;
private int vertexQuantity;

Graph(int quantity)
{
vertexQuantity=quantity;
vertices=new Vertex[vertexQuantity];
vertexPosition=0;
edges=new boolean[vertexQuantity][vertexQuantity];
}
public void insertVertex(Object element)
{
vertices[vertexPosition]=new Vertex();
vertices[vertexPosition].setElement(element);
vertexPosition++;
}

public void insertEdge(Object originElement, Object finishElement)

{
int originPosition=getVertexOrder(originElement);
int finishPosition=getVertexOrder(finishElement);
edges[originPosition][finishPosition]=true;
}

private int getVertexOrder(Object element)

{
int position=0, order=-1;
boolean found=false;

while(position<vertexQuantity & found==false)

{
if(vertices[position].getElement().equals(element))
{
found=true;
order=position;
}
position++;
}

return order;
}
}

- Página 85 de 101 -
 Carrera: Analista de Sistemas y Licenciatura en Sistemas
Asignatura: Estructuras de Datos

Apunte de Cátedra

public class Vertex

{
private Object element;

Vertex()
{
element=null;
}

public Object getElement()

{
return element;
}

public void setElement(Object element)

{
this.element=element;
}
}

Cuando un grafo es esparcido o disperso, es decir, la mayoría de los términos de la matriz de adyacencia son
null, esta implementación no es eficiente. Es adecuada cuando el grafo es denso (existen muchos arcos o
aristas)

4.2.- Mediante listas de adyacencia

En esta representación, se mantiene una secuencia con los vértices del grafo. Además para cada vértice del
grafo se mantiene una secuencia con todos sus vértices adyacentes. En un grafo con n vértices habrá n
secuencias de vértices adyacentes. Las referencias a las secuencias se almacenarán en un vector de tamaño n.
Los vértices suelen identificarse por un nombre o etiqueta. En tal caso, se necesita asociar un índice a cada
uno de ellos que nos permita acceder a la secuencia de vértices adyacentes.

La representación gráfica es de la siguiente forma:

v1
v2 v2 v4 /

v2 v4 /
v1 v4
v3 v2 /

v3 v4 v3 /

La implementación básica para un grafo dirigido es la siguiente:

public class Graph

{
private Vertex[] vertices;
private int vertexPosition;
private int vertexQuantity;

Graph(int quantity)
{
vertexQuantity=quantity;
vertices=new Vertex[vertexQuantity];
vertexPosition=0;
}

- Página 86 de 101 -
 Carrera: Analista de Sistemas y Licenciatura en Sistemas
Asignatura: Estructuras de Datos

Apunte de Cátedra

public void insertVertex(Object element)

{
vertices[vertexPosition]=new Vertex();
vertices[vertexPosition].setElement(element);
vertexPosition++;
}

public void insertEdge(Object originElement, Object finishElement)

{
int originPosition=getVertexOrder(originElement);
Edge edge=vertices[originPosition].getEdge();

Edge newEdge=new Edge();

newEdge.setPosition(getVertexOrder(finishElement));

if(edge==null)
{
vertices[originPosition].setEdge(newEdge);
}
else
{
while(edge.getEdge()!=null)
edge=edge.getEdge();
edge.setEdge(newEdge);
}
}

private int getVertexOrder(Object element)

{
int position=0, order=-1;
boolean found=false;

while(position<vertexQuantity & found==false)

{
if(vertices[position].getElement().equals(element))
{
found=true;
order=position;
}
position++;
}

return order;
}

public class Vertex

{
private Object element;
private Edge edge;

Vertex()
{
element=null;
edge=null;
}

public Object getElement()

{
return element;
}

public Edge getEdge()

{
return edge;
}

public void setElement(Object element)

{
this.element=element;
}

- Página 87 de 101 -
 Carrera: Analista de Sistemas y Licenciatura en Sistemas
Asignatura: Estructuras de Datos

Apunte de Cátedra

public void setEdge(Edge edge)

{
this.edge=edge;
}
}

public class Edge

{
private int position;
private Edge edge;

Edge()
{
position=0;
edge=null;
}

public int getPosition()

{
return position;
}

public Edge getEdge()

{
return edge;
}

public void setPosition(int position)

{
this.position=position;
}

public void setEdge(Edge edge)

{
This.edge=edge;
}
}

Faltarían las implementaciones correspondientes a los grafos no dirigidos, cuyo código es muy similar a los
anteriormente citados, solamente que se tendrá en cuenta el hecho de que cada vez que se crea un arco de v i,
a vj, también se debe agregar el arco de vj a vi.

5.- OPERACIONES SOBRE GRAFOS

5.1.- Recorridos
La operación de recorrer un grafo consiste en partir de un vértice determinado y visitar todos aquellos
vértices que son accesibles desde él en un determinado orden. Para realizar la operación pueden seguirse dos
estrategias: el recorrido en profundidad (DFS: Depth First Search) o recorrido en anchura (BFS: Breadh First
Search).

5.1.1.- Recorrido en profundidad

Es una generalización del recorrido en preorden de un árbol: se comienza visitando un vértice cualquiera y, a
continuación, se recorre en profundidad el componente conexo que “cuelga” de cada sucesor.
Este método de recorrido se realiza de acuerdo a los siguientes pasos:
1. Se visita el vértice del que se parte, v.
2. Se selecciona un vértice w, adyacente a v y que todavía no se haya visitado.
3. Se realiza el recorrido en profundidad partiendo del vértice w.
4. Cuando se encuentra un vértice cuyo conjunto de adyacentes han sido visitados en su totalidad se
retrocede hasta el último vértice visitado que tenga vértices adyacentes no visitados y se ejecuta el paso 2.
Suponemos la existencia de un conjunto (visitados) para ir almacenando los vértices del grafo por los que se
va pasando. En principio el conjunto de vértices visitados estará vacío.

- Página 88 de 101 -
 Carrera: Analista de Sistemas y Licenciatura en Sistemas
Asignatura: Estructuras de Datos

Apunte de Cátedra

Es posible que algunos vértices del grafo no se hayan visitado, en cuyo caso se selecciona alguno de ellos
como nuevo vértice de partida y se repite el proceso hasta que todos los vértices de G se hayan visitado.

La implementación del algoritmo es la siguiente:

public void depthFirstSearch(Object element)

{
Vector visited=new Vector(vertexQuantity);
depthFirst(getVertexOrder(element), visited);
}

private void depthFirst(int element, Vector visited)

{
System.out.print(vertices[element].getElement()+" ");
visited.addElement(new Integer(element));
Enumeration adjs=adjacents(new Integer(element));
while(adjs.hasMoreElements())
{
Integer adjsOther=(Integer)adjs.nextElement();
if(!visited.contains(adjsOther))
depthFirst(adjsOther.intValue(), visited);
}
}

Supóngase el siguiente grafo dirigido:

Vamos a realizar su recorrido en profundidad tomando como vértice de partida 1.

6 2 1

7 4 3

El vértice 1 pasa al conjunto de visitados (Visitados = {1}) y obtiene el conjunto de adyacentes de 1 que son
{2, 4}.
Se recorre en profundidad el vértice 2 pasando al conjunto de visitados (Visitados = {1, 2}) y se obtienen sus
adyacentes; este caso {3, 4, 6}.
Como el vértice 3 no se ha visitado se recorre en profundidad. Se inserta en el conjunto de visitados
(Visitados = {1, 2, 3}) y se obtienen su adyacentes; en este caso el vértice {1}. Como el vértice 1 ya está en
el conjunto de visitados terminó el recorrido en profundidad del vértice 3.
Pasamos entonces al otro adyacente del 2 que era el vértice 4. Se recorre en profundidad el vértice 4. Se
inserta en el conjunto de visitados (Visitados = {1, 2, 3, 4}) y se obtienen su adyacentes; en este caso los
vértices {3, 7}. Como el vértice 3 ya está visitado se recorre en profundidad el vértice 7.
Se inserta el 7 en el conjunto de visitados (Visitados = {1, 2, 3, 4, 7}) y se obtienen su adyacentes; en este
caso el vértice {6}.
Como el vértice 6 no se ha visitado se recorre en profundidad. Se inserta en el conjunto de visitados
(Visitados = {1, 2, 3, 4, 7, 6}) y se obtienen su adyacentes; en este caso el vértice {5}.
Como el vértice 5 tampoco se ha visitado se recorre en profundidad el vértice 5. Se inserta en el conjunto de
visitados (Visitados = {1, 2, 3, 4, 7, 6, 5}) y se obtienen sus adyacentes; en este caso el vértice {7}. Como ya

- Página 89 de 101 -
 Carrera: Analista de Sistemas y Licenciatura en Sistemas
Asignatura: Estructuras de Datos

Apunte de Cátedra

se ha visitado termina el recorrido en profundidad del vértice 4 y con el también termina el recorrido de los
vértices 5, 6, y 7.
Pasamos al último adyacente del 2 que era el 6 que ya está visitado terminando el recorrido en profundidad
del vértice 2.
Pasamos ahora al otro adyacente del vértice 1 que es el 4. Como ya está en el conjunto de visitados se
termina el recorrido en profundidad del vértice 1 y con él el recorrido 5 6 7 2 4 1 3 en profundidad del grafo.
El listado de los vértices en profundidad es: 1 2 3 4 7 6 5.

5.1.2.- Recorrido en anchura

Generaliza el recorrido en anchura (por niveles) de un árbol: después de visitar un vértice se visitan los
sucesores, después los sucesores de los sucesores, y así reiteradamente.
Este método de recorrido consiste en los siguientes pasos:
1. Se visita el vértice de partida v.
2. Se visitan todos sus adyacentes que no estuvieran ya visitados y así sucesivamente. Esto es, se visitan
todos los vértices adyacentes antes de pasar a otro vértice.
Utilizamos un conjunto (visitados) para ir almacenando los vértices del grafo por los que se va pasando. En
una cola se mantienen los vértices adyacentes que se han obtenido a partir de los vértices visitados y cuyos
adyacentes aún restan por explorar.
Inicialmente, tanto el conjunto de vértices visitados como la cola de vértices por visitar estarán vacíos.

La implementación del algoritmo es la siguiente:

public void breadhFirstSearch(Object element)

{
breadhFirst(getVertexOrder(element));
}

private void breadhFirst(int element)

{
Vector visited=new Vector(vertexQuantity);
Queue explore=new Queue();
explore.insert(new Integer(element));
visited.addElement(new Integer(element));
do
{
Integer vertexOther=(Integer)explore.delete();
System.out.print(vertices[vertexOther.intValue()].getElement()+" ");
Enumeration adjs=adjacents(vertexOther);
while(adjs.hasMoreElements())
{
Integer adjsOther=(Integer)adjs.nextElement();
if(!visited.contains(adjsOther))
{
explore.insert(adjsOther);
visited.addElement(adjsOther);
}
}
}
while(!explore.isEmpty());
}

Supóngase el mismo grafo dirigido que antes. Hacemos un recorrido en anchura tomando como vértice de
partida el vértice 1. Se inserta en la cola (Cola: <1>) y se inserta en el conjunto de visitados (Visitados =
{1}).
Sacar de la cola el vértice 1. Obtener todos sus adyacentes, en este caso los vértices {2, 4}. Como no
pertenecen al conjunto de visitados se insertan en ese conjunto (Visitados = {1, 2, 4}) y se insertan en la cola
(Cola: <2, 4>).

- Página 90 de 101 -
 Carrera: Analista de Sistemas y Licenciatura en Sistemas
Asignatura: Estructuras de Datos

Apunte de Cátedra

Sacamos de la cola el vértice 2. Obtenemos todos sus adyacentes, en este caso los vértices {3, 4, 6}. Como 3
y 6 no pertenecen al conjunto de visitados se insertan en ese conjunto (Visitados = {1, 2, 4, 3, 6}) y se
insertan en la cola (Cola: <4, 3, 6>).
Sacamos de la cola el vértice 4. Obtenemos todos sus adyacentes, en este caso los vértices 3 y 7. Como el
vértice 7 no pertenecen al conjunto de visitados se inserta en dicho conjunto (Visitados = {12, 4, 3, 6, 7}) y
se inserta en la cola (Cola: <3, 6, 7>).
Sacamos de la cola el vértice 3. Obtenemos todos sus adyacentes, en este caso el vértice {1}. Como ya
pertenece al conjunto de visitados no hacemos nada (Cola: <6, 7>).
Sacamos de la cola el vértice 6. Obtenemos todos sus adyacentes, en este caso el vértice {5}. Como no
pertenecen al conjunto de visitados se inserta en ese conjunto (Visitados = {1, 2, 4, 3, 6, 7, 5}) y se inserta
en la cola (Cola: <7, 5>).
Sacamos de la cola el vértice 7. Obtenemos todos sus adyacentes, en este caso el vértice {6}. Como ya
pertenece al conjunto de visitados no hacemos nada (Cola: <5>).
Sacamos de la cola el vértice 5. Obtenemos todos sus adyacentes, en este caso el vértice {7}. Como ya
pertenece al conjunto de visitados no se procesa.
La cola ya se vació terminando el recorrido en anchura y produciendo el listado: 1 2 4 3 6 7 5.

Para ambos recorridos será necesario el método adyacentes (para lista de adyacencia).

private Enumeration adjacents(Integer element)

{
Vector vertices=new Vector();
Edge position=vertices[element.intValue()].getEdge();

while(position != null)
{
vertices.addElement(new Integer(position.getPosition()));
position=position.getEdge();
}

return vertices.elements();
}

5.2.- Algoritmos de caminos mínimos

El algoritmo de recorrido en anchura puede utilizarse para buscar el camino más corto desde un vértice a
otro cualquiera en un grafo conectado, suponiendo que todas las aristas son igualmente buenas.
En muchas situaciones los arcos tienen asociados costes distintos.

Ejemplos:
 Mapa de carreteras: Los vértices son las ciudades y el coste de cada arco se representa por la distancia en
Km. entre las ciudades.
 Red de computadoras: Las conexiones entre los nodos que forman la red se representan por aristas cuyos
costes estarán en función de las velocidades de dichas conexiones (líneas telefónicas vs. fibra óptica).

Sea G un grafo etiquetado. La longitud o coste de un camino P es la suma del coste de los arcos de P. Esto
es, si P = ((v0, v1), (v1, v2), ..., (vk-1, vk)), la longitud de P, denotada por w( P), se define como

k-1
w(P) =
 w((vi, vi+1))
i=0

La distancia de un vértice v a otro u en G, denotada por d(v, u), es la longitud del camino de longitud mínima
(o, simplemente, camino mínimo) de v a u, si existe dicho camino.

- Página 91 de 101 -
 Carrera: Analista de Sistemas y Licenciatura en Sistemas
Asignatura: Estructuras de Datos

Apunte de Cátedra

Se utiliza la convención de que d(v, u) =  si no hay un camino entre v y u.

Sea un grafo etiquetado G = (V, A), interesa encontrar el camino mínimo de un vértice v al resto de vértices
del grafo. El algoritmo de Dijkstra calcula dichos caminos cuando los arcos tienen costes no negativos, es
decir, w(a)  0  a  A.

5.2.1.- Algoritmo de Dijkstra (árbol mínimo/máximo - camino mínimo/máximo - camino crítico)

Algoritmo voraz (greedy): en cada iteración se selecciona la mejor opción entre las disponibles. Este tipo de
algoritmos se utiliza a menudo en situaciones donde se trata de optimizar una función de coste sobre una
colección de objetos. También conocido como algoritmos ávidos.
Adaptación del esquema voraz al problema de caminos mínimos con origen en v: algoritmo que en cada
iteración añade un vértice al conjunto de vértices visitados. El vértice seleccionado es aquel de los vértices
por visitar más próximo a v. El algoritmo finaliza cuando no quedan vértices por visitar.
Para mantener en cada paso la distancia mínima desde el origen podemos usar un array llamado distancia,
que mantiene en cada paso la distancia desde el origen a cada vértice del grafo.
En cada iteración, una vez seleccionado, de entre los vértices por visitar, el vértice u más próximo a v se
actualiza el array distancia para aquellos vértices w que son adyacentes de u y que cumplen que distancia[u]
+ w((u, w)) < distancia[w].

La implementación del algoritmo es la siguiente:

public Vector dijkstraAlgorithm(Object vertex)

{
return dijkstra(getVertexOrder(vertex));
}

private Vector dijkstra(int vertex)

{
int vs;
Vector distance=new Vector(vertexQuantity);
Vector toVisit=new Vector(vertexQuantity);
for(vs=0; vs<vertexQuantity; vs++)
{
Integer duv=null;
if(vs==vertex)
duv=new Integer(0);
else
duv=new Integer(INFINITO);
distance.insertElementAt(duv, vs);
toVisit.addElement(new Integer(vs));
}
while(!toVisit.isEmpty())
{
Integer u=minimum(distance, toVisit.iterator());
toVisit.removeElement(u);
int du=((Integer)distance.get(u.intValue())).intValue();
if(du != INFINITO)
{
Enumeration adjs=adjacents(u);
while(adjs.hasMoreElements())
{
Integer w=(Integer)adjs.nextElement();
if(toVisit.contains(w))
{
int cuw=getEdge(u, w).getCoste();
if(du + cuw < ((Integer)distance.get(w.intValue())).intValue())
distance.set(w.intValue(), new Integer(du + cuw));
}
}
}
}
return distance;
}

- Página 92 de 101 -
 Carrera: Analista de Sistemas y Licenciatura en Sistemas
Asignatura: Estructuras de Datos

Apunte de Cátedra

private Integer minimum(Vector distance, Iterator toVisitI)

{
Integer vertex, vertexMinimum=(Integer)toVisitI.next();
int distanceValue, distanceMinimum=((Integer)distance.get(vertexMinimum.intValue())).intValue();
while(toVisitI.hasNext())
{
vertex=(Integer)toVisitI.next();
distanceValue=((Integer)distance.get(vertex.intValue())).intValue();
if(distanceValue < distanceMinimum)
{
vertexMinimum=vertex;
distanceMinimum=distanceValue;
}
}
return vertexMinimum;
}

Ejemplo de caminos mínimos a partir del vértice 1:

7
2 3
3 5

8
1 10 1 4
2
5
6
6 5
7

distancia
visitados porVisitar 1 2 3 4 5 6 v mín.
 {1, 2, 3, 4, 5, 6} 0      1
{1} {2, 3, 4, 5, 6} 0 3    5 2
{1, 2} {3, 4, 5, 6} 0 3 10   5 6
{1, 2, 6} {3, 4, 5} 0 3 10 7  5 4
{1, 2, 6, 4} {3, 5} 0 3 10 7 13 5 3
{1, 2, 6, 4, 3} {5} 0 3 10 7 11 5 5
{1, 2, 6, 4, 3, 5}  0 3 10 7 11 5

El coste total del algoritmo es O(n2).

Para reconstruir el camino mas corto a cada vértice, se agrega otro arreglo Camino de vértices, tal que
caminos[v] contenga el vértice inmediato anterior a v en el camino más corto.
Se asigna un valor inicial a camino[v] igual a 0 para todo v ≠ 0. El arreglo Camino puede actualizarse
después de la actualización del arreglo distancia en el método de dijkstra(int).

if(du + cuw < ((Integer)distance.get(w.intValue())).intValue())

{
distance.set(w.intValue(), new Integer(du + cuw));
way[w.intValue()]=u.intValue();
}

Al término de Dijkstra, el camino a cada vértice puede encontrarse regresando por los vértices predecesores
del arreglo camino. Por ejemplo, para reconstruir el camino más corto del vértice 1 (origen) al vértice 4,
sería: v  4

- Página 93 de 101 -
 Carrera: Analista de Sistemas y Licenciatura en Sistemas
Asignatura: Estructuras de Datos

Apunte de Cátedra

hacer
{
Escribir v
v  way[v]
}
mientras(v != 1)

5.2.2.- Algoritmo de Floyd-Warshall (camino mínimo entre todos los pares de nodos)
El problema que intenta resolver este algoritmo es el de encontrar el camino más corto entre todos los pares
de nodos o vértices de un grafo. Esto es semejante a construir una tabla con todas las distancias mínimas
entre pares de ciudades de un mapa, indicando además la ruta a seguir para ir de la primera ciudad a la
segunda. Este es uno de los problemas más interesantes que se pueden resolver con algoritmos de grafos.
Existen varias soluciones a este problema y los algoritmos a aplicar dependen también de la existencia de
arcos con pesos o costes negativos en el grafo. En el caso de no existir pesos negativos, sería posible ejecutar
n veces el algoritmo de Dijkstra para el cálculo del camino mínimo, donde n es el número de vértices o
nodos del grafo. Esto conllevaría un tiempo de ejecución de O(n3) (aunque se puede reducir). Si existen
arcos con pesos negativos, se puede ejecutar también n veces el algoritmo de Bellman-Ford (que se verá mas
adelante), una vez para cada nodo del grafo. Para grafos densos (con muchas conexiones o arcos) esto
conllevaría un tiempo de ejecución de O(n4).
El algoritmo de Floyd-Warshall (“All-Pairs-Shortest-Path” - Todos los caminos mínimos) ideado por Floyd
en 1962 basándose en un teorema de Warshall también de 1962, usa la metodología de Programación
Dinámica para resolver el problema. Éste puede resolver el problema con pesos negativos y tiempos de
ejecución iguales a O(n3); sin embargo, para ciclos de peso negativo el algoritmo tiene problemas.
Este algoritmo se puede aplicar a multitud de problemas, incluyendo el diseño de circuitos, el diseño de rutas
de transporte, aproximaciones al problema del viajante de comercio, o como base de otros algoritmos más
complejos.

La implementación del algoritmo es la siguiente:

public int[][] floyd()

{
int u, v, w;
int[][] floydMatrix=//asignarle la matriz de adyacencia
//no se aceptan bucles, ni ciclos
for(u=0; u<vertexQuantity; u++)
floydMatrix[u][u]=0;
for(u=0; u<vertexQuantity; u++)
for(v=0; v<vertexQuantity; v++)
for(w=0; w<vertexQuantity; w++)
if((v!=u) & (u!=w) & floydMatrix[v][u] < INFINITO & floydMatrix[u][w] < INFINITO)
if(floydMatrix[v][w] > (floydMatrix[v][u] + floydMatrix[u][w]))
floydMatrix[v][w]=floydMatrix[v][u]+floydMatrix[u][w];
return floydMatrix;
}

5.2.3.- Algoritmo de Bellman-Ford (camino mínimo/máximo)

Soluciona el problema de la ruta más corta o camino mínimo desde un nodo origen, de un modo más general
que el algoritmo de Dijkstra, ya que permite valores negativos en los arcos.
El algoritmo devuelve un valor booleano si encuentra un circuito o lazo de peso negativo. En caso contrario
calcula y devuelve el camino mínimo con su coste.
Para cada vértice v perteneciente a V, se mantiene el atributo distancia[v] como cota superior o coste del
camino mínimo desde el origen o al vértice v.

El pseudocódigo del algoritmo es:

booleano Bellman-Ford(o)
{
distancia[o]=0

- Página 94 de 101 -
 Carrera: Analista de Sistemas y Licenciatura en Sistemas
Asignatura: Estructuras de Datos

Apunte de Cátedra

predecesor[o] = 0
para(cada v perteneciente a V[G]-{v})
{
distancia[v]=infinito
predecesor[v]=nulo
}
para(i de 1 a V[G]-1)
para(cada arco (u ,v) perteneciente a A[G])
si(distancia[v] > distancia[u] + matrizAdya(u, v))
{
distancia[v] = distancia[u] + matrizAdya(u, v)
predecesor[v] = u
}
para (cada arco (u, v) chequea lazo de peso negativo)
si (distancia[v] > distancia[u] + matrizAdya(u, v))
retornar falso //el algoritmo no converge
retornar verdadero
}

Ejemplo de caminos mínimos con pesos negativos a partir del vértice A:

B 2
-1

A 3 2 E
1
-3
4
C D
5

A B C D E
0    
0 -1   
0 -1 4  
0 -1 2  
0 -1 2  1
0 -1 2 1 1
0 -1 2 -2 1

El problema de la ruta más larga puede ser transformado en el de ruta más corta cambiando el signo de los
costes de los arcos.
En este caso el problema es inconsistente para circuitos de peso positivo.

5.2.4.- Algoritmo de Ford-Fulkerson (flujo máximo)

Se puede considerar un grafo como una red de flujo. Donde un nodo fuente produce o introduce en la red
cierta cantidad de algún tipo de material, y un nodo sumidero lo consume. Cada arco, por lo tanto, puede
considerarse como un conducto que tiene cierta capacidad de flujo. De igual modo que en redes eléctricas
(Ley de Kirchhoff), la suma de flujos entrantes a un nodo, debe ser igual a la suma de los salientes (principio
de conservación de energía), excepto para el nodo fuente y el nodo sumidero.
Por lo tanto, el problema de flujo máximo se enuncia como: ¿cuál es la tasa a la cual se puede transportar el
material desde el nodo fuente al nodo sumidero, sin violar las restricciones de capacidad?. Este algoritmo se
puede usar para resolver modelos de: transporte de mercancías (logística de aprovisionamiento y
distribución), flujo de gases y líquidos por tuberías, componentes o piezas en líneas de montaje, corriente en

- Página 95 de 101 -
 Carrera: Analista de Sistemas y Licenciatura en Sistemas
Asignatura: Estructuras de Datos

Apunte de Cátedra

redes eléctricas, paquetes de información en redes de comunicaciones, tráfico ferroviario, sistema de

regadíos, etc.
Una red de flujo es un grafo dirigido G=(V, E) donde cada arco (u, v) perteneciente a E tiene una capacidad
no negativa. Se distinguen dos nodos: la fuente o nodo s, y el sumidero o nodo t. Si existen múltiples fuentes
y sumideros, el problema se puede simplificar añadiendo una fuente común y un sumidero común.

Este algoritmo depende de tres conceptos principales:

 Un camino de aumento, es una trayectoria desde el nodo fuente s al nodo sumidero t que puede
conducir más flujo.
 La capacidad residual es la capacidad adicional de flujo que un arco puede llevar cf(u, v) = c(u, v) - f(u,
v).
 Teorema de Ford-Fulkerson (1962): En cualquier red, el flujo máximo que fluye de la fuente al
destino es igual a la capacidad del corte mínimo que separa a la fuente del destino.

Una variación del algoritmo de Ford-Fulkerson es el algoritmo de Edmonds-Karp (J. Edmonds; R.M. Karp
- 1972). En éste, el „camino de aumento‟ es elegido usando una búsqueda por niveles o en anchura (breadth-
first search). El algoritmo de Edmonds-Karp requiere O(n2) tiempo de computación, donde n es el número
de nodos o vértices, y el número de arcos del grafo.

5.2.5.- Algoritmo de Kruskal y Prim (árbol de coste total mínimo/máximo)

El objetivo del algoritmo de Kruskal es construir un árbol (subgrafo sin ciclos) formado por arcos
sucesivamente seleccionados de mínimo peso a partir de un grafo con pesos en los arcos.
El algoritmo de Prim encuentra un árbol de peso total mínimo conectando nodos o vértices con arcos de peso
mínimo del grafo sin formar ciclos.

5.3.- Algoritmo de Fleury (recorridos eulerianos)

El algoritmo de Fleury es un algoritmo de búsqueda de caminos eulerianos en grafos. El algoritmo garantiza
que si existe un camino euleriano en el grafo lo encuentra. Basa su ejecución en cuatro pasos, partiendo del
requisito de que el grafo sea euleriano.

Grafos Eurelianos
Definimos un grafo euleriano G como un grafo conexo que posee un camino cerrado que incluye todas las
aristas de G, a la que llamaremos camino euleriano. Cada arista se recorre una vez y sólo una vez. Definimos
que G es semi-euleriano si levantamos la restricción de que el camino euleriano deba ser cerrado.

En la figura siguiente se puede observar un grafo no euleriano y otro grafo euleriano y su correspondiente
camino:

a b b c

c a f

d e d e

Grafo no Euleriano Grafo Euleriano de camino: a d e f c e b c d b a

- Página 96 de 101 -
 Carrera: Analista de Sistemas y Licenciatura en Sistemas
Asignatura: Estructuras de Datos

Apunte de Cátedra

Grafos Hamiltonianos
En los grafos euleriano se examinaba la posibilidad de crear un camino cerrado que incluyese todas las
aristas de un grafo conexo G. Un problema similar es el de sí existe un camino cerrado que pasa exactamente
una vez a través de cada vértice de G. Si este existe se dice que G es un grafo hamiltoniano.

A continuación se muestra el grafo hamiltoniano dodecaedrico:

j d

a q
k i e p

h f

l g o

n
m ñ

s r

- Página 97 de 101 -
 Carrera: Analista de Sistemas y Licenciatura en Sistemas
Asignatura: Estructuras de Datos

Apunte de Cátedra

REFERENCIAS
De libros...
1. “Algoritmos + Estructuras = Programas”. Nicklaus Wirth. Editorial Prentice Hall. 1987. México.

2. “Cómo programar en Java”. H. M. Deitel y P. J. Deitel. Editorial Prentice Hall. 1997. México.

3. “Data Structures, Algorithms and Program Style Using C”. J. F. Korsh y L. J. Garrett. Editorial PWS
Publishing CO. 1988. Estados Unidos.

4. “Data Structures: from Arrays to Priority Queues”. Wayne Amsbury. Editorial Wadsworth Publishing.
1985. Estados Unidos.

5. “Data Structures and Algorithm Analysis in C”. Mark Allen Weiss. Editorial Addison Wesley. 1996.
Estados Unidos.

6. “El lenguaje de programación Java”. Tercera edición. K. Arnold, J. Gosling y D. Holmes. Editorial
Addison Wesley. 2001. España.

7. “Estructuras de Datos”. Osvaldo Cairó y Silvia Guardati. Editorial Mc. Graw Hill. 1993. México.

8. “Estructuras de Datos en Java”. Mark Allen Weiss. Editorial Addison Wesley. 2000. España.

9. “Estructuras de Datos en Pascal”. A. Tenenbaum y M. Augestein. Editorial Prentice Hall. 1983. España.

10. “Estructuras de Datos y Algoritmos”. Alfred Aho, John Hopcroft y Jeffrey Ullman. Editorial Addison-
Wesley. 1988. Estados Unidos.

11. “Estructuras de Datos-Algoritmos, Abstracción y Objetos”. L. Joyanes Aguilar y I. Zahonero Martínez.

Editorial Mac. Graw Hill. 1998. España.

12. “Fundamentals of Data Structures”. Ellis Horowitz y Sartaj Sahni. Editorial WH Freeman & CO. 1983.
Estados Unidos.

13. “Introducción a la Programación Orientada a Objetos con Java”. Primera Edición. C. Thomas Wu.
Editorial Mc. Graw Hill. 2001. España.

14. “Java Data Structures and Programming”. Liwu Li. Editorial Springer. 1998. Alemania.

15. “Pascal y Estructuras de Datos”. Neil Dale y Susan Lily. Editorial Mc. Graw Hill. 1992. México.

16. “Reliable Data Structures in C”. Thomas Plum. Editorial Plum Hall. 1985. Estados Unidos.

De páginas en Internet...
 http://babbage.clarku.edu/~achou/cs160/source/datastructures/

 http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/binsort.html

 http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/radixsort.html

 http://dis.eafit.edu.co/cursos/st030/desarrolloCursoST030_034.html

- Página 98 de 101 -
 Carrera: Analista de Sistemas y Licenciatura en Sistemas
Asignatura: Estructuras de Datos

Apunte de Cátedra

 http://doschivos.com/new/algobusque.htm

 http://guamuchil.udo.mx/~fcampos/ordenamientos.htm

 http://home.hawaii.rr.com/chodandkathy/linear/search sort_files/slide0285.htm

 http://mailweb.pue.udlap.mx/~ccastane/Syllabus_Estructura_Datos/Sy_EstructuraDatos_Java.html

 http://mailweb.udlap.mx/~ingrid/Clases/Trie.html

 http://members.tripod.com/fcc98/tutores/alg2/alg2.html

 http://rfhs8012.fh-regensburg.de/~saj39122/AD/aufgaben/aufg06/aufg06.htm

 http://trevinca.ei.uvigo.es/~pavon/transparencias/TTema4Grafos.pdf

 http://xue.unalmed.edu.co/~dosorio/linux/hash.htm

 http://www.cee.hw.ac.uk/DSA/ProgramIndex.htm

 http://www.cs.utsa.edu/~carola/teaching/cs5633/spring04/slides/Lecture-18.pdf

 http://www.dcc.uchile.cl/~rbaeza/handbook/hbook.html

 http://www.dma.fi.upm.es/fleury/definicionesGrafos.htm

 http://www.dma.fi.upm.es/gregorio/grafos/paginagrafos.html

 http://www.hut.fi/~ccandoli/botanica/algorithms/java/

 http://www.infor.uva.es/~jmrr/TAD2003/home.htm

 http://www.it.uc3m.es/~tsps/practica08/enunciado.htm

 http://www.itlp.edu.mx/publica/tutoriales/estructdatos2/

 http://www.lcc.uma.es/~av/Libro/CAP2.pdf

 http://www.javacommerce.com/tutorial/JavaData/JavaData.html

 http://www.seeingwithc.org/topic4html.html

- Página 99 de 101 -