El objetivo de los algoritmos de búsqueda es recorrer un grafo de manera que se visiten todos sus vértices, o por lo menos aquellos que sean alcanzables desde un nodo de inicio. Hay dos tipos principales de búsqueda: búsqueda en profundidad y búsqueda en amplitud.
El objetivo de la búsqueda en profundidad es avanzar en un camino de búsqueda tanto como sea posible. Este se logra a través de un proceso recursivo y una estrategia de marcado de nodos, que le permite al algoritmo saber que nodos se han visitado ya. Las marcas corresponden a colores con el siguiente significado:
La siguiente función implementa el algoritmo de búsqeda en profundidad (DFS por sus siglas en Inglés). La función recibe el grafo (G), el nodo desde el que comienza (node) y un arreglo con la información de color para cada nodo.
def DFS_Visit(G, node, color):
color[node] = 'gray'
total_marked = 1
for neighbor in G[node]:
if color[neighbor] == 'white':
total_marked += DFS_Visit(G, neighbor, color)
color[node] = 'black'
return total_marked
A continuación vamos a probar el algoritmo sobre el siguiente grafo:
# Graph construction
def make_link(G, node1, node2):
if node1 not in G:
G[node1] = {}
(G[node1])[node2] = 1
if node2 not in G:
G[node2] = {}
(G[node2])[node1] = 1
return G
edges1 = [('v', 'r'), ('r', 's'), ('s', 'w'), ('w', 't'),
('w', 'x'), ('t', 'x'), ('t', 'u'), ('x', 'y'),
('u', 'y')]
G1 = {}
for v1, v2 in edges1:
make_link(G1, v1, v2)
# Initialization of 'color' array
color = {}
for v in G1:
color[v] = 'white'
# Run DFS starting from node 's'
num_nodes = DFS_Visit(G1, 't', color)
print "Number of visited nodes:", num_nodes
print color
Number of visited nodes: 8 {'s': 'black', 'r': 'black', 'u': 'black', 't': 'black', 'w': 'black', 'v': 'black', 'y': 'black', 'x': 'black'}
Como se puede ver, la función visitó los 8 nodos del grafo y por lo tanto su color final es negro.
Podemos usar la función para determinar si hay un camino que conecte dos nodos:
def connected(G, v1, v2):
color = {}
for v in G1:
color[v] = 'white'
DFS_Visit(G, v1, color)
return color[v2] == 'black'
Vamos a probarla sobre un grafo correspondiente al anterior, pero al cual se le ha removido el arco que conecta los nodos 's' y 'w'.
edges2 = [('v', 'r'), ('r', 's'), ('w', 't'),
('w', 'x'), ('t', 'x'), ('t', 'u'), ('x', 'y'),
('u', 'y')]
G2 = {}
for v1, v2 in edges2:
make_link(G2, v1, v2)
print connected(G2, 'v', 's')
print connected(G2, 'v', 'y')
True False
Para poder calcular el camino entre dos vértices encontrado por DFS, necesitamos llevar un registro del orden en que se visitan los vértices, en particular a través de que vértice se llegó a otro vértice. Esto se llevará a cabo con una arreglo adicional, parent
, el cual indicará para cada vértice el nodo a través del cual fue alcanzado, es decir su padre.
def DFS_Visit_p(G, node, color, parent):
color[node] = 'gray'
total_marked = 1
for neighbor in G[node]:
if color[neighbor] == 'white':
parent[neighbor] = node
total_marked += DFS_Visit_p(G, neighbor, color, parent)
color[node] = 'black'
return total_marked
Para calcular el camino entre dos vértices v1
y v2
, invocamos DFS con v1
como vértice de arranque, y después usamos el arreglo parent
para calcular el camino en caso de que este exista.
def path(G, v1, v2):
color = {}
parent = {}
for v in G:
color[v] = 'white'
parent[v] = None
DFS_Visit_p(G, v1, color, parent)
pathlist = []
node = v2
while node <> None:
pathlist.append(node)
node = parent[node]
if color[v2] == 'black':
return pathlist[::-1] # los vértices en pathlist están en orden inverso, [::-1] los invierte
else:
return []
print path(G1, 't', 'r')
['t', 'x', 'w', 's', 'r']
Una componente conexa de un grafo no dirigido es un subgrafo (maximal) en el cual todos los vértices están conectados. La siguiente función calcula el número de componentes conexas.
def connected_components(G):
color = {}
parent = {}
for v in G:
color[v] = 'white'
parent[v] = None
count = 0
for v in G:
if color[v] == 'white':
count += 1
DFS_Visit_p(G, v, color, parent)
return count
edges3 = [('v', 'r'), ('r', 's'), ('w', 't'),
('w', 'x'), ('t', 'x'),
('u', 'y')]
G3 = {}
for v1, v2 in edges3:
make_link(G3, v1, v2)
print connected_components(G1)
print connected_components(G2)
print connected_components(G3)
1 2 3
La versión de DFS anterior es recursiva, sin embargo es posible formular el mismo algoritmo de una manera iterativa:
def DFS_iterative(G, node):
color = {}
parent = {}
for v in G:
color[v] = 'white'
color[node] = 'gray'
parent[node] = None
nodelist = [node]
total_marked = 1
while nodelist <> []:
u = nodelist.pop()
for neighbor in G[u].keys()[::-1]:
if color[neighbor] == 'white':
color[neighbor] = 'gray'
parent[neighbor] = u
nodelist.append(neighbor)
total_marked += 1
color[u] = 'black'
return total_marked, parent
Probemos el algoritmo en el Grafo 1 definido anteriormente:
print DFS_iterative(G1, 's')
(8, {'s': None, 'r': 's', 'u': 'y', 't': 'w', 'w': 's', 'v': 'r', 'y': 'x', 'x': 'w'})
En la búsqueda en amplitud se procesan los nodos por niveles, es decir, el primer nodo que se visita es el nodo de arranque 's', segundo los nodos que están a una distancia 1 de 's', después los nodos que están a una distancia 2 de 's' y así sucesivamente. Esto se logra con un cambio simple en el código de la búsqueda en profundidad iterativa:
def BFS_iterative(G, node):
color = {}
depth = {}
parent = {}
for v in G:
color[v] = 'white'
color[node] = 'gray'
depth[node] = 0
parent[node] = None
nodelist = [node]
total_marked = 1
while nodelist <> []:
u = nodelist[0]
nodelist.remove(nodelist[0])
for neighbor in G[u]:
if color[neighbor] == 'white':
color[neighbor] = 'gray'
depth[neighbor] = depth[u] + 1
parent[neighbor] = u
nodelist.append(neighbor)
total_marked += 1
color[u] = 'black'
return total_marked, parent, depth
print BFS_iterative(G1, 'w')
print '================================='
print DFS_iterative(G1, 'w')
(8, {'s': 'w', 'r': 's', 'u': 't', 't': 'w', 'w': None, 'v': 'r', 'y': 'x', 'x': 'w'}, {'s': 1, 'r': 2, 'u': 2, 't': 1, 'w': 0, 'v': 3, 'y': 2, 'x': 1}) ================================= (8, {'s': 'w', 'r': 's', 'u': 'y', 't': 'w', 'w': None, 'v': 'r', 'y': 'x', 'x': 'w'})