Найти высоту узла в дереве 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 высота 2 60 высота 2 50 высота 2 70 Height3

, но вместо этого он дает мне выход

40 Высота0 10 Высота1 20 Высота1 30 Высота2 60 Высота2 50 Высота1 70 Высота2

Как я могу это решить?

Answer 1

for -loop вашего BFS метод должен выглядеть следующим образом:

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") к высота родительского узла («элемент») + 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;