INGENIERIA EN SISTEMAS
DOCENTE: ROGERIO ORLANDO BELTRAN CASTRO
INTELIGENCIA ARTIFICIAL.
MANEJO DE GRAFOS CON JAVA
INGENIERIA EN SISTEMAS
INTELIGENCIA ARTIFICIAL. GRAFOS EN PHYTON 1
INGENIERIA EN SISTEMAS
DOCENTE: ROGERIO ORLANDO BELTRAN CASTRO
INDICE
INDICE ............................................................................................................................................................................... 2
RECORRIDO EN ANCHURA Y EN PROFUNDIDAD DE UN GRAFO REPRESENTADO POR UNA MATRIZ ... 3
RECORRIDO EN ANCHURA .......................................................................................................................................... 3
RECORRIDO EN PROFUNDIDAD ................................................................................................................................. 3
PROYECTO EN NETBEANS ........................................................................................................................................... 5
INTELIGENCIA ARTIFICIAL. GRAFOS EN PHYTON 2
INGENIERIA EN SISTEMAS
DOCENTE: ROGERIO ORLANDO BELTRAN CASTRO
Recorrido en anchura y en profundidad de
un grafo representado por una matriz
RECORRIDO EN ANCHURA
“En Ciencias de la Computación, Búsqueda en anchura (en inglés BFS – Breadth First Search) es
un algoritmo para recorrer o buscar elementos en un grafo (usado frecuentemente
sobre árboles). Intuitivamente, se comienza en la raíz (eligiendo algún nodo como elemento raíz en el
caso de un grafo) y se exploran todos los vecinos de este nodo. A continuación para cada uno de los
vecinos se exploran sus respectivos vecinos adyacentes, y así hasta que se recorra todo el árbol.”
Un recorrido en anchura se refiere a recorrer un grafo por niveles, es decir, partiendo de un nodo inicial
recorro todos sus vecinos, posteriormente los vecinos de los vecinos hasta que todos los nodos hayan
sido visitados.
RECORRIDO EN PROFUNDIDAD
“Una Búsqueda en profundidad (en inglés DFS o Depth First Search) es un algoritmo que permite
recorrer todos los nodos de un grafo o árbol (teoría de grafos) de manera ordenada, pero no uniforme.
Su funcionamiento consiste en ir expandiendo todos y cada uno de los nodos que va localizando, de
forma recurrente, en un camino concreto. Cuando ya no quedan más nodos que visitar en dicho camino,
regresa (Backtracking), de modo que repite el mismo proceso con cada uno de los hermanos del nodo
ya procesado.”
INTELIGENCIA ARTIFICIAL. GRAFOS EN PHYTON 3
INGENIERIA EN SISTEMAS
DOCENTE: ROGERIO ORLANDO BELTRAN CASTRO
Un recorrido en profundidad es que partiendo de un nodo inicial, visite toda una rama, luego otra hasta
que todos los nodos hayan sido visitados.
A continuación un ejemplo sencillo de ambos recorridos realizado en Java:
INTELIGENCIA ARTIFICIAL. GRAFOS EN PHYTON 4
INGENIERIA EN SISTEMAS
DOCENTE: ROGERIO ORLANDO BELTRAN CASTRO
PROYECTO EN NETBEANS
Creamos un proyecto
Creamos el proyecto
INTELIGENCIA ARTIFICIAL. GRAFOS EN PHYTON 5
INGENIERIA EN SISTEMAS
DOCENTE: ROGERIO ORLANDO BELTRAN CASTRO
Creamos una clase llamada Grafo
Adicionamos el siguiente código
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package practica_java;
/**
*
* @author UTS
*/
import [Link];
/**
* Clase Grafo
* @author UTS
*/
INTELIGENCIA ARTIFICIAL. GRAFOS EN PHYTON 6
INGENIERIA EN SISTEMAS
DOCENTE: ROGERIO ORLANDO BELTRAN CASTRO
public class Grafo {
public int[][] g = {{2, 1, 0, 1, 0},
{1, 2, 1, 0, 0},
{0, 1, 2, 1, 0},
{1, 0, 1, 2, 1},
{0, 0, 0, 1, 2}};
private boolean[] visitiadoAnchura = new boolean[5];
private boolean[] visitiadoProfunidad = new boolean[5];
public Grafo() {
public int[][] getG() {
return g;
public ArrayList<Integer> recorridoAnchura(int nodoI) {
//Lista donde guardo los nodos recorridos
ArrayList<Integer> recorridos = new ArrayList<Integer>();
//El nodo inicial ya está visitado
visitiadoAnchura[nodoI] = true;
//Cola de visitas de los nodos adyacentes
ArrayList<Integer> cola = new ArrayList<Integer>();
//Se lista el nodo como ya recorrido
[Link](nodoI);
//Se agrega el nodo a la cola de visitas
INTELIGENCIA ARTIFICIAL. GRAFOS EN PHYTON 7
INGENIERIA EN SISTEMAS
DOCENTE: ROGERIO ORLANDO BELTRAN CASTRO
[Link](nodoI);
//Hasta que visite todos los nodos
while (![Link]()) {
int j = [Link](0); //Se saca el primero nodo de la cola
//Se busca en la matriz que representa el grafo los nodos adyacentes
for (int i = 0; i < [Link]; i++) {
//Si es un nodo adyacente y no está visitado entonces
if (g[j][i] == 1 && !visitiadoAnchura[i]) {
[Link](i);//Se agrega a la cola de visitas
[Link](i);//Se marca como recorrido
visitiadoAnchura[i] = true;//Se marca como visitado
return recorridos;//Devuelvo el recorrido del grafo en anchura
public ArrayList<Integer> recorridoProfunidad(int nodoI) {
//Lista donde guardo los nodos recorridos
ArrayList<Integer> recorridos = new ArrayList<Integer>();
visitiadoProfunidad[nodoI] = true;//El nodo inicial ya está visitado
//Cola de visitas de los nodos adyacentes
ArrayList<Integer> cola = new ArrayList<Integer>();
[Link](nodoI);//Listo el nodo como ya recorrido
[Link](nodoI);//Se agrega el nodo a la cola de visitas
INTELIGENCIA ARTIFICIAL. GRAFOS EN PHYTON 8
INGENIERIA EN SISTEMAS
DOCENTE: ROGERIO ORLANDO BELTRAN CASTRO
while (![Link]()) {//Hasta que visite todos los nodos
int j = [Link](0);//Se saca el primer nodo de la cola
//Se busca en la matriz que representa el grafo los nodos adyacentes
for (int i = 0; i < [Link]; i++) {
//Si es un nodo adyacente y no está visitado entonces
if (g[j][i] == 1 && !visitiadoProfunidad[i]) {
[Link](i);//Se agrega a la cola de visita
//Se recorren los hijos del nodo actual de visita y se agrega el recorrido al la lista
[Link](recorridoProfunidad(i));
visitiadoProfunidad[i] = true;//Se marca como visitado
return recorridos;//Se devuelve el recorrido del grafo en profundidad
}
}
El programa principal tiene el siguiente código
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package practica_java;
import [Link];
/**
*
* @author FLIA BELTRAN MALDONA
*/
public class Practica_Java {
INTELIGENCIA ARTIFICIAL. GRAFOS EN PHYTON 9
INGENIERIA EN SISTEMAS
DOCENTE: ROGERIO ORLANDO BELTRAN CASTRO
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Grafo g=new Grafo();
ArrayList<Integer> enAnchura=[Link](0);//Nodo inicial 0
[Link]("Recorrido en anchura de un grafo representado como matriz: ");
for(int i=0;i<[Link]();i++){
[Link](""+[Link](i)+"");
ArrayList<Integer> enProfundidad=[Link](0);//Nodo inicial 0
[Link]("");
[Link]("Recorrido en profundidad de un grafo representado como matriz: ");
for(int i=0;i<[Link]();i++){
[Link](""+[Link](i)+"");
INTELIGENCIA ARTIFICIAL. GRAFOS EN PHYTON 10
