实现广度优先图遍历一个给定的深度

  • Z时代
  • 2024-01-10
  • 分类：问答

我想实现广度优先图遍历，返回从一个节点到另一个路径的数量，但只能通过给定数量的节点。实现广度优先图遍历一个给定的深度

例如给出一个节点A，B，C，D，E的列表，如果我想知道从A到D获得的不同路径的数量，但是只有当路径不超过2个停止。 A-B-D，A-E-D将被认为是可以接受的，但是A-B-E-D会停止太多次，所以答案将是2条路径。

我想实现这个算法，但我不知道如何跟踪深度，以便我的搜索只有n层深。

这是我写的代码，迄今为止。问题在于searchNumPaths（）方法。

public class PathSearch{ 
private int maxSearches; 
private int pathCount; 
private int numPaths; 
private String node; 
private ArrayList<ArrayList<String>> path; 
ArrayList<Node> visited; 
public PathSearch(int maxSearches, int pathCount) { 
    node = ""; 
    this.maxSearches = maxSearches; 
    this.pathCount = pathCount; 
    path = new ArrayList<ArrayList<String>>(); 
    visited = new ArrayList<Node>(); 
} 
public int searchNumPaths(HashMap<String, Node> graph, Node startLocation, String endLocation, Queue<String> queue) { 
    //queue.add(startLocation.getLocation()); 
    while(!queue.isEmpty()) { 
     node = queue.remove(); 
     System.out.println("\n" + node +"\n"); 
     for (Edge realPath: graph.get(node).getNeighbors()) { 
       node = realPath.getEndLocation(); 
       System.out.println(node); 
       queue.add(node); 
       if (node.equals(endLocation)) { 
        numPaths++; 
       } 
     } 
     pathCount++; 
     if (pathCount>6){ 
      break; 
     } 
     for (int i = 0; i<queue.size(); i++) { 
      searchNumPaths(graph, graph.get(queue.peek()), endLocation, queue); 
      queue.remove(); 
     } 
    } 
    return numPaths; 
} 
public static void main(String[] args) throws IOException { 
    Train train = new Train(); 
    Graph graph = new Graph(train.readFile("input.txt")); 
    LinkedList<String> queue = new LinkedList<String>(); 
    queue.add("A"); 
    PathSearch great = new PathSearch(10, 0); 
    HashMap<String, Node> map = graph.returnMap(); 
    Node node = graph.returnMap().get("A"); 
    String nodeTwo = graph.returnMap().get("C").getLocation(); 
    //System.out.println(queue.remove()); 
    System.out.println("Number of paths: " + great.searchNumPaths(map, node, nodeTwo, queue)); 
}

}

回答：

您可以创建一个QueueNode类，它包含在您的队列放在一起有一个数字，表示该节点的深度当前字符串。然后，您可以继续搜索，直到遇到深度过大的节点。像这样的东西（T是在你的情况下，String）：

public class QueueNode<T> { 
    T value; 
    int depth; 
    public QueueNode(T value, int depth) { 
     this.value = value; 
     this.depth = depth; 
    } 
    // And so on.. Getters etc. 
}

当您创建新的对象QueueNode，只需将深入到一个比当前节点的深度。

通过这样做，你可以添加这样的事情你searchNumPaths函数（调用queue.remove()后）：

if (node.getDepth() > maxDepth) { 
    return numPaths; 
}

请注意，如果这仅适用于您的队列保证随深度增加而返回的节点。对于广度优先的搜索来说，情况总是如此，但如果您打算将其更改为A星搜索或稍后进行搜索，则此假设会中断。

以上是 实现广度优先图遍历一个给定的深度 的全部内容， 来源链接： utcz.com/qa/261100.html

回到顶部