bfsツリーのノードの高さを見つけよう

Question

bfsのツリーノードの高さを探していますが、うまくいきません。最初の5つのノードに正しい高さを与えていますが、最後の2つのノードは正しくありません。ここで、コードの出力は

40 Height0 10 Height1 20 Height1 30身長2 60身長2 50身長2 70 Height3

あるべき

/* 
* 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高さ0 10高さ20高さ1 30高さ2 60高さ2 50高さ1 70高さ2

どうすればこの問題を解決できますか？

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"）の高さを設定する

Answer 1

あなたのBFSのfor -loop方法は次のように見えるように持っています親ノード（「要素」）の高さ+ 1が、最初の訪問時にのみ返されます（したがって、ステートメント内）。これはあなたが望むもの、すなわち身長です。

以前に行ったことは、以前に訪問したかどうかにかかわらず、隣人として見たときにノードの高さを増やすことでした。そして親ノードの高さをそれに変更しますが、それは再び印刷されないので表示されません。

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;