计算距离集合中所有节点K距离内的节点数-yiteyi-C++库

给定一棵带有一些标记节点和正数K的无向树。我们需要打印与所有标记节点的距离小于K的所有此类节点的计数，这意味着与所有标记节点的距离小于K的每个节点都应该在结果中计数。 例如：

null

图片[1]-计算距离集合中所有节点K距离内的节点数-yiteyi-C++库

In above tree we can see that node with index 0, 2, 3, 5, 6, 7 have distances less than 3from all the marked nodes.so answer will be 6

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

我们可以使用广度优先搜索来解决这个问题。在这个问题中需要观察的主要问题是，如果我们发现两个标记节点之间的距离最大，考虑到所有标记节点对，那么如果一个节点与这两个节点之间的距离小于K，那么它与所有标记节点之间的距离将小于K，因为这两个节点代表所有标记节点的极限，如果一个节点位于该限制内，那么它与所有标记节点的距离将小于K，否则不会。如上例所示，节点1和节点4是最远的标记节点，因此距离这两个节点小于3的节点也将距离节点2小于3。现在，第一个距离标记节点，我们可以通过对任意随机节点进行bfs得到，第二个距离标记节点，我们可以通过对我们刚刚从第一个bfs中找到的标记节点进行另一个bfs得到，在这个bfs中，我们还可以找到所有节点与第一个距离标记节点的距离，为了找到所有节点与第二个距离标记节点的距离，我们将再进行一个bfs，所以在做了这三个bfs之后，我们可以得到所有节点与两个极端标记节点的距离，这可以与K进行比较，以知道哪些节点与所有标记节点的距离都在K-距离范围内。

C++

                         //  C++ program to count nodes inside K distance                       
                         // range from marked nodes                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Utility bfs method to fill distance vector and returns                       
                         // most distant marked node from node u                       
                         int                                     bfsWithDistance(vector<                                     int                                     > g[],                                     bool                                     mark[],                                     int                                     u,                       
                                                 vector<                                     int                                     >& dis)                       
                         {                       
                                                 int                                     lastMarked;                       
                                                 queue<                                     int                                     > q;                       
           
                                                 //  push node u in queue and initialize its distance as 0                       
                                                 q.push(u);                       
                                                 dis[u] = 0;                       
           
                                                 //  loop until all nodes are processed                       
                                                 while                                     (!q.empty())                       
                                                 {                       
                                                 u = q.front();      q.pop();                       
                                                 //  if node is marked, update lastMarked variable                       
                                                 if                                     (mark[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 not given value already                       
                                                 if                                     (dis[v] == -1)                       
                                                 {                       
                                                 dis[v] = dis[u] + 1;                       
                                                 q.push(v);                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 //  return last updated marked value                       
                                                 return                                     lastMarked;                       
                         }                       
           
                         // method returns 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(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 */                       
                                                 v = bfsWithDistance(g, mark, u, dl);                       
           
                                                 //  third bfs to fill dr by distances from second                       
                                                 // chosen marked node                       
                                                 bfsWithDistance(g, mark, v, dr);                       
           
                                                 int                                     res = 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[i] <= K && dr[i] <= K)                       
                                                 res++;                       
                                                 }                       
                                                 return                                     res;                       
                         }                       
           
                         // Driver code to test above methods                       
                         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[] = {1, 2, 4};                       
                                                 int                                     N =                                     sizeof                                     (marked) /                                     sizeof                                     (marked[0]);                       
           
                                                 int                                     K = 3;                       
                                                 cout << nodesKDistanceFromMarked(edges, V, marked, N, K);                       
                                                 return                                     0;                       
                         }                       

Python3

                         # Python3 program to count nodes inside                       
                         # K distance range from marked nodes                       
                         import                                     queue                       
           
                         # Utility bfs method to fill distance                       
                         # vector and returns most distant                       
                         # marked node from node u                       
                         def                                     bfsWithDistance(g, mark, u, dis):                       
                                                 lastMarked                                     =                                     0                       
                                                 q                                     =                                     queue.Queue()                       
           
                                                 # push node u in queue and initialize                       
                                                 # its distance as 0                       
                                                 q.put(u)                       
                                                 dis[u]                                     =                                     0                       
           
                                                 # loop until all nodes are processed                       
                                                 while                                     (                                     not                                     q.empty()):                       
                                                 u                                     =                                     q.get()                       
                                   
                                                 # if node is marked, update                       
                                                 # lastMarked variable                       
                                                 if                                     (mark[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                                     (dis[v]                                     =                                     =                                     -                                     1                                     ):                       
                                                 dis[v]                                     =                                     dis[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)                       
           
                                                 res                                     =                                     0                       
                                   
                                                 # loop over all nodes                       
                                                 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):                       
                                                 res                                     +                                     =                                     1                       
                                                 return                                     res                       
           
                         # 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                                     =                                     [                                     1                                     ,                                     2                                     ,                                     4                                     ]                       
                                                 N                                     =                                     len                                     (marked)                       
           
                                                 K                                     =                                     3                       
                                                 print                                     (nodesKDistanceFromMarked(edges, V,                       
                                                 marked, N, K))                       
           
                         # This code is contributed by PranchalK                       

输出：

本文由 乌特卡什·特里维迪 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章