在图中的两个节点之间寻找路径（存储通过的节点）

Question

我有一个图，我想找到两个节点（3 号和 5 号）之间的路径。

我读了关于在图中查找路径的内容，并尝试编写 DFS 和 BFS。两者都已实施并且运行良好。但是，我想获得从 3 到 5 直接访问的每个节点的列表。两种算法都按预期工作，当运行 bsf 我将按以下顺序访问节点：2,6,1,4,5。使用 dfs 2,1,4,5。但我想实现的是 6,5（在第一种情况下）和 2,4,5 在第二种情况下。

换句话说，我只想保存从 3 到 5 途中的节点（在 dfs/bfs 期间未访问所有节点），作为节点列表。

绞尽脑汁想了很久，怎么改代码实现，还是换个方式？我应该将节点存储在正确的路径中，还是使用不同的算法？我根本不知道该怎么做。

我的男朋友

  public List<Node> bfs(Node root, Node nodeWeSearchFor)
 { Queue<Node> queue = new LinkedList<Node>();
  List<Node> route = new ArrayList<Node>();

  if(root == null || nodeWeSearchFor == null) return route;
  //State is just an enum Visited or unvisited
  root.state = State.Visited;
   //Adds to end of queue
  queue.add(root);

  while(!queue.isEmpty())
  {
      //removes from front of queue
      Node r = queue.remove(); 


      //Visit child first before grandchild
      for(Node n: r.getConnectedNodes())
      {
          if(n.state == State.Unvisited)
          {
              queue.add(n);
              route.add(n);
              n.state = State.Visited;
              //If we found node, return
              if(n==nodeWeSearchFor){
                  return route;
              }
          }
      }
  }
return route;}

我的dfs:

    public  List<Node> dfs(Node root, Node nodeWeSearchFor)
 {       
  List<Node> route = new ArrayList<Node>();
  //Avoid infinite loops
  if(root == null) return route;

  System.out.print(root.toString() + "\t");
  root.state = State.Visited;
  route.add(root);
  if(root == nodeWeSearchFor) return route;
  //for every child
  for(Node n: root.getConnectedNodes())
  {
      //if childs state is not visited then recurse
      if(n.state == State.Unvisited)
      {
          //recursive call for dfs (We are passing route)
          dfs(n,nodeWeSearchFor,route);
      }
  }
return route;
}

 public  List<Node> dfs(Node root, Node nodeWeSearchFor,List<Node> _route)
 {       
  List<Node> route = _route;
  //Avoid infinite loops
  if(root == null) return route;

  System.out.print(root.toString() + "\t");
  root.state = State.Visited;
  route.add(root);
  if(root == nodeWeSearchFor) return route;
  //for every child
  for(Node n: root.getConnectedNodes())
  {
      //if childs state is not visited then recurse
      if(n.state == State.Unvisited)
      {
          dfs(n,nodeWeSearchFor,route);
      }
  }
return route;

}

Answer 1

这很容易，在DFS中，当你到达"end"（你不能前进）时，你必须"go back"。因此，当您要 "back" 时，您只需从已访问节点列表中删除 "dead end" 处的那个节点。

在 BFS 中，您必须为每个访问的节点创建新列表，复制 "opens him" 节点的已访问节点，然后将其自身添加到该列表中。

在图中的两个节点之间寻找路径（存储通过的节点）

Finding a way between two nodes in a grah (Storing the nodes passed)

java

graph

breadth-first-search

depth-first-search