Count Nodes within K-distance

Approach:

In this approach, we will be using the bfs traversal of the graph. Finding the maximum distance between any two marked nodes considering all pairs of marked nodes one by one. After calculating the maximum distance, we will be checking each node's distance from both of these nodes( which are farthest from each other). If the distance of the node is less than K from both nodes, that means it will be at a distance less than K from all the marked nodes because these two nodes represent the extreme limit of all marked nodes, i.e., if a node lies in the limit, then it will be at a distance less than K from all marked nodes otherwise not. Now by doing a bfs traversal on the graph starting from any node, we can find the first extreme of both nodes. Now by again doing bfs from this node, we can find the second extreme node to avoid one extra bfs traversal for finding nodes distance from the first extreme; we can find these distances in the same bfs we are doing to find the second node. For finding distances of the node from the second extreme node, we will need one more bfs traversal. After getting all distances, we can check whether the distances are less than K for the count.

Steps:

• Create a function called BFSUTIL, which we will use to traverse the graph and store the distance of nodes from extreme and will return the most extreme marked node from node U.this function will take parameters array storing edges, a boolean array for marked nodes, node U and array for storing distances. BFSUTIL(GRAPH,MARK,U,DISTANCES)
• Declare a variable for storing the previous marked node ‘PREMARKED.’
• Initialize a queue for bfs traversal ‘Q’ and push node U  in the queue and initialize its distance as 0, i.e., DISTANCES.get(U)=0;
• Now run a loop until all the nodes are processed or the queue is empty.
• Now do Q.POLL() and check if it is marked in the boolean array and if it is already marked change last marked as the current node.
• Now loop over all neighbors of U and update their distance before pushing in the queue, i.e., if DISTANCES.GET(V) is -1 update it.
• Finally, return the PREMARKED node.
• Now for the main function, which returns the count of nodes, prepare the graph and the marked nodes.
• Declare three arrays TEMP, DISTANCEFROMFIRSTEXTREME, DISTFROMSECONDEXTREME, to find the first distant node and to store distances from both extremes, respectively.
• Run three bfs traversals as said in approach.
• Finally, check for the distances which are less than K and add it to the final COUNT, which was initialized as ZERO initially.
• Return COUNT.

O(V+E), Where ‘V’ denotes the number of vertices in the graph, and ‘E’ denotes the number of edges in the graph.

Since we are doing a bfs traversal, which is taking O(V+E) time complexity.

O(V), Where ‘V’ denotes the number of vertices in the graph.

As we are using Arraylist to store vertices.