java - profundidad - bfs y dfs

Encuentre el número de rutas únicas a un nodo específico usando la primera búsqueda de profundidad

Question

Tengo un gráfico dirigido con los vértices 123456. Utilizando una primera búsqueda en profundidad, si quería poder encontrar el número de rutas únicas de 1-4 (por ejemplo), ¿cómo podría hacerlo? Aquí está mi DFS actual.

private final Map<Character, Node> mNodes;
private final List<Edge> mEdges;
private List<Node> mVisited = new ArrayList<>();
int weight;
int numberOfPaths;

public DepthFirstSearch(Graph graph){
    mNodes = graph.getNodes();
    mEdges = new ArrayList<>(graph.getEdges());
    for(Node node : mNodes.values()){
        node.setVisited(false);
    }
}

public void depthFirstSearch(Node source){

    source.setVisited(true);
    List<Edge> neighbours = source.getNeighbouringEdges(mEdges);
    for(Edge edge : neighbours){
        System.out.println(edge.getFrom().getName()+"-"+edge.getTo().getName());
        if(!edge.getTo().isVisited()){

            mVisited.add(edge.getTo());
            weight += edge.getWeight();
            depthFirstSearch(edge.getTo());

        }
    }

}

Answer 1

Realmente depende de los bordes de tu gráfica. Si todos sus vértices están conectados entre sí, sería muy simple porque obtendría el mismo número de rutas cada vez (1-> 4, 1-> 2-> 4, 1-> 3-> 4, 1 -> 5-> 4, ..., 1-> 6-> 5-> 3-> 2-> 4 [yendo con las rutas de 1 a 4 ejemplo). Sería muy similar dado cualquier camino n-> m (dado el hecho de que no desea ciclos), y habría el mismo número de rutas cada vez. Sin embargo, si hay vértices que no están conectados a otros vértices, es donde se pondría interesante. Probablemente quieras usar un algoritmo de Djikstra modificado que luego te daría las diferentes respuestas (estoy suponiendo que estás buscando) para un número de rutas únicas.

Answer 2

Como los ciclos no están permitidos, tiene un DAG ( gráfico acyclid dirigido ).

Estas son algunas preguntas relacionadas con este tema:

• Número de rutas entre dos nodos en un DAG
• Tipo topológico para encontrar el número de caminos para t

Básicamente, la idea es obtener un tipo topológico del DAG , luego iterar los nodos comenzando desde el nodo de destino hacia atrás hasta el nodo fuente, calculando cuántas rutas hay desde ese nodo.

Como la matriz no tiene ciclos y los nodos están ordenados topológicamente, cuando visita un nodo, todos los nodos a los que se puede acceder desde ese nodo aparecen más tarde en el orden y ya se han visitado. Por lo tanto, el recuento de rutas desde un nodo hasta el objetivo es la suma de los recuentos de los nodos adyacentes.

Modelos:

class Graph
{
    private List<Node> nodes;
    private List<Edge> edges;

    public Graph() {
        nodes = new ArrayList<>();
        edges = new ArrayList<>();
    }

    public List<Node> getNodes() { return nodes; }    
    public List<Edge> getEdges() { return edges; }

    public void addNode(Node node) { nodes.add(node); }    
    public void addEdge(Edge edge) {
        edges.add(edge);        
        edge.getFrom().addEdge(edge);
        edge.getTo().addEdge(edge);
    }
}

class Node
{
    private List<Edge> outgoings, incomings;

    public Node() {
        outgoings = new ArrayList<>();
        incomings = new ArrayList<>();
    }

    public List<Edge> getOutgoings() { return outgoings; }    
    public List<Edge> getIncomings() { return incomings; }

    public void addEdge(Edge edge) {
        if (edge.getFrom() == this) outgoings.add(edge);
        if (edge.getTo() == this) incomings.add(edge);
    }
}

class Edge
{
    private Node from, to;

    public Edge(Node from, Node to) {
        this.from = from;
        this.to = to;
    }

    public Node getFrom() { return from; }    
    public Node getTo() { return to; }
}

Algoritmo:

static int countPaths(Graph graph, Node source, Node target)
{
    List<Node> nodes = topologicalSort(graph);
    int[] counts = new int[nodes.size()];

    int srcIndex = nodes.indexOf(source);
    int tgtIndex = nodes.indexOf(target);

    counts[tgtIndex] = 1;

    for (int i = tgtIndex; i >= srcIndex; i--) {
        for (Edge edge : nodes.get(i).getOutgoings())
            counts[i] += counts[nodes.indexOf(edge.getTo())];
    }

    return counts[srcIndex];
}

static List<Node> topologicalSort(Graph g)
{
    List<Node> result = new ArrayList<>();
    Set<Node> visited = new HashSet<>();
    Set<Node> expanded = new HashSet<>();

    for (Node node: g.getNodes())
        explore(node, g, result, visited, expanded);

    return result;
}

static void explore(Node node, Graph g, List<Node> ordering, Set<Node> visited, Set<Node> expanded) {
    if (visited.contains(node)) {            
        if (expanded.contains(node)) return;
        throw new IllegalArgumentException("Graph contains a cycle.");
    }

    visited.add(node);

    for (Edge edge: node.getIncomings())
        explore(edge.getFrom(), g, ordering, visited, expanded);

    ordering.add(node);
    expanded.add(node);
}

Uso:

Graph g = new Graph();

Node a = new Node();
Node b = new Node();
Node c = new Node();
Node d = new Node();
Node e = new Node();

Edge ab = new Edge(a, b);
Edge bc = new Edge(b, c);
Edge cd = new Edge(c, d);
Edge ad = new Edge(a, d);
Edge ae = new Edge(a, e);
Edge ed = new Edge(e, d);
Edge be = new Edge(b, e);
Edge ec = new Edge(e, c);

g.addNode(a);
g.addNode(b);
g.addNode(c);
g.addNode(d);
g.addNode(e);

g.addEdge(ab);
g.addEdge(bc);
g.addEdge(cd);
g.addEdge(ad);
g.addEdge(ae);
g.addEdge(ed);
g.addEdge(be);
g.addEdge(ec);

int count = countPaths(g, a, d); 

//count: 6

// Paths:
//1. A->B->C->D
//2. A->D
//3. A->E->D
//4. A->B->E->C->D
//5. A->B->E->D
//6. A->E->C->D

Pero, si quieres hacerlo usando un BFS , puedes intentar hacer un retroceso restableciendo los nodos visitados:

static int countPaths(Graph graph, Node source, Node target)
{
    Set<Node> visiteds = new HashSet<>();
    return BFS(source, target, visiteds);
}

static int BFS(Node current, Node target, Set<Node> visiteds) {
    if (current == target) return 1;
    else
    {
        int count = 0;
        visiteds.add(current);

        for (Edge edge : current.getOutgoings())
            if (!visiteds.contains(edge.getTo()))
                count += BFS(edge.getTo(), target, visiteds);

        visiteds.remove(current);
        return count;
    }
}    

Sin embargo, para aumentar el rendimiento, puede implementar algún tipo de memorización :

static int countPaths(Graph graph, Node source, Node target)
{
    Set<Node> visiteds = new HashSet<>();
    Map<Node, Integer> memoize = new HashMap<>();

    for (Node node : graph.getNodes())
        memoize.put(node, -1);

    memoize.put(target, 1);

    return BFS(source, visiteds, memoize);
}

static int BFS(Node current, Set<Node> visiteds, Map<Node, Integer> memoize) {
    if (memoize.get(current) != -1) return memoize.get(current);
    else
    {
        int count = 0;
        visiteds.add(current);

        for (Edge edge : current.getOutgoings())
            if (!visiteds.contains(edge.getTo()))
                count += BFS(edge.getTo(), visiteds, memoize);

        visiteds.remove(current);
        memoize.put(current, count);
        return count;
    }
}  

Answer 3

(Asumiendo un gráfico acíclico dirigido)

Todo lo que necesita hacer es ejecutar su DFS y contar cada ruta descubierta que conduzca al nodo de destino.

El error en su código es que su estado setVisited() y isVisited() es global. Esto significa que cada vez que se encuentre con el nodo C lo marcará como visitado y se mantendrá marcado para toda la ejecución de DFS, incluso para rutas donde todavía no se ha visitado.

Un ejemplo de ejecución DFS (dado gráfico simple A -> B , B -> C , A -> C ):

• (Paso 1 - ruta A ) Visita A , marca A visitada

• (Paso 1.1 - ruta A -> B ) Visita B , marca B visitada

• (Paso 1.1.1 - ruta A -> B -> C ) Visite C , marca C visitada

• (Paso 1.2 - ruta A -> C ) Aquí omite esta ruta ya que C está marcado como visitado desde el paso 1.1.1 (lo cual es incorrecto)

Debe rastrear los nodos visitados correctamente, por ejemplo:

• confíe en la persona que llama que el gráfico de entrada es realmente acíclico y no rastrea los nodos visitados en absoluto (ya que no hay forma de visitar un solo nodo dos veces en un gráfico acíclico). Usted corre el riesgo de que su programa ingrese recursión infinita por entrada incorrecta

• use detección de ciclo más simple / más barata. Puede rastrear la profundidad de recursión y cuando se vuelve más profundo que el número total de nodos en el gráfico, se genera una excepción

• restablecer el estado del nodo visitado inmediatamente después de la visita (esto es lo que @Arturo Menchaca sugiere en su gran respuesta)

• mantener un estado visitado por separado para cada ruta que se procesa

Ejemplo de código java que rastrea los nodos visitados en una lista (de esta manera puede imprimir las rutas descubiertas):

package test.java.so;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class So37503760 {

    public static class Graph {

        private final Map<Character, Node> nodes = new TreeMap<Character, Node>();

        public Node addNode(char c) {
            Node existingNode = nodes.get(c);
            if(existingNode!=null) {
                return existingNode;
            }
            Node newNode = new Node(c);
            nodes.put(c, newNode);
            return newNode;
        }

        public void addEdge(char f, char t) {
            addNode(f).addChild(addNode(t));
        }

        public Node getNode(char name) {
            Node ret = nodes.get(name);
            if(ret==null) {
                throw new RuntimeException("No such node " + name);
            }
            return ret;
        }

    }

    public static class Node {

        private final char name;
        private final ArrayList<Node> children = new ArrayList<Node>();

        public Node(char c) {
            this.name=c;
        }

        public void addChild(Node childNode) {
            children.add(childNode);
        }

        public ArrayList<Node> getChildren() {
            return children;
        }

        public char getName() {
            return name;
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addEdge(''A'', ''B'');
        graph.addEdge(''A'', ''C'');
        graph.addEdge(''B'', ''C'');
        graph.addEdge(''C'', ''D'');
        graph.addEdge(''C'', ''E'');
        graph.addEdge(''D'', ''E'');
        int numberOfPaths = depthFirstSearch(graph, ''A'', ''E'');
        System.out.println("Found " + numberOfPaths + " paths");
    }

    public static int depthFirstSearch(Graph graph, char startNode, char destinationNode){
        return depthFirstSearch(graph, graph.getNode(startNode), graph.getNode(destinationNode), new ArrayList<Node>());
    }

    public static int depthFirstSearch(Graph graph, Node startNode, Node destinationNode, List<Node> currentPath){
        if(currentPath.contains(startNode)) {
            currentPath.add(startNode);
            throw new RuntimeException("Cycle detected: " + pathToString(currentPath));
        }
        currentPath.add(startNode);
        try {
//          System.out.println("Progress: " + pathToString(currentPath));
            if(startNode==destinationNode) {
                System.out.println("Found path: " + pathToString(currentPath));
                return 1;
            }
            int ret=0;
            for(Node nextNode : startNode.getChildren()){
                ret += depthFirstSearch(graph, nextNode, destinationNode, currentPath);
            }
            return ret;
        } finally {
            currentPath.remove(currentPath.size()-1);
        }
    }

    private static String pathToString(List<Node> path) {
        StringBuilder b = new StringBuilder();
        boolean printArrow=false;
        for(Node n : path) {
            if(printArrow) {
                b.append(" -> ");
            }
            b.append(n.getName());
            printArrow=true;
        }
        return b.toString();
    }
}