C++ 为每个节点构建图的构件大小

介绍

图论是计算机科学中的一个基本领域，允许我们研究和可视化对象或实体之间的关系。分析图的一个重要方面是理解网络中组件或连接的子图的大小。在本文中，我们将探讨如何使用C++代码从每个节点的构件大小构建图。在图论中，组件是指任何连接的子图，在该子图中任意两个顶点之间存在路径。它有助于描绘整个图结构中相互连接的节点的聚集或群组。

从每个节点的构件大小构建图

在构建我们的组件大小分布图之前，让我们简要了解邻接表——一种在编程语言如C++中表示图的流行方式。邻接表通过为每个顶点存储邻居信息来表示节点之间的连接。

创建邻接表表示法

定义一个名为Graph的结构体，其中包含’value’和’neighbors’等属性。
创建一个节点结构体的数组（或向量），其索引表示节点的标签或标识符。
对于连接两个顶点A和B的每条边，在数组或向量的相应位置添加A和B作为邻居。

查找连接的组件

现在我们使用邻接表结构表示了我们的图，我们可以通过深度优先搜索（DFS）递归地找到每个节点的连接组件。

将所有节点初始化为未访问。
遍历每个未访问的节点。
- 在通过DFS探索从一个节点到另一个节点时，检查它们是否已经访问过。
- 如果尚未访问，则将其标记为已访问，并继续对其邻居进行DFS探索，直到没有更多未访问的邻居为止。
- 在DFS遍历期间访问到新发现的节点时，增加计数变量。
为每个单独的起始节点存储这些连接组件的数量。

用于从每个节点的构件大小构建图的C++代码

算法

第1步 − 包含所需的头文件。
第2步 − 创建一个带有ID和邻居向量的类Graph。
第3步 − 创建一个名为outputgraph()的函数，该函数接受一个名为components的pair向量和一个整数n。
第4步 − 创建一个unordered map mp来存储组件。
第5步 − 循环遍历组件并将它们添加到map中。
第6步 − 通过检查每个组件中的节点数量是否可以被组件大小整除来检查输入是否有效。
第7步 − 在给定的代码中，可能有两种情况不能运行代码。
第8步 − 第一种情况是输入本身是错误的，另一种情况是无法从输入的pair中形成边。
第9步 − 借助给定的组件大小和pair输入，可以构建图的边。

示例

//Including the required header files
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Graph {
   public:
      // unique identifier for each node
      // stores neighbor IDs
      int id;
      vector<int> neighbors;
    
      Graph() { }
    
      void addNeighbor(int neighborID) {
         neighbors.push_back(neighborID);
      }
};
//Defining the function with three parameters
//The parameters are the input pairs, their address of it, and the size
void outputgraph(vector<pair<int, int>> &components, int n) {
   unordered_map<int, vector<int>> mp;
   for (int m = 0; m < n; m++)//O(n) {
      mp[components[m].second].push_back(components[m].first);
   }

   bool noEdgesExist = true;
   for (auto a : mp)//O(n) {
      int component_size, num_nodes;
      component_size = a.first;
      num_nodes = a.second.size();
      if (component_size != 1)
         noEdgesExist = false;
      if (num_nodes % component_size != 0) {
         cout << "Valid Graph cannot be constructed\n";
         return;
      }
   }
   //If the edges could not be constructed using the given pairs this statement gets executed
   if (noEdgesExist){
      cout << "Edges cannot be constructed for this possible graph\n";
      return;
   }

   vector<pair<int, int>> edges;

   for (auto a : mp){
      vector<int> nodes = a.second;
      int component_size = a.first;

      // divide the nodes into groups of size= component_size
      int numGroups = nodes.size() / component_size;
      for (int m = 0; m < numGroups; m++){
         int start = m * component_size;
         for (int y = start + 1; y < start + component_size; y++){
            edges.push_back({nodes[y], nodes[y - 1]});
         }
      }
   }
   //for loop will iterate through the pairs
   for (int m = 0; m < edges.size(); m++){
      cout << edges[m].first << ", "
         << edges[m].second;
      if (m != edges.size() - 1){
         cout << ", ";
      }
   }

}
//main function to test the implemented functions

int main() {
//component size is initialized as 2
   int n = 2;
   vector<pair<int, int>> components{{1,2}, {2,2}, {3,1}, {4,1}, {5,1}, {6,1}};

   outputgraph(components, n);

   return 0;
}