Gráficos en Java: búsqueda en anchura (BFS)

Los gráficos son una forma conveniente de almacenar ciertos tipos de datos. El concepto fue portado de las matemáticas y apropiado para las necesidades de la informática. Debido a...

Introducción

Los gráficos son una forma conveniente de almacenar ciertos tipos de datos. El concepto fue portado de las matemáticas y apropiado para las necesidades de la informática.

Debido al hecho de que muchas cosas se pueden representar como gráficos, el recorrido de gráficos se ha convertido en una tarea común, especialmente utilizada en ciencia de datos y aprendizaje automático.

Búsqueda en amplitud

Breadth First Search (BFS) visita "capa por capa". Esto significa que en un gráfico, como se muestra a continuación, primero visita todos los elementos secundarios del nodo inicial. Estos niños son tratados como la "segunda capa".

A diferencia de Búsqueda en profundidad primero (DFS), BFS no recorre agresivamente una rama hasta llegar al final, sino cuando iniciamos la búsqueda desde un nodo, visita todos los vecinos no visitados de ese nodo antes de proceder a todos los vecinos no visitados de otro nodo:

Implementación

Usaremos gráficos implementados a través de una lista de adyacencia, como usamos para DFS. Además, necesitamos agregar el atributo visited junto con los métodos visit() y univisit() a nuestra clase Node:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
public class Node {
    int n;
    String name;
    boolean visited;

    Node(int n, String name) {
        this.n = n;
        this.name = name;
        visited = false;
    }

    void visit() {
        visited = true;
    }

    void unvisit() {
        visited = false;
    }
}

Ahora, definamos un Gráfico:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
public class Graph {

    // Each node maps to a list of all his neighbors
    private HashMap<Node, LinkedList<Node>> adjacencyMap;
    private boolean directed;

    public Graph(boolean directed) {
        this.directed = directed;
        adjacencyMap = new HashMap<>();
    }

    // ...
}

Ahora, agreguemos el método addEdge(). Usaremos dos métodos, un método auxiliar y el método real.

En el método auxiliar, también haremos una verificación de posibles bordes duplicados. Antes de agregar un borde entre A y B, primero lo eliminaremos y solo luego lo agregaremos. Si existía (estamos agregando un borde duplicado), se eliminó y después de agregarlo nuevamente, solo hay uno.

Sin embargo, si no existiera, eliminar un borde inexistente resultará en una NullPointerException, por lo que estamos introduciendo una copia temporal de la lista:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public void addEdgeHelper(Node a, Node b) {
    LinkedList<Node> tmp = adjacencyMap.get(a);

    if (tmp != null) {
        tmp.remove(b);
    }
    else tmp = new LinkedList<>();
    tmp.add(b);
    adjacencyMap.put(a,tmp);
}

public void addEdge(Node source, Node destination) {

    // We make sure that every used node shows up in our .keySet()
    if (!adjacencyMap.keySet().contains(source))
        adjacencyMap.put(source, null);

    if (!adjacencyMap.keySet().contains(destination))
        adjacencyMap.put(destination, null);

    addEdgeHelper(source, destination);

    // If a graph is undirected, we want to add an edge from destination to source as well
    if (!directed) {
        addEdgeHelper(destination, source);
    }
}

Finalmente, tendremos los métodos auxiliares printEdges(), hasEdge() y resetNodesVisited(), que son bastante sencillos:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
public void printEdges() {
    for (Node node : adjacencyMap.keySet()) {
        System.out.print("The " + node.name + " has an edge towards: ");
        for (Node neighbor : adjacencyMap.get(node)) {
            System.out.print(neighbor.name + " ");
        }
        System.out.println();
    }
}

public boolean hasEdge(Node source, Node destination) {
    return adjacencyMap.containsKey(source) && adjacencyMap.get(source).contains(destination);
}

public void resetNodesVisited(){
    for(Node node : adjacencyMap.keySet()){
        node.unvisit();
    }
}

Examinemos el algoritmo BFS en el siguiente gráfico no dirigido:

1
2
3
4
Node 0 has neighbors: 1, 3, 2
Node 1 has neighbors: 0
Node 2 has neighbors: 3, 0
Node 3 has neighbors: 2, 0

Podemos elegir cualquier nodo desde el que comenzar, así que comencemos con 1. Repetimos el proceso de agregar y eliminar nodos de la cola hasta que la cola esté vacía.

Una cola es una estructura de datos FIFO (primero en entrar, primero en salir). Funciona como una cola de la vida real, por lo que las entradas se procesan (eliminan de la cola) una por una en el orden en que se agregaron.

Esta es una estructura de datos muy conveniente para BFS ya que queremos procesar los nodos en el orden en que los visitamos, asegurándonos de procesar primero los nodos "más cercanos" al nodo inicial.

Dado que se agregan a la cola antes de que se agreguen a la cola los nodos "más" alejados del nodo inicial, sabemos que los más cercanos se procesarán primero.

  1. Empezamos por tener una cola que contiene solo el nodo 1

  1. Elimina el primer elemento de la cola, en este caso el 1, márcalo como visitado
  2. Agregue todos los vecinos no visitados de 1 a la cola (solo 0)

  1. Elimina el primer elemento de la cola, en este caso 0, márcalo como visitado
  2. Agregue todos los vecinos no visitados de 0 a la cola (nodos 3 y 2, 1 ya se marcó como visitado)

  1. Elimina el primer elemento de la cola, en este caso el 3, márcalo como visitado
  2. Agregue los 3 vecinos no visitados a la cola (no hay ninguno)

  1. Elimina el primer elemento de la cola, en este caso el 2, márcalo como visitado
  2. Agregue todos los vecinos no visitados de 2 a la cola (nuevamente, no hay ninguno)
  3. La cola ahora está vacía, BFS ha terminado

