This article will look at the problem of counting the nodes that have k distance from all the nodes in the Graph. Graph questions are the most popular and vital in coding interviews and programming competitions. First, let us understand the data structure Graph.

In computer science, a graph data structure is a collection of nodes that have data and are connected to other nodes with the help of edges.

Sample graph with nodes and edges

Sample Example

Consider the Graph given above as G. The vertex numbers range from 0 to 9. The vertex is joined together with the help of edges. Numbers are present on each vertex. We have to find the count of nodes that are at a distance k from all the marked nodes in the set. Let us take the value of k as 2. Only vertices 3, and 5 the common distances that are at distance 2 from vertices 2, 4, and 5. So, 2 is our final answer.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Algorithm

We will solve the problem using breadth-first search.

Step 1: Create a function called bfsWithDistance 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. bfsWithDistance(graph, marked, u, distance).

Step 2: Declare a variable for storing the previous marked node ‘lastMarked.’

Step 3: Initialize a queue for bfs traversal ‘q’’ and push node u in the queue and initialize its distance as 0, i.e., distance.get(u)=0;

Step 4: Now run a loop until all the nodes are processed or the queue is empty.

Step 5: Now do q.remove() and check if it is marked in the boolean array and if it is already marked change last marked as the current node.

Step 6: Now loop over all neighbors of u and update their distance before pushing in the queue, i.e., if distance.get(v) is -1 update it.

Step 7: Finally, return the ‘lastMarked’ node.

Step 8: Now for the main function, which returns the count of nodes, prepare the graph and the marked nodes.

Step 9: Declare three arrays tmp, dl, dr, to find the first distant node and to store distances from both extremes, respectively.

Step 10: Run three bfs traversals as said in approach.

Step 11: Finally, check for the distances which are less than K and add it to the final ‘count’, which was initialized as 0 initially.

Step 12: Return count.

Implementation in Java

import java.io.*;
import java.util.*;
class CN
{
// to fill distance vector and return most
// distant marked node from node u using bfs
static int bfsWithDistance(ArrayList<ArrayList<Integer>> g, boolean marked[], int u,
ArrayList<Integer> distance)
{
int lastMarked = 0;
Queue<Integer> q = new LinkedList<>();
// push node u in queue and initialize its distance as 0
q.add(u);
distance.set(u , 0);
while (!q.isEmpty())
{
u = q.remove();
// if node is marked, update lastMarked variable
if (marked[u] == true)
lastMarked = u;
// loop over all neighbors of u and update their
// distance before pushing in queue
for (int i = 0; i < g.get(u).size(); i++)
{
int v = g.get(u).get(i);
// if not given value already
if (distance.get(v) == -1)
{
distance.set(v , distance.get(u) + 1);
q.add(v);
}
}
}
// return last updated marked value
return lastMarked;
}
// method to return count of nodes which are in K-distance
// range from marked nodes
static int nodesKDistanceFromMarked(int edges[][], int V,
int marked[], int N, int K)
{
// vertices in a tree are one more than number of edges
V = V + 1;
ArrayList<ArrayList<Integer>>g = new ArrayList<ArrayList<Integer>>(V);
for(int i=0;i<V;i++){
g.add(new ArrayList<Integer>());
}
// fill vector for graph
int u, v;
for (int i = 0; i < (V - 1); i++)
{
u = edges[i][0];
v = edges[i][1];
g.get(u).add(v);
g.get(v).add(u);
}
// fill boolean array mark from marked array
boolean mark[] = new boolean[V];
Arrays.fill(mark, false);
for (int i = 0; i < N; i++)
mark[marked[i]] = true;
// vectors to store distances
ArrayList<Integer> tmp = new ArrayList<>(),dl = new ArrayList<>(),dr = new ArrayList<>();
for(int i=0;i<V;i++){
tmp.add(-1);
dl.add(-1);
dr.add(-1);
}
// first bfs to get one
// distant marked node
u = bfsWithDistance(g, mark, 0, tmp);
/* second bfs to get other distant marked node
and also dl is filled with distances from first
chosen marked node */
v = bfsWithDistance(g, mark, u, dl);
// third bfs to fill dr by distances from second
// chosen marked node
bfsWithDistance(g, mark, v, dr);
int count = 0;
// loop over all nodes
for (int i = 0; i < V; i++)
{
// increase res by 1, if current node has distance
// less than K from both extreme nodes
if (dl.get(i) <= K && dr.get(i) <= K)
count++;
}
return count;
}
// Driver Code
public static void main(String args[])
{
int edges[][] =
{
{1, 0}, {0, 3}, {0, 8}, {2, 3},
{3, 5}, {3, 6}, {3, 7}, {4, 5},
{5, 9}
};
int V = edges.length;
int marked[] = {2, 4, 5};
int N = marked.length;
int K = 2;
System.out.println(nodesKDistanceFromMarked(edges, V, marked, N, K));
}
}

Output

