Gráficos en Java: búsqueda en profundidad (DFS)

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 profundidad primero {# depthfirstsearch}

Búsqueda primero en profundidad (DFS) busca lo más lejos posible a lo largo de una rama y luego retrocede para buscar lo más lejos posible en la siguiente rama. Esto significa que en el gráfico anterior, comienza con el primer vecino y continúa hacia abajo en la línea hasta donde sea posible:

Una vez que llega al nodo final de esa rama (1), retrocede hasta el primer nodo donde se enfrentó a la posibilidad de cambiar de rumbo (5) y visita toda esa rama, que en nuestro caso es el nodo (2).

Luego retrocede nuevamente al nodo (5) y como ya ha visitado los nodos (1) y (2), retrocede a (3) y se redirige a la siguiente rama (8).

Implementación

Ya que sabemos cómo representar gráficos en código a través de listas de adyacencia y matrices, hagamos un gráfico y recorrámoslo usando DFS. Los gráficos con los que trabajaremos son lo suficientemente simples como para que no importe la implementación que elijamos.

Sin embargo, para proyectos reales, en la mayoría de los casos, las listas de adyacencia serán una mejor opción, por lo que representaremos el gráfico como una lista de adyacencia.

Queremos visitar todos nuestros nodos una vez, como se ve en la animación de arriba, se vuelven rojos una vez visitados, por lo que no los visitamos más. Para hacer esto en el código, introduciremos un indicador visitado:

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

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

    // Two new methods we'll need in our traversal algorithms
    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 el borde ya existía, esto nos impide agregar un borde duplicado. Si aún no había un borde allí, solo tenemos un borde entre los dos nodos.

Si el borde no existiera, eliminar un borde inexistente dará como resultado 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();
    }
}

También agregaremos el método depthFirstSearch(Node node) a nuestra clase Graph que hace lo siguiente:

  • Si node.visited == true, simplemente regresa
  • Si aún no ha sido visitado, haga lo siguiente:
    • Find the first unvisited neighbor newNode of node and call depthFirstSearch(newNode)
    • Repeat the process for all unvisited neighbors

Ilustremos esto con un ejemplo:

1
2
3
4
Node A is connected with node D
Node B is connected with nodes D, C
Node C is connected with nodes A, B
Node D is connected with nodes B
  1. Todos los nodos están sin visitar al principio (node.visited == false)
  2. Llame a . depthFirstSeach () con un nodo arbitrario como nodo de inicio, digamos depthFirstSearch (B)
  3. marcar B como visitado
  4. ¿B tiene vecinos no visitados? Sí -> el primer nodo no visitado es D, así que llame a profundidadPrimeraBúsqueda(D)
  5. marcar D como visitado
  6. ¿Tiene D vecinos no visitados? No -> (B ya ha sido visitado) regresar
  7. ¿B tiene vecinos no visitados? Sí -> el primer nodo no visitado es C, así que llame a depthFirstSearch (C)
  8. marcar C como visitado
  9. ¿C tiene vecinos no visitados? Sí -> el primer nodo no visitado es A, así que llame a depthFirstSearch(A)\
    1. mark A as visited\
    2. Does A have any unvisited neighbors? No. -> return
  10. ¿C tiene vecinos no visitados? No -> regresar
  11. ¿B tiene vecinos no visitados? No -> regresar

Llamar a DFS en nuestro gráfico nos daría el recorrido B,D,C,A (el orden de visita). Cuando el algoritmo se escribe así, es fácil traducirlo a código:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
public void depthFirstSearch(Node node) {
    node.visit();
    System.out.print(node.name + " ");

    LinkedList<Node> allNeighbors = adjacencyMap.get(node);
    if (allNeighbors == null)
        return;

    for (Node neighbor : allNeighbors) {
        if (!neighbor.isVisited())
            depthFirstSearch(neighbor);
    }
}

Nuevamente, así es como se ve cuando se traduce a una animación:

DFS a veces se denomina un recorrido de gráfico "agresivo" porque llega tan lejos como es posible a través de una "rama". Como podemos ver en el gif anterior, cuando DFS encuentra el nodo 25, fuerza la rama 25 - 12 - 6 - 4 hasta que no puede avanzar más. Solo entonces el algoritmo regresa para verificar si hay otros vecinos no visitados de los nodos anteriores, comenzando con los visitados más recientemente.

Nota: Es posible que tengamos un gráfico no conectado. Un gráfico no conectado es un gráfico que no tiene una ruta entre dos nodos.

En este ejemplo, se visitarían los nodos 0, 1 y 2 y la salida mostraría estos nodos e ignoraría por completo los nodos 3 y 4.