Nuestros nodos se visitan en el orden 1-0-3-2. Debería ser obvio que el conjunto de pasos 2-3, 4-5, 6-7 y 8-9 son iguales y que el paso 10 es nuestra condición de terminación del bucle. Visto de esta manera, debería ser fácil escribir código para nuestro método breadthFirstSearch(Node node).

Hay varios tipos de implementaciones de Queue en Java, pero usaremos una LinkedList en su lugar, ya que proporciona todos los métodos necesarios.

Estamos agregando el siguiente método a nuestra clase Graph:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
void breadthFirstSearch(Node node) {

    // Just so we handle receiving an uninitialized Node, otherwise an
    // exception will be thrown when we try to add it to queue
    if (node == null)
        return;

    // Creating the queue, and adding the first node (step 1)
    LinkedList<Node> queue = new LinkedList<>();
    queue.add(node);

    while (!queue.isEmpty()) {
        Node currentFirst = queue.removeFirst();

        // In some cases we might have added a particular node more than once before
        // actually visiting that node, so we make sure to check and skip that node if we have
        // encountered it before
        if (currentFirst.isVisited())
            continue;

        // Mark the node as visited
        currentFirst.visit();
        System.out.print(currentFirst.name + " ");

        LinkedList<Node> allNeighbors = adjacencyMap.get(currentFirst);

        // We have to check whether the list of neighbors is null before proceeding, otherwise
        // the for-each loop will throw an exception
        if (allNeighbors == null)
            continue;

        for (Node neighbor : allNeighbors) {
            // We only add unvisited neighbors
            if (!neighbor.isVisited()) {
                queue.add(neighbor);
            }
        }
    }
    System.out.println();
}

Ahora creamos nuestro gráfico de ejemplo en código y verificamos si nuestro método funciona como se esperaba:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public class GraphShow {
    public static void main(String[] args) {

        Graph graph = new Graph(false);
        Node a = new Node(0, "0");
        Node b = new Node(1, "1");
        Node c = new Node(2, "2");
        Node d = new Node(3, "3");
        Node e = new Node(4, "4");

        graph.addEdge(a,d);
        graph.addEdge(a,b);
        graph.addEdge(a,c);
        graph.addEdge(c,d);

        graph.breadthFirstSearch(b);
    }
}

Producción:

1
1 0 3 2

Si lee el artículo de DFS, puede recordar que nos encontramos con una situación en la que, en un gráfico no conectado, no se imprimirían todos los nodos, ya que el algoritmo pasaría por todos los nodos que pudiera y luego se detendría.

Lo mismo sucede con BFS, y esto también puede suceder cuando los gráficos están dirigidos, a veces no podemos llegar a todos los nodos. A veces, este es el comportamiento que buscamos, pero a veces queremos que se visiten todos los nodos.

Haremos lo mismo que hicimos en DFS, es decir, seguiremos llamando a BFS mientras haya nodos no visitados. Crearemos un nuevo método breadthFirstSearchModified(Node node) que haga esto por nosotros:

1
2
3
4
5
6
7
8
9
void breadthFirstSearchModified(Node node) {
    breadthFirstSearch(node);

    for (Node n : adjacencyMap.keySet()) {
        if (!n.isVisited()) {
            breadthFirstSearch(n);
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class GraphShow {
    public static void main(String[] args) {

        Graph graph = new Graph(false);
        Node a = new Node(0, "0");
        Node b = new Node(1, "1");
        Node c = new Node(2, "2");
        Node d = new Node(3, "3");
        Node e = new Node(4, "4");

        graph.addEdge(a,d);
        graph.addEdge(a,b);
        graph.addEdge(c,e);

        System.out.println("Using the unmodified version of BFS we get:");
        graph.breadthFirstSearch(a);

        graph.resetNodesVisited();
        System.out.println("Using the modified version of BFS we get:");
        graph.breadthFirstSearchModified(a);
    }
}

Producción:

1
2
3
4
5
Using the unmodified version of BFS we get:
0 3 1
Using the modified version of BFS we get:
0 3 1
4 2

También hay algo llamado búsqueda BFS "bidireccional". Esto es útil cuando queremos encontrar el camino más corto entre dos vértices (nodos).

Esto se logra ejecutando simultáneamente (en diferentes subprocesos) un BFS desde el nodo de inicio y el nodo de destino. Esto, en teoría, encuentra la ruta más corta entre dos nodos dos veces más rápido que ejecutar BFS solo desde el nodo inicial.

Nota: Igual que con DFS, si queremos pasar por los vecinos en un orden particular (en lugar del orden en que se agregaron los bordes), podemos usar una PriorityQueue en lugar de una LinkedList para la lista de vecinos.

The el codigo es el mismo, we just have to implement Comparable and add a compareTo() method to our Node class.

Conclusión

Los gráficos son una forma conveniente de almacenar ciertos tipos de datos. El concepto fue portado de las matemáticas y apropiado para las necesidades de la informática.

Debido al hecho de que muchas cosas se pueden representar como gráficos, el recorrido de gráficos se ha convertido en una tarea común, especialmente utilizada en ciencia de datos y aprendizaje automático.

Breadth-First Search es uno de los pocos algoritmos de recorrido de gráficos y visita los nodos "capa por capa". A diferencia de la búsqueda primero en profundidad, BFS no recorre agresivamente una rama hasta que llega al final, sino que cuando comenzamos la búsqueda desde un nodo, visita todos los vecinos no visitados de ese nodo antes de proceder a todos los vecinos no visitados de otro nodo. o nodo.