无向图中简单环的数量 (N个顶点)

---

引言

无向图是计算机科学和图论中的一个重要组成部分，它表示一组由边连接的节点，这些边没有方向性。与无向图相关的常见问题之一是计算简单环或回路的数量，简单环是指仅访问每个顶点一次的闭合路径。在本文中，我们将探讨如何使用功能强大的编程语言C和C++来计算具有N个顶点的给定无向图中简单环的总数。

无向图

在我们开始编码之前，让我们确保每个人都理解无向图中简单环的构成。

让我们考虑一个具有四个顶点（N=4）的无向图，如下所示：

在这个例子中，每个简单环都从一个顶点开始，并以同一个顶点结束，访问所有四个顶点，同时确保每个节点只访问一次。

图的表示

首先，为我们的图创建一个合适的表示至关重要。最常用的方法是使用邻接表或邻接矩阵。

• 邻接表 - 每个节点存储与其相邻节点的连接。

• 邻接矩阵 - 使用一个方阵，其中行和列表示顶点，填充的值表示边的连接。

深度优先搜索 (DFS)

下一步是对我们的图进行深度优先搜索，从每个可能的顶点开始，如下所示：

• 递归地访问每个未访问的相邻顶点，直到到达一个先前访问过的节点（环的闭合）。

• 为了区分同时探索的不同路径，在DFS遍历期间标记已访问的节点。

• 在DFS实现过程中跟踪所有遇到的唯一环，以便进一步分析。

计算简单环

为了有效地获得整个图的准确计数，需要结合以下要素：

• 从每个顶点分别运行DFS，并使用布尔数组维护先前访问过的节点的信息。

• 在每次递归调用期间跟踪路径，并维护一个已访问节点列表以检测环的形成。

• 通过附加初始顶点来存储每个发现的环，以创建一个完整的循环。

C++程序：计算具有N个顶点的给定无向图中的简单环数量

简单环的数量使用给定邻接矩阵中的递归函数计算。

算法

• 步骤1 - 使用包含C++中所有函数的全包头文件。

• 步骤2 - “V”变量用整数数据类型初始化。

• 步骤3 - 已访问的顶点表示为“vis”，它包含布尔数组以获取环的数量。

• 步骤4 - 使用的图是动态规划，它是一个函数，它采用三个参数作为起始顶点、当前顶点和环的长度。

• 步骤5 - 假设当前顶点已被访问，for循环将遍历邻接矩阵值的每个节点。

• 步骤6 - 当下一个顶点是起始顶点时，计数将递增。

• 步骤7 - 根据矩阵值，将返回无向图计数。

示例

//using the required header files which includes all the header within it
#include <bits/stdc++.h> 
using namespace std;

// Adjacency matrix is represented in an array
void Vertex(int V, vector<vector<int> > graph) {
   // Declaring the variable count with a value of 0
   int count = 0;
   int dp[(1 << V)][V];

   // Declaring with a value of 0
   memset(dp, 0, sizeof dp);

   // for loop will iterate through 
   for (int num = 0;
      num < (1 << V); num++) {

         // To get the number of bits
         int nodes
         = __builtin_popcountll(num);
         // To find the first bit
         int first
         = __builtin_ffsl(num);
		
         if (nodes == 1) {

            // Declaring with a value of 1
            dp[num][first] = 1;
         } else {

            // Resetting visited array before each traversal
            // Dynamic programming starts from vertex i where the current cycle has only one node and increments the value by 1
            for (int val = first + 1;
               val < V; val ++) {
				
            if ((num & (1 << val))) {
					
               int newnum = num ^ (1 << val);
   
               for (int k = 0; k < V; k++) {

                  if ((newnum & (1 << k)) && graph[k][val]) {
                     dp[num][val]
                     += dp[newnum][k];

                     //Graph connected to the first node
                     if (graph[val][first] && nodes > 2)
                        count += dp[num][val];
                  }
               }
            }
         }
      }
   }

   // Getting the final answer
   cout << count << endl;
}

// main function
int main() {
   // In the graph, the vertices in initialized with a value of 4
   int V = 4; 
  
   // Declaring the input as adjacency matrix
   vector<vector<int> > graph = { { 1, 1, 1, 1 }, 
      { 1, 0, 1, 1 }, 
      { 1, 1, 0, 1 }, 
      { 1, 1, 1, 0 } };

   Vertex(V, graph);

   return 0;
}

输出

2

结论

通过本文中的详细描述以及提供的C++实现示例，我们现在可以解决涉及计算简单环的类似问题。在处理各种具有挑战性的问题时，计算给定图中的环至关重要。通过使用深度优先搜索和适当的数据结构来有效地描述图，可以进行此类计算。