在 bfs 树中查找节点的高度

Question

我想在 bfs 中找到树节点的高度，但没有成功，它为我提供了前 5 个节点的正确高度，但后两个节点不正确。这是代码

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package bfs;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class BreadthFirstSearchExample
{ 

 private Queue<Node> queue;
 static ArrayList<Node> nodes=new ArrayList<Node>();
 static class Node
 {
  int data;
  boolean visited;
  int parent;
  int height;

  Node(int data){
   this.data=data;


  }
 }

 public BreadthFirstSearchExample()
 {
  queue = new LinkedList<Node>();
 }

 // find neighbors of node using adjacency matrix
 // if adjacency_matrix[i][j]==1, then nodes at index i and index j are connected
 public ArrayList<Node> findNeighbours(int adjacency_matrix[][],Node x)
 {
  int nodeIndex=-1;

  ArrayList<Node> neighbours=new ArrayList<Node>();
  for (int i = 0; i < nodes.size(); i++) {
   if(nodes.get(i).equals(x))
   {
    nodeIndex=i;
    break;
   }
  }

  if(nodeIndex!=-1)
  {
   for (int j = 0; j < adjacency_matrix[nodeIndex].length; j++) {
    if(adjacency_matrix[nodeIndex][j]==1)
    {
     neighbours.add(nodes.get(j));
    }
   }
  }
  return neighbours;
 }

 public  void bfs(int adjacency_matrix[][], Node node)
 {

  queue.add(node);
  node.visited=true;


  int nf =0;

  while (!queue.isEmpty())
  {
   nf = queue.size();
   Node element=queue.remove();

   System.out.print(element.data + "\t");


    System.out.print("Height" + element.height + "\t");

   ArrayList<Node> neighbours=findNeighbours(adjacency_matrix,element);
   for (int i = 0; i < neighbours.size(); i++) {
    Node n=neighbours.get(i);
    int mf = neighbours.size();

    if(n!=null && !n.visited)
    {

     n.parent=element.data;
     queue.add(n);
     n.visited=true;   
    }
    n.height++;
   element.height = n.height;
   }

  }
 }

 public static void main(String arg[])
 {

   Node node40 =new Node(40);
   Node node10 =new Node(10);
   Node node20 =new Node(20);
   Node node30 =new Node(30);
   Node node60 =new Node(60);
   Node node50 =new Node(50);
   Node node70 =new Node(70);

   nodes.add(node40);
   nodes.add(node10);
   nodes.add(node20);
   nodes.add(node30);
   nodes.add(node60);
   nodes.add(node50);
   nodes.add(node70);
   int adjacency_matrix[][] = {
     {0,1,1,0,0,0,0},  // Node 1: 40
     {1,0,0,1,0,0,0},  // Node 2 :10
     {1,0,0,1,1,1,0},  // Node 3: 20
     {0,1,1,0,1,0,0},  // Node 4: 30
     {0,0,1,1,0,0,1},  // Node 5: 60
     {0,0,1,0,0,0,1},  // Node 6: 50
     {0,0,0,0,1,1,0},  // Node 7: 70
   };
   System.out.println("The BFS traversal of the graph is ");
   BreadthFirstSearchExample bfsExample = new BreadthFirstSearchExample();
   bfsExample.bfs(adjacency_matrix, node40);

 }
}

代码的输出应该是

40 Height0 10 Height1 20 Height1 30 Height2 60 Height2 50 Height2 70 Height3

但它给了我输出

40 Height0 10 Height1 20 Height1 30 Height2 60 Height2 50 Height1 70 Height2

我该如何解决这个问题？

Answer 1

您的 bfs 方法的 for 循环必须如下所示：

for (int i = 0; i < neighbours.size(); i++) {
  Node n = neighbours.get(i);
  int mf = neighbours.size();

  if (n != null && !n.visited) {
    n.parent = element.data;
    queue.add(n);
    n.visited = true;
    n.height = element.height + 1;    // <- this is right
  }

  // This was wrong
  //n.height++;                    
  //element.height = n.height;
}

解释：

更改的行将访问节点（"n"）的高度设置为父节点（"element"）的高度+ 1，但仅在第一次访问时（所以在if语句）。这就是你想要的，即高度。

你之前所做的是每次将节点视为邻居时增加节点的高度，而不管它之前是否被访问过。然后您将父节点的高度更改为该高度，但再也看不到它，因为它不会再次打印。

Answer 2

只需将此部分更改为

if(n!=null && !n.visited)
{
    n.parent=element.data;
    queue.add(n);
    n.visited=true;
}
n.height++;
element.height = n.height;

至

if(n!=null && !n.visited)
{
    n.parent=element.data;
    queue.add(n);
    n.visited=true;
    n.height=element.height+1;
}
//n.height++;
//element.height = n.height;

在 bfs 树中查找节点的高度

Find height of a node in bfs tree

java

breadth-first-search