Grafos Busq Anchura y Profundidad

GRAFOS
BÚSQUEDA EN ANCHURA Y EN PROFUNDIDAD

Indice:
• Definición.
• Representación
◦ Matriz de Adyacencia
◦ Lista de Adyacencia
• Búsqueda Profundidad.
• Búsqueda Anchura.
• Pseudocódigo.
• Ejemplos de uso.
• Referencias.
Definición:
En matemáticas y ciencias de la computación, un grafo es un conjunto de objetos llamados vértices
o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias
entre elementos de un conjunto. Típicamente, un grafo se representa gráficamente como un
conjunto vértices o nodos unidos por aristas, los vértices son objetos que contienen información y
las aristas son conexiones entre vértices.
Representación:
Una característica especial en los grafos es que podemos representarlos utilizando dos estructuras
de datos distintas. En los algoritmos que se aplican sobre ellos veremos que adoptaran tiempos
distintos dependiendo de la forma de representación elegida. En particular, los tiempos de ejecución
variarán en función del número de vértices y el de aristas, por lo que la utilización de una
representación u otra dependerá en gran medida de si el grado es denso o disperso.
Representación por matriz de adyacencia:

Es la forma más común de representarlo y la mas directa. Consiste en una tabla de tamaño VxV en
la que a[i][j] tendrá como valor 1 si existe una arista del nodo i al nodo j. En caso contrario, el valor
será 0. Cuando se trata de grafos ponderados en lugar 1 el valor que tomará será el peso de la arista.
Si el grafo es no dirigido hay que asegurarse de que se marca con un 1 o con el peso tanto la entrada
de a[i][j] como la entrada de a[j][i] puesto que se puede recorrer en ambos sentidos.
Representación por lista de adyacencia:

Otra forma de representar un grafo es por medio de listas que definen las aristas que conectan a los
nodos. Lo que se hace es definir una lista enlazada para cada nodo, que contendrá los nodos a los
cuales es posible acceder. Es decir, un nodo A tendrá una lista enlazada asociada en la que aparecerá
un elemento con una referencia al nodo B si A y B tienen una arista que los une. Obviamente si el
grafo es no dirigido en la lista de B aparecerá la correspondiente referencia al nodo A.
Búsqueda 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 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.
Búsqueda en anchura:
Búsqueda en anchura (en inglés BFS - Breadth First Search) es un algoritmo para recorrer o buscar
elementos en un grafo. Intuitivamente, se comienza en la raíz eligiendo algún nodo como elemento
raíz 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 grafo.
Formalmente, BFS es un algoritmo de búsqueda sin información, que expande y examina todos los
nodos de un árbol sistemáticamente para buscar una solución. El algoritmo no usa ninguna
estrategia heurística.
Pseudocódigo:
Busqueda en profundidad:
DFS(grafo G)
PARA CADA vértice u ∈ V[G] HACER
estado[u] ← NO_VISITADO
padre[u] ← NULO
tiempo ← 0
PARA CADA vértice u ∈ V[G] HACER
SI estado[u] = NO_VISITADO ENTONCES
DFS_Visitar(u,tiempo)
DFS_Visitar(nodo u, int tiempo)

estado[u] ← VISITADO
tiempo ← tiempo + 1
d[u] ← tiempo
PARA CADA v ∈ Vecinos[u] HACER
SI estado[v] = NO_VISITADO ENTONCES
padre[v] ← u
DFS_Visitar(v,tiempo)
estado[u] ← TERMINADO
tiempo ← tiempo + 1
f[u] ← tiempo
Búsqueda en anchura:
BFS(grafo G, nodo_fuente s)
{
// recorremos todos los vértices del grafo inicializándolos a NO_VISITADO,
// distancia INFINITA y padre de cada nodo NULL
for u ∈ V[G] do
{
estado[u] = NO_VISITADO;
distancia[u] = INFINITO; /* distancia infinita si el nodo no es
alcanzable */
padre[u] = NULL;
}
estado[s] = VISITADO;
distancia[s] = 0;
padre[s] = NULL;
CrearCola(Q); /* nos aseguramos que la cola está vacía */
Encolar(Q, s);
while !vacia(Q) do
{
// extraemos el nodo u de la cola Q y exploramos todos sus nodos
adyacentes
u = extraer(Q);
for v ∈ adyacencia[u] do
{
if estado[v] == NO_VISITADO then
{
estado[v] = VISITADO;
distancia[v] = distancia[u] + 1;
padre[v] = u;
Encolar(Q, v);
}
}
}
}
Ejemplos de uso:
Mediante el uso del los grafos se pueden resolver diversos problemas como por ejemplo la síntesis
de circuitos secuenciales, contadores o sistemas de apertura. Son utilizados en muchas áreas de la
Ingeniería.
Los grafos se utilizan también para modelar trayectos como el de una línea de autobús a través de
las calles de una ciudad, en el que podemos obtener caminos óptimos para el trayecto aplicando
diversos algoritmos como puede ser el algoritmo de Floyd.
Para la administración de proyectos, utilizamos técnicas como técnica de revisión y evaluación de
programas en las que se modelan los mismos utilizando grafos y optimizando los tiempos para
concretar los mismos.
La teoría de grafos también ha servido de inspiración para las ciencias sociales, en especial para
desarrollar un concepto no metafórico de red social que sustituye los nodos por los actores sociales
y verifica la posición, centralidad e importancia de cada actor dentro de la red. Esta medida permite
cuantificar y abstraer relaciones complejas, de manera que la estructura social puede representarse
gráficamente.
Por ejemplo, una red social puede representar la estructura de poder dentro de una sociedad al
identificar los vínculos (aristas), su dirección e intensidad y da idea de la manera en que el poder se
transmite y a quiénes.
Se emplea en problemas de control de producción, para proyectar redes de ordenadores, para
diseñar módulos electrónicos modernos y proyectar sistemas físicos con parámetros localizados
(mecánicos, acústicos y eléctricos).
Se usa para la solución de problemas de genética y problemas de automatización de la proyección.
Apoyo matemático de los sistemas modernos para el procesamiento de la información. Acude en las
investigaciones nucleares.
Los grafos son importantes en el estudio de la biología y hábitat. El vértice representa un hábitat y
las aristas representan los senderos de los animales o las migraciones. Con esta información, los
científicos pueden entender cómo esto puede cambiar o afectar a las especies en su hábitat.
Referencias:
Algoritmos y estructuras de datos: http://www.algoritmia.net
Wikimedia Commons: http://commons.wikimedia.org
Introduction to Algorith: http://mitpress.mit.edu/algorithms/
Enciclopedia Libre Universal:http://enciclopedia.us.es/index.php/Teor%C3%ADa_de_grafos
Wikipedia http://www.wikipedia.org

Grafos Busq Anchura y Profundidad

Cargado por

Copyright:

Formatos disponibles

Grafos Busq Anchura y Profundidad

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Grafos Busq Anchura y Profundidad

Cargado por

Copyright:

Formatos disponibles

GRAFOS

BÚSQUEDA EN ANCHURA Y EN PROFUNDIDAD

Representación por matriz de adyacencia:

Representación por lista de adyacencia:

DFS_Visitar(nodo u, int tiempo)

Algoritmos y estructuras de datos: http://www.algoritmia.net

Wikimedia Commons: http://commons.wikimedia.org

Introduction to Algorith: http://mitpress.mit.edu/algorithms/

Enciclopedia Libre Universal:http://enciclopedia.us.es/index.php/Teor%C3%ADa_de_grafos

También podría gustarte