如何求两个节点图之间的距离<Integer,List<Integer>>

Question

我正在尝试编写一个程序来查找两个节点之间的距离，给定父子关系

输入

1 2

1 3

3 4

3 5  

我使用以下代码来获取值。这棵树是双向的，到每个节点都有单位距离。

代码

    Map<Integer, List<Integer>> adjacencies = new HashMap<Integer,  List<Integer>>(); 
        for (int i=1; i<=n; i++) {
           List<Integer> l1= new ArrayList<Integer>();
           adjacencies.put(i,l1);
        }  
        for (int i=0; i<n-1; i++) {
            int u = in.nextInt();
            int v = in.nextInt();
            adjacencies.get(u).add(v);
            adjacencies.get(v).add(u);
        }

Answer 1

您可以使用 BFS 来查找两个节点之间的距离。我希望这个解决方案能帮助你。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;

public class StackOverFlow {
static Map<Integer, List<Integer>> adjacencies = new HashMap<Integer, List<Integer>>(); 

public static void main(String[] args) {

    Scanner in = new Scanner(System.in);
    int n = in.nextInt();

    for (int i=1; i<=n; i++) {
       List<Integer> l1= new ArrayList<Integer>();
       adjacencies.put(i,l1);
    }  
    for (int i=0; i<n-1; i++) {
        int u = in.nextInt();
        int v = in.nextInt();
        adjacencies.get(u).add(v);
        adjacencies.get(v).add(u);
    }

    findingDistanceBetweenTwoNodes(1, 3);
}
static int [] parent = new int[100];
static boolean [] visited = new boolean[100];

public static void findingDistanceBetweenTwoNodes(int nodea, int nodeb){

    Queue<Integer> q = new LinkedList<Integer>();
    q.add(nodea);
    parent[nodea] = -1;
    visited[nodea] = true;
    boolean loop = true;
    while(!q.isEmpty() && loop){
        int element = q.remove();
        Integer s =null;

        while((s = getChild(element))!=null) {
            parent[s] = element;
            visited[s] = true;
            if(s == nodeb)
            {
                loop= false;
                break;
            }

            q.add(s);
        }
    }
    int x = nodeb;
    int d = 0;
    if(!loop)
     {
        while(parent[x] != -1)

     {
         d +=1;
         x = parent[x];
     }

    System.out.println("\nThe distance from node "+nodea+ " to node "+nodeb+" is "   +d);
     }
    else
        System.out.println("Can't reach node "+nodeb);
}


private static Integer getChild(int element) {
    ArrayList<Integer> childs = (ArrayList<Integer>) adjacencies.get(element);
    for (int i = 0; i < childs.size(); i++) {
        if(!visited[childs.get(i)])
        return childs.get(i);
    }
    return null;

}

}

Answer 2

假设一个节点只能有一个父节点。

创建一个

TreeNode

类型，它可以有

TreeNode parent, List<TreeNode> children

属性。根节点

parent

为空，叶子节点没有

children

我认为这种树形结构使您的工作更轻松。

Answer 3

虽然并非不可能，但我个人认为将 Map 作为树的表示进行导航太麻烦了，最好的是前面的答案中描述的数据结构 - 其中对象有其父级和子级。

计算它们之间的距离并不是一个在寻找某些节点时遍历树的问题，如果你没有树遍历的知识，你可以从这里开始https://en.wikipedia.org/wiki/Tree_traversal，但它是没什么难的，只是有更多的方法可以完成它。

Answer 4

我建议您使用简单的 DFS 过程来完成它，因为它更容易编码，并且不需要额外的内存（除了递归堆栈），只要时间复杂度可以接受：

int dfs(int u, int pu, int target, int h, Map<Integer, List<Integer>> adjacencies) {
    if (u == target) { // if target reached
      return h; // return current distance
    }
    for (int v : adjacencies.get(u)) {
      if (v != pu) { // don't go up in the tree, only down
        int d = dfs(v, u, target, h+1, adjacencies);
        if (d != -1) { // if target is in this subtree
          return d;
        }
      }
    }
    return -1; // target is not in this subtree
  }

您可以像这样使用它：

int from = 1;
int to = 5;
int dist = dfs(from, -1, to, 0, adjacencies); // use from as root of DFS

希望有帮助。