El estudio de los grafos comienza con Euler, en 1736, con el celebre problema
de los puentes de su ciudad, Koenigsberg, siete puentes que unían
cuatro sectores de tierra, en el curso del rio Pregal que atravesaba la ciudad.
El tema es conocido como el Koenigsberg Bridge Problem, que propone, arrancando
de un area de tierra, recorrer las otras areas de tierra, a través de los
puentes, pasando solo una vez por cada puente, retornando al area de inicio.
C
C
-------------------------------|-|-----------|-|-------------------------|-|------------
|-| |-| |-| *----
c |-| |-| d |-| g / \ \
|-| |-| |-| / \ \
+--|-|-----------|-|--+ +--|-|------------ c| |d \g
| | | \ / \
| A --------------------- \ / \
Rio Pregal | ||||||||||||||||||||| D A *---------* D
| Isla Kneiphof --------------------- / \ e /
| | e | / \ /
+--|-|-----------|-|--+ +--|-|------------ a| |b /f
|-| |-| |-| \ / /
a |-| |-| b |-| f \ / /
|-| |-| |-| *----
-------------------------------|-|-----------|-|-------------------------|-|------------
B
B
La solución a que llegó Euler es que para que exista una caminata, que
arrancando en un vértice, recorra todos los puentes una vez y vuelva al
punto de partida, los vértices deben tener, cada uno, un grado par.
El matemático inició de esta manera la representación de problemas a través
de grafos.
Veamos algunos ejemplos donde la estructura de datos grafos puede ser muy util :
Entre muchos más, ya que grafos es la estructura matemática más usada.
*---* *---* *---* +------*****
| 1 | | 1 | +--| 1 |--+ | * 1 *
*---* *---* | *---* | +------*****
||| | | | | |
+-------+|+------+ +-------+ +------+ V A |
| | | | | | | |
*---* | *---* *---* *---* | *---* | *****---------*****
| 2 |------------| 3 | | 2 | | 3 | +--| 2 |--+ * 2 * * 4 *
*---* | *---* *---* *---* *---* *****---------*****
| | | | | | | | | | | |
+-------+|+------+ +--+ +--+ +--+ +--+ V | | | |
||| | | | | | | | | |
*---* *---* *---* *---* *---* *---* *****---------+ | |
| 4 | | 4 | | 5 | | 6 | | 7 | | 3 | * 3 *-----------+ |
*---* *---* *---* *---* *---* *---* *****-------------+
Grafo 1 Grafo 2 Grafo 3 Grafo 4
*---* *---* *---*
| 1 | | 1 | | 1 |
*---* *---* *---*
| | |
+-------+ +------+ |
| | |
*---* *---* *---* *---* *---* | *---*
| 2 | | 3 | | 2 |------------| 3 | | 2 |------------| 3 |
*---* *---* *---* *---* *---* | *---*
| | | |
+-------+ +------+ |+------+
| | ||
*---* *---*
| 4 | | 4 |
*---* *---*
Subgrafo 1 del Grafo 1 Subgrafo 2 del Grafo 1 Subgrafo 3 del Grafo 1 Subgrafo 4 del Grafo 1
*---* *---* *---* *---*
| 1 | +--| 1 | | 1 | +--| 1 |--+
*---* | *---* *---* | *---* |
| | |
V V A
| | |
| *---* *---* | *---* |
+--| 2 | | 2 | +--| 2 |--+
*---* *---* *---*
|
V
|
*---* *---*
| 3 | | 3 |
*---* *---*
Subgrafo 1 del Grafo 3 Subgrafo 2 del Grafo 3 Subgrafo 3 del Grafo 3 Subgrafo 4 del Grafo 3
*---* *---* *---*
| 1 | | 5 | /| 1 |\ Paris
*---* *---* //*---* \
||| | -----------/ | -----------386
+-------+|+------+ +-------+ / 383 / |468 \
| | | | / ----- | \
*---* | *---* *---* *---* *---* /557 *---* *---*
| 2 |------------| 3 | | 6 |------------| 7 | Nantes | 2 |------------| 3 |------------| 4 | Nancy
*---* | *---* *---* *---* *---* / 562 /*---*\ 491 *---*
| | | | | / / | \
+-------+|+------+ +------+ 338| /----------485 |393 ------------314
||| | |// | \
*---* *---* *---* *---* *---*
| 4 | | 8 | Bourdeos | 5 |------------| 6 | | 7 | Marsella
*---* *---* *---* 224 *---* *---*
Grafo 5 Grafo 6
Observar que hemos denominado a los vértices del grafo con los números
1, 2, ..., n y no hemos hecho mención a sus contenidos. En el grafo 6
están denominados los vértices y también se hace mención a sus contenidos,
en este caso, los nombres de la ciudades de Francia que los vértices
representan. Otro dato que el vértice podría contener es, por ejemplo,
la población de la ciudad, entre otros.
Observar que los arcos han sido dibujados, pero no se ha puesto denominación
alguna. Normalmente se denominan a los arcos con las letras minúsculas
del alfabeto, como puede verse en el grafo de Euler.
En el grafo 6, se han representado los arcos sin su denominación, aunque
sí su contenido, en este caso la extensión en kilometros de la carretera
que une cada par de ciudades Francesas.
Observar que el grafo 4 no es un grafo propiamente dicho, ya que sobre el
vértice 1 un arco comienza y termina, y sobre los vértices 3 y 4 hay más
de un arco entre ellos.
Los grafos se pueden representar de diversas manera. La representación
correcta debe elegirse según la aplicación que se le dará al grafo, en
particular, teniendo en cuenta las funciones a realizar sobre el mismo.
Las siguientes son representaciones posibles de grafos :
Son matrices cuadradas de tantas filas y columnas como vértices tenga el
grafo a representar. En las celdas de la matriz se indica si existe un arco
entre los vértices que determinan la celda.
Partiendo de los nodos de cada vértice, evoluciona una lista que informa
los nodos que son adyacentes del inicial.
Los nodos de una multilista de adyacencia tiene enlaces a varias listas,
hecho del cual proviene su nombre.
Esta representación se basa en que existe un nodo, y solo uno, por cada
arco, aunque este nodo enlace varias listas.
La estructura del nodo es :
Para visualizar la navegación de grafos usaremos el siguiente ejemplo :
Cualquier árbol, cuyas ramas son solamente arcos de un grafo G y donde
todos sus nodos son todos los vértices del grafo G, recibe el nombre
de árbol incluido en el grafo G.
Para la implementacion de grafos con listas usaremos el grafo 9 :
Las entidades que participan en un grafo son : los grafos, los vertices y los arcos.
El siguiente bosquejo asocia a cada una de estas entidades con una clase,
siendo estas clases capaces de producir ocurrencias de objetos de dichas clases.
Matrices de Adyacencia ( Adjacency Matrices )
1 2 3 4 5 6 7 1 2 3 4 5 6 7 8
.................. ...................
1 . 0 1 1 0 0 0 0 . 1 . 0 1 1 1 0 0 0 0 .
. . . .
2 . 1 0 0 1 1 0 0 . 2 . 1 0 1 1 0 0 0 0 .
1 2 3 4 . . . .
........... 3 . 1 0 0 0 0 1 1 . 1 2 3 3 . 1 1 0 1 0 0 0 0 .
1 . 0 1 1 1 . . . ......... . .
. . 4 . 0 1 0 0 0 0 0 . 1 . 0 1 0 . 4 . 1 1 1 0 0 0 0 0 .
2 . 1 0 1 1 . . . . .
. . 5 . 0 1 0 0 0 0 0 . 2 . 1 0 1 . 5 . 0 0 0 0 0 1 0 0 .
3 . 1 1 0 1 . . . . . . .
. . 6 . 0 0 1 0 0 0 0 . 3 . 0 0 0 . 6 . 0 0 0 0 1 0 1 0 .
4 . 1 1 1 0 . . . ......... . .
........... 7 . 0 0 1 0 0 0 0 . 7 . 0 0 0 0 0 1 0 1 .
.................. . .
8 . 0 0 0 0 0 0 1 0 .
...................
Grafo 1 Grafo 2 Grafo 3 Grafo 5
Observar que en todos los grafos la diagonal de la matriz tiene solo ceros.
Observar que para los grafos no direccionados la submatriz superior es
espejo de la inferior, respecto de la diagonal.
Observar que en los grafos direccionados, normalmente, difieren la submatriz
superior de la inferior.
Observar que solo existe una señal, indicando la existencia o no del arco,
tratandose de una representación inadecuada para almacenar información
perteneciente al arco, como podría ser la distancia entre dos ciudades,
si los vértices representan a las mismas.
Listas de Adyacencia ( Adjacency Matrices )
+-------+ +-------+ +-------+ +-------+ +-------+ +-------+ +-------+ +-------+ +-------+ +-------+
Vertice 1 | --|----->| 2 | --|--->| 3 | --|--->| 4 | 0 | Vertice 1 | --|----->| 2 | 0 | Vertice 1 | --|----->| 2 | --|--->| 3 | --|--->| 4 | 0 |
+-------+ +-------+ +-------+ +-------+ +-------+ +-------+ +-------+ +-------+ +-------+ +-------+ +-------+
Vertice 2 | --|----->| 1 | --|--->| 3 | --|--->| 4 | 0 | Vertice 2 | --|----->| 1 | --|--->| 3 | 0 | Vertice 2 | --|----->| 1 | --|--->| 3 | --|--->| 4 | 0 |
+-------+ +-------+ +-------+ +-------+ +-------+ +-------+ +-------+ +-------+ +-------+ +-------+ +-------+
Vertice 3 | --|----->| 1 | --|--->| 2 | --|--->| 4 | 0 | Vertice 3 | 0 | Vertice 3 | --|----->| 1 | --|--->| 2 | --|--->| 4 | 0 |
+-------+ +-------+ +-------+ +-------+ +-------+ +-------+ +-------+ +-------+ +-------+
Vertice 4 | --|----->| 1 | --|--->| 2 | --|--->| 3 | 0 | Vertice 4 | --|----->| 1 | --|--->| 2 | --|--->| 3 | 0 |
+-------+ +-------+ +-------+ +-------+ +-------+ +-------+ +-------+ +-------+
Vertice 5 | --|----->| 6 | 0 |
+-------+ +-------+ +-------+
Vertice 6 | --|----->| 5 | --|--->| 7 | 0 |
+-------+ +-------+ +-------+
Vertice 7 | --|----->| 6 | --|--->| 8 | 0 |
+-------+ +-------+ +-------+
Vertice 8 | --|----->| 7 | 0 |
+-------+ +-------+
Grafo 1 Grafo 3 Grafo 5
Observar que en el caso de grafos no direccionados un arco aparece dos veces.
Observar que el el caso de grafos direccionados un arco aparece solo una vez.
Observar que si los arcos conllevan información, es facil administrarla en
el caso de los digrafos, pero no así en los grafos.
Multilistas de Adyacencia ( Adjacency Multilist )
+---------------------------------------------+
| M | v1 | v2 | Enlace por v1 | Enlace por v2 |
+---------------------------------------------+
donde M es un campo de marcado, un bit, que puede ser usado para señalar,
por ejemplo, que el arco fué visitado.
Este nodo también podría tener campos para la información asociada a los
arcos, como ocurre en los grafos ponderados, donde los arcos tienen un peso.
+-------+
*---* Vertice V1 | --|--+ +---------------------+
| 1 | +-------+ +--> Nodo N1 | | 1 | 2 | N2 | N4 | arco(1,2) Lista V1 --> N1 --> N2 --> N3
*---* Vertice V2 | --|--+ +---------------------+ Lista V2 --> N1 --> N4 --> N5
||| +-------+ +-> Nodo N2 | | 1 | 3 | N3 | N4 | arco(1,3) Lista V3 --> N2 --> N4 --> N6
+-------+|+------+ Vertice V3 | --|---+ +---------------------+ Lista V4 --> N3 --> N5 --> N6
| | | +-------+ +-> Nodo N3 | | 1 | 4 | 0 | N5 | arco(1,4)
*---* | *---* Vertice V4 | --|---+ +---------------------+
| 2 |------------| 3 | +-------+ Nodo N4 | | 2 | 3 | N5 | N6 | arco(2,3)
*---* | *---* +---------------------+
| | | Nodo N5 | | 2 | 4 | 0 | N6 | arco(2,4)
+-------+|+------+ +---------------------+
||| Nodo N6 | | 3 | 4 | 0 | 0 | arco(3,4)
*---* +---------------------+
| 4 |
*---*
Grafo 1
Una secuencia de construcción del grafo requeriría, primero, crear los
nodos de los vértices, segundo, crear los nodos de los arcos, y tercero,
enlazar todos los nodos donde participa un determinado vértice, recurriendo
hasta agotar los vértices.
Navegación de Grafos
*---*
| 1 |
*---*
| |
+-------+ +-------+
| | +-------+ +-------+ +-------+
*---* *---* Indice 0 Vertice 1 | --|----->| 2 | --|--->| 3 | 0 |
| 2 | | 3 | +-------+ +-------+ +-------+ +-------+
*---* *---* Indice 1 Vertice 2 | --|----->| 1 | --|--->| 4 | --|--->| 5 | 0 |
| | | | +-------+ +-------+ +-------+ +-------+
+--+ +--+ +--+ +--+ Indice 2 Vertice 3 | --|----->| 1 | --|--->| 6 | --|--->| 7 | 0 |
| | | | +-------+ +-------+ +-------+ +-------+
*---* *---* *---* *---* Indice 3 Vertice 4 | --|----->| 2 | --|--->| 8 | 0 |
| 4 | | 5 | | 6 | | 7 | +-------+ +-------+ +-------+
*---* *---* *---* *---* Indice 4 Vertice 5 | --|----->| 2 | --|--->| 8 | 0 |
| | | | +-------+ +-------+ +-------+
| +---+ +---+ | Indice 5 Vertice 6 | --|----->| 3 | --|--->| 8 | 0 |
+----------+| |+----------+ +-------+ +-------+ +-------+
|| || Indice 6 Vertice 7 | --|----->| 3 | --|--->| 8 | 0 |
*---* +-------+ +-------+ +-------+ +-------+ +-------+
| 8 | Indice 7 Vertice 8 | --|----->| 4 | --|--->| 5 | --|--->| 6 | --|--->| 7 | 0 |
*---* +-------+ +-------+ +-------+ +-------+ +-------+
Grafo 8 Grafo 8 representado por su Lista de Adyacencia
Los grafos pueden ser navegados según las siguientes formas básicas :
A lo Ancho ( Breadth First Search )
*---* *---* *---*
Nodo inicio ...>| 1 |(1) | 1 |(8) | 1 |(2)
*---* *---* *---*
| | | | | |
+-------+ +-------+ +-------+ +-------+ +-------+ +-------+
| | | | | |
*---* *---* *---* *---* *---* *---*
| 2 |(2) | 3 |(3) | 2 |(6) | 3 |(7) | 2 |(5) | 3 |(1) <... Nodo Inicio
*---* *---* *---* *---* *---* *---*
| | | | | | | | | | | |
+--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+
| | | | | | | | | | | |
*---* *---* *---* *---* *---* *---* *---* *---* *---* *---* *---* *---*
| 4 |(4)| 5 |(5) | 6 |(6)| 7 |(7) | 4 |(2)| 5 |(3) | 6 |(4)| 7 |(5) | 4 |(7)| 5 |(8) | 6 |(3)| 7 |(4)
*---* *---* *---* *---* *---* *---* *---* *---* *---* *---* *---* *---*
| | | | | | | | | | | |
| +---+ +---+ | | +---+ +---+ | | +---+ +---+ |
+----------+| |+----------+ +----------+| |+----------+ +----------+| |+----------+
|| || || || || ||
*---* *---* *---*
| 8 |(8) Nodo inicio ...>| 8 |(1) | 8 |(6)
*---* *---* *---*
Grafo 8 Grafo 8 Grafo 8
En Profundidad ( Depth First Search )
*---* *---* *---*
Nodo inicio ...>| 1 |(1) | 1 |(4) | 1 |(2)
*---* *---* *---*
| | | | | |
+-------+ +-------+ +-------+ +-------+ +-------+ +-------+
| | | | | |
*---* *---* *---* *---* *---* *---*
| 2 |(2) | 3 |(7) | 2 |(3) | 3 |(5) | 2 |(3) | 3 |(1) <... Nodo Inicio
*---* *---* *---* *---* *---* *---*
| | | | | | | | | | | |
+--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+
| | | | | | | | | | | |
*---* *---* *---* *---* *---* *---* *---* *---* *---* *---* *---* *---*
| 4 |(3)| 5 |(5) | 6 |(6)| 7 |(8) | 4 |(2)| 5 |(8) | 6 |(6)| 7 |(7) | 4 |(4)| 5 |(6) | 6 |(7)| 7 |(8)
*---* *---* *---* *---* *---* *---* *---* *---* *---* *---* *---* *---*
| | | | | | | | | | | |
| +---+ +---+ | | +---+ +---+ | | +---+ +---+ |
+----------+| |+----------+ +----------+| |+----------+ +----------+| |+----------+
|| || || || || ||
*---* *---* *---*
| 8 |(4) Nodo inicio ...>| 8 |(1) | 8 |(5)
*---* *---* *---*
Grafo 8 Grafo 8 Grafo 8
Componentes
*---*
| 1 |
*---*
| |
+-------+ +-------+
| |
*---* *---* *---* *---*
| 2 | | 3 | | 9 | |1 3|
*---* *---* *---* *---*
| | | | | | |
+--+ +--+ +--+ +--+ +--+ +--+ |
| | | | | | |
*---* *---* *---* *---* *---* *---* |
| 4 | | 5 | | 6 | | 7 | |1 0| |1 1| |
*---* *---* *---* *---* *---* *---* |
| | | | | | |
| +---+ +---+ | +--+ +--+ |
+----------+| |+----------+ | | |
|| || *---* *---*
*---* |1 2| |1 4|
| 8 | *---* *---*
*---*
Componente 1 Componente 2 Componente 3
Grafo 9
Arboles Incluidos ( Spanning Tree )
Si en BFS o DFS se agrupan los arcos, que esas enumeraciones
recorren, en un conjunto que llamamos Conjunto de Arcos Recorridos, y que
denominamos T ( Tree ), y por otro lado agrupamos al resto de los nodos
del grafo, conjunto que llamaremos Conjunto de Arcos No Recorridos, y
que denominaremos B ( Back ), el conjunto T forma un árbol que incluye
todos los vértices del grafo, y por lo tango lo llamaremos Arbol Incluido
el el Grafo.
*---* *---*
| 1 | | 1 |
*---* *---*
| | |
+-------+ +-------+ +-------+
| | |
*---* *---* *---* *---*
| 2 | | 3 | | 2 | | 3 |
*---* *---* *---* *---*
| | | | | | |
+--+ +--+ +--+ +--+ +--+ +--+ +--+
| | | | | | |
*---* *---* *---* *---* *---* *---* *---* *---*
| 4 | | 5 | | 6 | | 7 | | 4 | | 5 | | 6 | | 7 |
*---* *---* *---* *---* *---* *---* *---* *---*
| | | |
| +---+ +---+ |
+----------+| | +----------+
|| | |
*---* *---*
| 8 | | 8 |
*---* *---*
DFS (1) Spanning Tree del Grafo 8 BFS (1) Spanning Tree del Grafo 8
*---* *---* *---* *---* *---* *---* *---* *---*
| 1 |----------| 2 | | 1 |----------| 2 | | 1 | | 2 | | 1 |----------| 2 |
*---* *---* *---* *---* *---* *---* *---* *---*
| \ / | | | | / |
| \ /----/ | | | | /----/ |
| / | | | | / |
| / \----\ | | | | / |
| / \ | | | | / |
*---* *---* *---* *---* *---* *---* *---* *---*
| 3 |----------| 4 | | 3 | | 4 | | 3 |----------| 4 | | 3 |----------| 4 |
*---* *---* *---* *---* *---* *---* *---* *---*
Grafo 10 Spanning Tree 1 Spanning Tree 2 Spanning Tree 3
Arbol Completo del Grafo 10 del Grafo 10 del Grafo 10
*---* 16 *---* *---* 16 *---* *---* 16 *---* *---* 16 *---*
| 1 |---------| 2 | | 1 |---------| 2 | | 1 |---------| 2 | | 1 |---------| 2 |
*---* *---* *---* *---* *---* *---* *---* *---*
| \21 /11| \5 /11| \5 | \5 | \5
| \*---*/ | \*---* *---*/ | \*---* | *---* \*---* | *---* \*---*
19| | 6 | |6 | 3 | | 6 | |6 | 3 | 19| | 6 | | 3 | 19| | 6 | | 3 |
| /*---*\ | /*---* *---* | *---* | *---* *---* | *---*\ /*---*
| /33 \14| /10 | | /33 | \14 /10
*---* *---* *---* *---* *---*/ *---* *---* *---*
| 5 |---------| 4 | | 5 |---------| 4 | | 5 |---------| 4 | | 5 | | 4 |
*---* 18 *---* *---* 18 *---* *---* 18 *---* *---* *---*
Sumatoria = 56 Sumatoria = 91 Sumatoria = 64
Grafo 11 Spanning Tree 1 Spanning Tree 2 Spanning Tree 3
Arcos Ponderados del Grafo 11 del Grafo 11 del Grafo 11
Los Spanning Tree sirven para :
Implementación de Grafos con Listas de Adyacencias
import java.util.*;
public class Grafos
{ static boolean[] visitados; // Arreglo vertices visitados
public static void main(String[] args)
{ List v01 = new LinkedList(); // Listas de cada vertice
List v02 = new LinkedList(); // Listas de cada vertice
List v03 = new LinkedList(); // Listas de cada vertice
List v04 = new LinkedList(); // Listas de cada vertice
List v05 = new LinkedList(); // Listas de cada vertice
List v06 = new LinkedList(); // Listas de cada vertice
List v07 = new LinkedList(); // Listas de cada vertice
List v08 = new LinkedList(); // Listas de cada vertice
List v09 = new LinkedList(); // Listas de cada vertice
List v10 = new LinkedList(); // Listas de cada vertice
List v11 = new LinkedList(); // Listas de cada vertice
List v12 = new LinkedList(); // Listas de cada vertice
List v13 = new LinkedList(); // Listas de cada vertice
List v14 = new LinkedList(); // Listas de cada vertice
v01.add("2"); v01.add("3"); // Vertices adyacentes de cada vertice
v02.add("1"); v02.add("4"); v02.add("5"); // Vertices adyacentes de cada vertice
v03.add("1"); v03.add("6"); v03.add("7"); // Vertices adyacentes de cada vertice
v04.add("2"); v04.add("8"); // Vertices adyacentes de cada vertice
v05.add("2"); v05.add("8"); // Vertices adyacentes de cada vertice
v06.add("3"); v06.add("8"); // Vertices adyacentes de cada vertice
v07.add("3"); v07.add("8"); // Vertices adyacentes de cada vertice
v08.add("4"); v08.add("5"); v08.add("6"); v08.add("7"); // Vertices adyacentes de cada vertice
v09.add("10"); v09.add("11"); // Vertices adyacentes de cada vertice
v10.add("9"); v10.add("12"); // Vertices adyacentes de cada vertice
v11.add("9"); v11.add("12"); // Vertices adyacentes de cada vertice
v12.add("10"); v12.add("11"); // Vertices adyacentes de cada vertice
v13.add("14"); // Vertices adyacentes de cada vertice
v14.add("13"); // Vertices adyacentes de cada vertice
List[] grafo = { v01, v02, v03, v04, v05, v06, v07, v08, v09, v10, v11, v12, v13, v14 }; // Grafo representado en un arreglo
Grafos.enumerarArcos(grafo); // Invocacion metodo enumera arcos
System.out.println(" "); // Invocacion metodo Breadth First Search
Grafos.inicializarVisitados(grafo); // Invocacion metodo Breadth First Search
Grafos.breadthFirstSearch(grafo, 1); // Invocacion metodo Breadth First Search
System.out.println(" "); // Invocacion metodo Breadth First Search
Grafos.inicializarVisitados(grafo); // Invocacion metodo Breadth First Search
Grafos.breadthFirstSearch(grafo, 8); // Invocacion metodo Breadth First Search
System.out.println(" "); // Invocacion metodo Breadth First Search
Grafos.inicializarVisitados(grafo); // Invocacion metodo Breadth First Search
Grafos.breadthFirstSearch(grafo, 3); // Invocacion metodo Breadth First Search
System.out.println(" "); // Invocacion metodo Depth First Search
Grafos.inicializarVisitados(grafo); // Invocacion metodo Depth First Search
Grafos.depthFirstSearch(grafo, 1); // Invocacion metodo Depth First Search
System.out.println(" "); // Invocacion metodo Depth First Search
Grafos.inicializarVisitados(grafo); // Invocacion metodo Depth First Search
Grafos.depthFirstSearch(grafo, 8); // Invocacion metodo Depth First Search
System.out.println(" "); // Invocacion metodo Depth First Search
Grafos.inicializarVisitados(grafo); // Invocacion metodo Depth First Search
Grafos.depthFirstSearch(grafo, 3); // Invocacion metodo Depth First Search
System.out.println(" "); // Invocacion metodo Enumerar Componentes
Grafos.inicializarVisitados(grafo); // Invocacion metodo Enumerar Componentes
Grafos.enumerarComponentes(grafo); // Invocacion metodo Enumerar Componentes
}
static void inicializarVisitados(List[] grafo) // Metodo que inicializa visitados
{ Grafos.visitados = new boolean[grafo.length]; // Metodo que inicializa visitados
for ( int i = 0; i < grafo.length; i = i + 1 ) // Metodo que inicializa visitados
{ Grafos.visitados[i] = false; // Metodo que inicializa visitados
} // Metodo que inicializa visitados
}
static void enumerarArcos(List[] g) // Metodo que enumerra los arcos de un grafo
{ List visitado = null;
ListIterator iter = null;
for ( int i = 0; i < g.length; i = i + 1 )
{ visitado = g[i];
iter = visitado.listIterator(0);
while ( iter.hasNext() )
{ System.out.println("Arco del Vertice "+(i+1)+" al Vertice "+(String)iter.next());
}
}
}
static void breadthFirstSearch(List[] g, int inicial) // Metodo que navega el grafo a lo ancho
{ LinkedList avisitar = new LinkedList();
List visitado = null;
ListIterator iter = null;
String rotulo = null;
Integer entero = null;
int vertice = 0;
Grafos.visitados[inicial-1] = true;
System.out.println("Breadth First Search - Vertice "+inicial);
visitado = g[inicial-1];
iter = visitado.listIterator();
while ( iter.hasNext() )
{ rotulo = (String)iter.next();
entero = new Integer(rotulo);
vertice = entero.intValue();
avisitar.add(entero);
}
while ( !avisitar.isEmpty() )
{ entero = (Integer)avisitar.removeFirst();
vertice = entero.intValue();
if ( visitados[vertice-1] == false )
{ Grafos.visitados[vertice-1] = true;
System.out.println("Breadth First Search - Vertice "+vertice);
visitado = g[vertice-1];
iter = visitado.listIterator();
while ( iter.hasNext() )
{ rotulo = (String)iter.next();
entero = new Integer(rotulo);
vertice = entero.intValue();
avisitar.add(entero);
}
}
}
}
static void depthFirstSearch(List[] grafo, int inicial) // Metodo que navega el grafo en profundidad
{ List visitado = null;
ListIterator iter = null;
String rotulo = null;
Integer nodo = null;
int indice = 0;
if ( Grafos.visitados[inicial-1] == false )
{ System.out.println("Depth First Search - Vertice "+inicial);
}
Grafos.visitados[inicial-1] = true;
visitado = grafo[inicial-1];
iter = visitado.listIterator(0);
while ( iter.hasNext() )
{ rotulo = (String)iter.next();
nodo = new Integer(rotulo);
indice = nodo.intValue();
if ( Grafos.visitados[indice-1] == false )
{ System.out.println("Depth First Search - Vertice "+rotulo);
Grafos.visitados[indice-1] = true;
Grafos.depthFirstSearch(grafo, indice); // Recursividad del metodo
}
}
}
static void enumerarComponentes(List[] grafo) // Metodo que enumera componentes
{ int componente = 0;
for ( int i = 0; i < grafo.length; i = i + 1 )
{ componente = componente + 1;
if ( Grafos.visitados[i] == false )
{ Grafos.depthFirstSearch(grafo, i+1);
System.out.println("Enumeracion de Componentes - Componente : "+componente);
}
}
}
}
Cuya salida es :
Arco del Vertice 1 al Vertice 2
Arco del Vertice 1 al Vertice 3
Arco del Vertice 2 al Vertice 1
Arco del Vertice 2 al Vertice 4
Arco del Vertice 2 al Vertice 5
Arco del Vertice 3 al Vertice 1
Arco del Vertice 3 al Vertice 6
Arco del Vertice 3 al Vertice 7
Arco del Vertice 4 al Vertice 2
Arco del Vertice 4 al Vertice 8
Arco del Vertice 5 al Vertice 2
Arco del Vertice 5 al Vertice 8
Arco del Vertice 6 al Vertice 3
Arco del Vertice 6 al Vertice 8
Arco del Vertice 7 al Vertice 3
Arco del Vertice 7 al Vertice 8
Arco del Vertice 8 al Vertice 4
Arco del Vertice 8 al Vertice 5
Arco del Vertice 8 al Vertice 6
Arco del Vertice 8 al Vertice 7
Arco del Vertice 9 al Vertice 10
Arco del Vertice 9 al Vertice 11
Arco del Vertice 10 al Vertice 9
Arco del Vertice 10 al Vertice 12
Arco del Vertice 11 al Vertice 9
Arco del Vertice 11 al Vertice 12
Arco del Vertice 12 al Vertice 10
Arco del Vertice 12 al Vertice 11
Arco del Vertice 13 al Vertice 14
Arco del Vertice 14 al Vertice 13
Breadth First Search - Vertice 1
Breadth First Search - Vertice 2
Breadth First Search - Vertice 3
Breadth First Search - Vertice 4
Breadth First Search - Vertice 5
Breadth First Search - Vertice 6
Breadth First Search - Vertice 7
Breadth First Search - Vertice 8
Breadth First Search - Vertice 8
Breadth First Search - Vertice 4
Breadth First Search - Vertice 5
Breadth First Search - Vertice 6
Breadth First Search - Vertice 7
Breadth First Search - Vertice 2
Breadth First Search - Vertice 3
Breadth First Search - Vertice 1
Breadth First Search - Vertice 3
Breadth First Search - Vertice 1
Breadth First Search - Vertice 6
Breadth First Search - Vertice 7
Breadth First Search - Vertice 2
Breadth First Search - Vertice 8
Breadth First Search - Vertice 4
Breadth First Search - Vertice 5
Depth First Search - Vertice 1
Depth First Search - Vertice 2
Depth First Search - Vertice 4
Depth First Search - Vertice 8
Depth First Search - Vertice 5
Depth First Search - Vertice 6
Depth First Search - Vertice 3
Depth First Search - Vertice 7
Depth First Search - Vertice 8
Depth First Search - Vertice 4
Depth First Search - Vertice 2
Depth First Search - Vertice 1
Depth First Search - Vertice 3
Depth First Search - Vertice 6
Depth First Search - Vertice 7
Depth First Search - Vertice 5
Depth First Search - Vertice 3
Depth First Search - Vertice 1
Depth First Search - Vertice 2
Depth First Search - Vertice 4
Depth First Search - Vertice 8
Depth First Search - Vertice 5
Depth First Search - Vertice 6
Depth First Search - Vertice 7
Depth First Search - Vertice 1
Depth First Search - Vertice 2
Depth First Search - Vertice 4
Depth First Search - Vertice 8
Depth First Search - Vertice 5
Depth First Search - Vertice 6
Depth First Search - Vertice 3
Depth First Search - Vertice 7
Enumeracion de Componentes - Componente : 1 Corregir el programa sale 1
Depth First Search - Vertice 9
Depth First Search - Vertice 10
Depth First Search - Vertice 12
Depth First Search - Vertice 11
Enumeracion de Componentes - Componente : 2 Corregir el programa sale 9
Depth First Search - Vertice 13
Depth First Search - Vertice 14
Enumeracion de Componentes - Componente : 3 Corregir el programa sale 13
Representacion de grafos oritentada a objetos
*-----------* *-----------*
| | | |
| Object | *---* | Object |
| | | A | | |
*-----------* *---* *-----------*
| | | a| |b | | |
+-------------+ | +---------------+ +--+ +--+ +-------------+ | +---------------+
| | | V V | | |
*-----------* *-----------* *-----------* *---* *---* *-----------* *-----------* *-----------*
| | | | | | | B | | C | | | | | | |
| Grafo | | Vertice | | Arco | *---* *---* | Grafo | | Vertice | | Arco |
| | | | | | | A d | A | | | | | |
*-----------* *-----------* *-----------* | +-----+ | *-----------* *-----------* *-----------*
| | | | | | | | | +---------+ | | | | | | | |
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ c +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
| | | | | | | | | | | | | | | | | | |7| |A| |B| |C| |a| |b| |c| |d|
+-+ +-+ ... +-+ +-+ +-+ ... +-+ +-+ +-+ ... +-+ Grafo 7 +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
*---------------------------------------* *---------------------------------------* *---------------------------------------*
| | | | | |
| *------* | | *------* | | *---* |
| | | Nombre del vertice | | | | Nombre del arco | | | | Nombre del grafo |
| *------* | | *------* | | *---* |
| | | | | |
| *---------------* | | *---------------* | | |
| | | | | | Datos del vertice | | | | | | | Datos del arco | | *------ ..... ------* Vertices |
| *---------------* | | *---------------* | | | | | | |
| | | | | *------ ..... ------* del grafo |
*---------------------------------------* | *-------* | | |
| | | | Vertices del arco | | |
Vertice | *-------* | | *---------- ..... ------* Arcos |
| | | | | | | | |
*---------------------------------------* | *---------- ..... ------* del grafo |
| |
Arco *---------------------------------------*
Grafo