根据每个节点的组件大小构建图

简介

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

根据每个节点的组件大小构建图

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

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

创建邻接表表示

  • 定义一个名为 Graph 的结构体，其中包含“值”和“邻居”等属性。

  • 创建一个 Node 结构体的数组（或向量）；其索引表示节点标签或标识符。

  • 对于连接两个顶点 A 和 B 的每条边，在数组或向量中各自对应的位置下将 A 和 B 作为邻居添加。

查找连通分量

现在我们已经使用邻接表结构表示了我们的图，我们可以通过深度优先搜索 (DFS) 递归地查找每个节点的连通分量。

  • 将所有节点初始化为未访问状态。

  • 遍历每个未访问的节点。

    • 当通过 DFS 探索从一个节点遍历到另一个节点时，检查它们是否已被访问。

    • 如果尚未访问，则将其标记为已访问，并继续对其邻居进行 DFS 探索，直到没有更多未访问的邻居为止。

    • 在 DFS 遍历期间访问新发现的节点时，增加计数变量。

  • 存储每个单独起始节点的连通分量计数。

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

算法

  • 步骤 1 - 包含所需的标头文件。

  • 步骤 2 - 创建一个带有 ID 和邻居向量的类 Graph。

  • 步骤 3 - 创建一个函数 outputgraph()，它接收一对向量 components 和一个整数 n。

  • 步骤 4 - 创建一个无序映射 mp 来存储组件。

  • 步骤 5 - 循环遍历组件并将它们添加到映射中。

  • 步骤 6 - 通过检查每个组件中的节点数量是否可被组件的大小整除来检查输入是否有效。

  • 步骤 7 - 在给定的代码中，可能存在两个无法运行代码的可能性。

  • 步骤 8 - 第一种情况是输入本身错误，另一种情况是无法从输入对形成边。

  • 步骤 9 - 可以借助给定的组件大小和对的输入来构建图的边。

示例

//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;
}

输出

2,1

结论

该代码运行并根据输入对和组件大小使用类方法以及布尔功能给出边对。通过本文中的详细描述和提供的 C++ 实现示例，我们现在可以解决涉及构建图的类似问题。

更新于： 2023-08-25

146 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告