2

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
// to fill distance vector and return most
// distant marked node from node u using bfs
int bfsWithDistance(vector<int> g[], bool marked[], int u,
vector<int>& distance)
{
int lastMarked;
queue<int> q;
// pushing node u in queue and initializing its distance as 0
q.push(u);
distance[u] = 0;
while (!q.empty())
{
u = q.front(); q.pop();
// if node is marked, update lastMarked variable
if (marked[u])
lastMarked = u;
// loop over all neighbors of u and update their
// distance before pushing in queue
for (int i = 0; i < g[u].size(); i++)
{
int v = g[u][i];
if (distance[v] == -1)
{
distance[v] = distance[u] + 1;
q.push(v);
}
}
}
// return last updated marked value
return lastMarked;
}
// method to return count of nodes which are in K-distance
// range from marked nodes
int nodesKDistanceFromMarked(int edges[][2], int V,
int marked[], int N, int K)
{
// vertices in a tree are one more than number of edges
V = V + 1;
vector<int> g[V];
// fill vector for graph
int u, v;
for (int i = 0; i < (V - 1); i++)
{
u = edges[i][0];
v = edges[i][1];
g[u].push_back(v);
g[v].push_back(u);
}
// fill boolean array mark from marked array
bool mark[V] = {false};
for (int i = 0; i < N; i++)
mark[marked[i]] = true;
// vectors to store distances
vector<int> tmp(V, -1), dl(V, -1), dr(V, -1);
// first bfs to get one
// distant marked node
u = bfsWithDistance(g, mark, 0, tmp);
/* second bfs to get other distant marked node
and also dl is filled with distances from first
chosen marked node */
v = bfsWithDistance(g, mark, u, dl);
// third bfs to fill distances from second
// chosen marked node
bfsWithDistance(g, mark, v, dr);
int count = 0;
for (int i = 0; i < V; i++)
{
// increase res by 1, if current node has distance
// less than K from both extreme nodes
if (dl[i] <= K && dr[i] <= K)
count++;
}
return count;
}
// Driver method
int main()
{
int edges[][2] =
{
{1, 0}, {0, 3}, {0, 8}, {2, 3},
{3, 5}, {3, 6}, {3, 7}, {4, 5},
{5, 9}
};
int V = sizeof(edges) / sizeof(edges[0]);
int marked[] = {2, 4, 5};
int N = sizeof(marked) / sizeof(marked[0]);
int K = 2;
cout << nodesKDistanceFromMarked(edges, V, marked, N, K);
return 0;
}

Output

2

Implementation in Python

import queue
# Utility bfs method to fill distance
# vector and returns most distant
# marked node from node u
def bfsWithDistance(g, marked, u, distance):
lastMarked = 0
q = queue.Queue()
# push node u in queue and initialize
# its distance as 0
q.put(u)
distance[u] = 0
# loop until all nodes are processed
while (not q.empty()):
u = q.get()
# if node is marked, update
# lastMarked variable
if (marked[u]):
lastMarked = u
# loop over all neighbors of u and
# update their distance before
# pushing in queue
for i in range(len(g[u])):
v = g[u][i]
# if not given value already
if (distance[v] == -1):
distance[v] = distance[u] + 1
q.put(v)
# return last updated marked value
return lastMarked
# method returns count of nodes which
# are in K-distance range from marked nodes
def nodesKDistanceFromMarked(edges, V, marked, N, K):
# vertices in a tree are one
# more than number of edges
V = V + 1
g = [[] for i in range(V)]
# fill vector for graph
u, v = 0, 0
for i in range(V - 1):
u = edges[i][0]
v = edges[i][1]
g[u].append(v)
g[v].append(u)
# fill boolean array mark from
# marked array
mark = [False] * V
for i in range(N):
mark[marked[i]] = True
# vectors to store distances
tmp = [-1] * V
dl = [-1] * V
dr = [-1] * V
# first bfs(from any random node)
# to get one distant marked node
u = bfsWithDistance(g, mark, 0, tmp)
# second bfs to get other distant
# marked node and also dl is filled
# with distances from first chosen
# marked node
u = bfsWithDistance(g, mark, u, dl)
# third bfs to fill dr by distances
# from second chosen marked node
bfsWithDistance(g, mark, u, dr)
count = 0
for i in range(V):
# increase res by 1, if current node
# has distance less than K from both
# extreme nodes
if (dl[i] <= K and dr[i] <= K):
count += 1
return count
# Driver Code
if __name__ == '__main__':
edges = [[1, 0], [0, 3], [0, 8],
[2, 3], [3, 5], [3, 6],
[3, 7], [4, 5], [5, 9]]
V = len(edges)
marked = [2,4,5]
N = len(marked)
K = 2
print(nodesKDistanceFromMarked(edges, V,
marked, N, K))

Output

2

Complexity Analysis

Time complexity

This approach will take O(V+E) times where V is vertices and E is the number of edges.

Space complexity:

O(V), auxiliary space required for the queue to do BFS

What is the maximum number of edges that a bipartite graph can have?

A bipartite graph can have most: (node with color 0) * (node with color 1) number of edges.

What is directed and undirected graphs?

Edges in directed graphs point from one end of the graph to the other. The edges in undirected networks merely link the nodes at each end.

Conclusion

In this blog, we discussed how to count the nodes within k- distance from all nodes in a set. We understood this problem with the help of an example. Then we discussed its algorithm. After that, we discussed its implementations in other languages like C++, Python3, and java. In the end, we saw the complexity analysis of the approach.