C++ 统计邻居节点和最大为K的图中节点数量

介绍

无向图是计算机科学和图论的基本组成部分，表示由无方向性的边连接的一组顶点。与无向图相关的一个常见问题是计算图中邻居节点和最大为K的节点数量。在计算机科学中，图论领域将处理给定矩阵中元素之间的连接关系。通常，图由边和节点元素组成。

统计图中节点数量

在这种情况下，所使用的图是无向图。无向图包含“N”个节点，“M”条边，并且需要满足条件以获取最多为K的节点数量。下面是一个由四个节点组成的无向图的常见示例。

示例

以四个顶点的邻接矩阵作为输入。

1 2
2 3
3 4
4 5

邻居是指节点的左侧或右侧节点。在上述情况中，节点1返回邻居总和为1，节点2返回邻居总和为2，节点3返回邻居总和为3，节点4返回邻居总和为2，最后节点5返回邻居总和为1。当邻居总和小于或等于K时，我们需要检查节点总和。因此，满足条件的节点只有1个，它的值为1。

方法1：使用递归函数计算图中邻居总和最多为K的节点数的C语言代码

邻接矩阵被初始化为输入，并且可以使用深度优先搜索（DFS）或广度优先搜索（BFS）算法来遍历列表。

算法

• 第1步 - 所需的头文件是和，已包含在给定的程序中。

• 第2步 - 将函数定义为具有三个参数graph，N和K，数据类型为int。

• 第3步 - 计数变量初始化为0，并使用for循环从1到N迭代遍历图的相邻列表。

• 第4步 - 边连接两个点A和B，它是给定邻接列表中的相邻节点。

• 第5步 - 求和值存储在名为“sum”的变量中，它求和给定顶点中的权重或属性值。

• 第6步 - 检查条件，判断sum值是否小于或等于K，如果是，则将计数增加1。

• 第7步 - 最终输出包含图中邻居总和最多为K时节点数的计数。

示例

//The header files are included
#include <stdio.h>
#include <stdlib.h>

// Function defined with three arguments and declared as output
int output(int** graph, int node, int edges) {
   //Initializing the variable as 0
   int val = 0; 
   //for loop will iterate through the values
   for (int m = 1; m <= node; ++m) {
      int sum = 0;
      for (int neighbor = 1; neighbor <= node; ++neighbor) {
         sum += graph[m][neighbor];
      }
      //To check for the condition whether the sum value is less than or equal to edges
      if (sum <= edges) {
         //When equal it is incremented by one
         val++;
      }
   }

   return val;
}

// Main function to test the code
int main() {
   //Initializing the variables with values
   int node = 5, M = 4, edges = 2;

   int** graph = (int**)malloc((node+1)*sizeof(int*)); // Indexed from 1 to N 

   for(int i=0; i<=node; ++i){
      graph[i] = (int*)malloc((node+1)*sizeof(int));
      for(int j=0; j<=node; ++j){
         graph[i][j] = 0;
      }
   }

   // The edges values are declared in the graph
   graph[1][2] = 1;
   graph[2][1] = 1;
   graph[2][3] = 1;
   graph[3][2] = 1;
   graph[3][4] = 1;
   graph[4][3] = 1;
   graph[4][5] = 1;
   graph[5][4] = 1;
   //The function is called recursively with the parameters
   int nodeCount = output(graph, node, edges);

   printf("The total number of nodes with a sum of neighbors less than or equal to %d:\n%d\n", edges, nodeCount);

   return 0;
}

输出

The total number of nodes with a sum of neighbors less than or equal to 2:
5

结论

使用C程序，构建代码 – 我们可以使用递归函数实现对给定无向图的计数。该函数与三个参数一起递归调用。通过使用pushback功能并添加用户给出的值的邻居元素，得到条件。