I have a problem about getting all siblings from the main node and implementing the process n Breadth First Search algorithm written by Java.

How can I implement that?

I shared my code snippets shown below.

Here is my Node class shown below.

public class Node{
    Node(int data){
       this.data = data;
       this.left = null;
       this.right = null;
       this.visited = false;
    }
    int data;
    Node left;
    Node right;
    boolean visited;

    // getter and setter 
}

Here is the initilaization process shown below.

Node node1 = new Node(1);
Node node7 = new Node(7);
Node node9 = new Node(9);
Node node8 = new Node(8);
Node node2 = new Node(2);
Node node3 = new Node(3);
node1.left = node7;
node1.right = node9;
node7.right = node8;
node9.right = node3;
node9.left = node2;

Here is the method shown below.

public static void bfs(Node root){
        if (root == null){
            return;
        }
        
        Node temp; //a binary tree with a inner generic node class
        Queue<Node> queue = new LinkedList<>(); //can't instantiate a Queue since abstract, so use LLQueue
        
        queue.add(root);
        root.visited = true;
        while (!queue.isEmpty())
        {
            temp = queue.poll(); //remove the node from the queue
            
            // How can I get all siblings of the node like
            // for (Node sibling : temp.getSiblingNodes())
            // sibling.visited=true;
            // queue.add(sibling);
            
        }

        // get the result as a list
    }

CodePudding user response：

Since Node has a property isVisited, I assume that there could be cycles in the Graph.

The algorithm can be described in the following steps:

• Mark the root Node as visited and put it into the Queue.

• Then until the Queue is not empty, repeat:

  • Remove the Node (current Node) from the head of the Queue;
  • Check its left and right child-Nodes. If a child-Node exists (i.e. not null) and hasn't been visited yet, then add this node both into the Queue and resulting list of sibling-Nodes and set isVisited property of the child-Node to true.

That's how it might be implemented:

public static List<Node> bfs(Node root) {
    if (root == null) return Collections.emptyList();
    
    List<Node> siblings = new ArrayList<>();
    Queue<Node> queue = new ArrayDeque<>(); // performs better than LinkedList
    
    queue.add(root);
    // siblings.add(root); // uncomment this line ONLY if you need the root-Node to be present in the result
    root.visited = true;
    
    while (!queue.isEmpty()) {
        Node current = queue.poll();

        tryAdd(siblings, queue, current.left);
        tryAdd(siblings, queue, current.right);
    }
    return siblings;
}

public static void tryAdd(List<Node> siblings, Queue<Node> queue, Node next) {
    if (next != null && !next.isVisited()) {
        queue.add(next);
        siblings.add(next);
        next.setVisited(true);
    }
}

To avoid repeating the same actions for both left and right child-Nodes, I've created method tryAdd().

We can alter its conditional logic by introducing a Predicate (in this case condition is short and well readable, and this option is shown rather for education purposes):

public static final Predicate<Node> IS_NULL_OR_VISITED =
    Predicate.<Node>isEqual(null).or(Node::isVisited);

public static void tryAdd(List<Node> siblings, Queue<Node> queue, Node next) {
    if (IS_NULL_OR_VISITED.test(next)) return;
    
    queue.add(next);
    siblings.add(next);
    next.setVisited(true);
}

CodePudding user response：

You should not try to get the sibling of a node. If you push the children of the current node to the queue, you will guarantee that you pull them out of the queue in sibling order. The important thing here is that you visit a node when it is pulled from the queue, not when it is added to the queue.

So your function could be turned into this:

    public static List<Node> bfs(Node root){
        Queue<Node> queue = new LinkedList<>();
        List<Node> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        queue.add(root); // Don't visit this root node yet...
        while (!queue.isEmpty())
        {
            Node node = queue.poll();
            result.add(node); // Here we visit the node
            // Add the children of the visited node to the queue
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        return result;
    }

The caller can do this:

    for (Node node : bfs(node1)) {
        System.out.println(node.data);
    }

CodePudding user response：

On a more side note, you can find an implementation for the BFS algorithm along with a Ford Fulkerson algorithm on this GitHub repository: Ford Fulkerson with BFS- Max flow problem