Algo similar sucedería si hubiéramos llamado a depthFirstSearch (4), solo que esta vez se visitarían 4 y 3 mientras que 0, 1 y 2 no. La solución a este problema es seguir llamando a DFS mientras haya nodos no visitados.

Esto se puede hacer de varias maneras, pero podemos hacer otra ligera modificación a nuestra clase Graph para manejar este problema. Agregaremos un nuevo método depthFirstSearchModified (nodo de nodo):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void depthFirstSearchModified(Node node) {
    depthFirstSearch(node);

    for (Node n : adjacencyMap.keySet()) {
        if (!n.isVisited()) {
            depthFirstSearch(n);
        }
    }
}

public void depthFirstSearch(Node node) {
    node.visit();
    System.out.print(node.name + " ");

    LinkedList<Node> allNeighbors = adjacencyMap.get(node);
        if (allNeighbors == null)
            return;

    for (Node neighbor : allNeighbors) {
        if (!neighbor.isVisited())
            depthFirstSearch(neighbor);
    }
}
 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 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,b);
        graph.addEdge(a,c);
        graph.addEdge(c,b);
        graph.addEdge(e,d);

        System.out.println("If we were to use our previous DFS method, we would get an incomplete traversal");
        graph.depthFirstSearch(b);
        graph.resetNodesVisited(); // All nodes are marked as visited because of
                                   // the previous DFS algorithm so we need to
                                   // mark them all as not visited

        System.out.println();
        System.out.println("Using the modified method visits all nodes of the graph, even if it's unconnected");
        graph.depthFirstSearchModified(b);
    }
}

Lo que nos da la salida:

1
2
3
4
If we were to use our previous DFS method, we would get an incomplete traversal
1 0 2
Using the modified method visits all nodes of the graph, even if it's unconnected
1 0 2 4 3

Ejecutemos nuestro algoritmo en un ejemplo más:

 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
public class GraphShow {
    public static void main(String[] args) {

        Graph graph = new Graph(true);
        Node zero = new Node(0, "0");
        Node one = new Node(1, "1");
        Node two = new Node(2, "2");
        Node three = new Node(3, "3");
        Node four = new Node(4, "4");
        Node five = new Node(5, "5");
        Node six = new Node(6, "6");
        Node seven = new Node(7, "7");
        Node eight = new Node(8, "8");

        graph.addEdge(one,zero);
        graph.addEdge(three,one);
        graph.addEdge(two,seven);
        graph.addEdge(two,four);
        graph.addEdge(five,two);
        graph.addEdge(five,zero);
        graph.addEdge(six,five);
        graph.addEdge(six,three);
        graph.addEdge(six,eight);
        graph.addEdge(seven,five);
        graph.addEdge(seven,six);
        graph.addEdge(seven,eight);

        graph.depthFirstSearch(seven);
    }
}

Esto nos da la salida:

1
7 5 2 4 0 6 3 1 8

Vecinos pedidos

Otra cosa "divertida" que podríamos querer agregar es un orden en el que se enumeran los vecinos para cada nodo. Podemos lograr esto usando una estructura de datos de almacenamiento dinámico (PriorityQueue en Java) en lugar de una LinkedList para vecinos e implementando un método compareTo() en nuestra clase Nodo para que Java sepa cómo ordenar nuestros objetos:

1
2
3
4
5
6
7
8
public class Node implements Comparable<Node> {

    // Same code as before...

    public int compareTo(Node node) {
        return this.n - node.n;
    }
}
1
2
3
class Graph {
    // Replace all occurrences of LinkedList with PriorityQueue
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class GraphShow {
    public static void main(String[] args) {

        GraphAdjacencyList graph = new GraphAdjacencyList(true);
        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,e);
        graph.addEdge(a,d);
        graph.addEdge(a,b);
        graph.addEdge(a,c);

        System.out.println("When using a PriorityQueue, it doesn't matter in which order we add neighbors, they will always be sorted");
        graph.printEdges();
        System.out.println();

        graph.depthFirstSearchModified(a);
        graph.resetNodesVisited();
    }
}
1
2
3
4
When using a PriorityQueue, it doesn't matter in which order we add neighbors, they will always be sorted
The 0 has an edge towards: 1 2 3 4

0 1 2 3 4

Si no usáramos un PriorityQueue, la salida DFS habría sido 0,4,3,1,2.

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.

Depth-First Search (DFS) es uno de los pocos algoritmos transversales de gráficos y busca lo más lejos posible a lo largo de una rama y luego retrocede para buscar lo más lejos posible en la siguiente rama.