C++ 检查图中的每个顶点三元组是否含有与第三个顶点相连的两个顶点

检查图中的每个顶点三元组，看看其中有没有两个顶点直接连接到第三个顶点。这个属性很重要，因为它表明顶点们之间是强相关的，有很多的连接关系。需要有效和直接连接实体的应用，如社交网络、交通网络和通信网络，都依赖于这种连接性。通过确认每个顶点三元组是否满足这个条件，可以评估图的整体结构对所代表的系统的连接性和潜在影响，并帮助分析和优化网络的性能和功能。

使用的方法

暴力方法
深度优先搜索（DFS）方法

暴力方法

在暴力方法中，会对图中的每个顶点三元组进行彻底检查，看看其中是否有两个顶点与第三个顶点相连。该方法通过遍历所有可能的三元组组合，检查每个三元组是否满足所需的连接关系。该方法的时间复杂度为O(V3)，其中V为顶点的数量，但对于大型图可能效率不高。虽然直观简单，但对于非常大的图可能没有用处。因此，为了在更大的图上进行更快、更有效的检查，更优化的算法如DFS、BFS或使用邻接矩阵/边列表表示更受青睐。

步骤

从图中选取一个顶点，我们称之为“v”，作为起始点。
针对图中的每对“u”和“w”（与“v”不同）顶点执行以下操作：
- 确认“u”和“w”之间是否有边界。
- 如果“u”和“w”之间有边界，则查看是否也存在“v”与“u”和“w”之间的边界。
- 如果“v”与“u”和“w”之间都有边界，则转到接下来的一对顶点，即分别是“w”。
- 如果“v”与“u”或“w”之间没有边界，则返回“False”，因为三元组的条件不满足。
如果所有三元组（“u”，“v”和“w”的三元组组合）都满足条件，则返回“True”。
如果任何一个三元组不满足要求，则返回“False”。

示例

#include <iostream>
#include <vector>
using namespace std;

bool checkTripletCondition(const vector<vector<int>>& graph) {
   int n = graph.size();
   for (int v = 0; v < n; v++) {
      for (int u : graph[v]) {
         for (int w : graph[v]) {
            if (u != v && w != v) {
               bool hasEdgeUV = false;
               bool hasEdgeVU = false;
               bool hasEdgeVW = false;
               bool hasEdgeWV = false;

               for (int x : graph[u]) {
                  if (x == v) hasEdgeUV = true;
               }

               for (int y : graph[v]) {
                  if (y == u) hasEdgeVU = true;
                  if (y == w) hasEdgeVW = true;
               }

               for (int z : graph[w]) {
                  if (z == v) hasEdgeWV = true;
               }

               if (hasEdgeUV && hasEdgeVW && hasEdgeWV) continue;
               else return false;
            }
         }
      }
   }
   return true;
}

int main() {
   vector<vector<int>> graph = {
      {1, 2},
      {0, 2},
      {0, 1, 3},
      {2}
   };

   cout << boolalpha << checkTripletCondition(graph) << endl;
   return 0;
}

输出

true

深度优先搜索（DFS）方法

深度优先搜索（DFS）方法是一种有序地遍历图的方法，从选择的顶点开始，以确定图中的每个顶点三元组是否包含两个与第三个顶点相连的顶点。对于它遇到的每个顶点三元组，算法探索所有可能的路径，并确定是否存在必要的连接。通过查看顶点的邻居，DFS有效地确定三元组的两个顶点是否相连。如果所有三元组满足要求，则算法为整个图验证该属性。DFS是一种强大且受欢迎的图探索方法，提供了一种验证上下文中连接要求的有用方式。

步骤

创建一个标志变量，并将其设置为true，以监视每个三元组是否满足要求。
DFS遍历应该从图中的每个顶点开始。
对于DFS遍历过程中遇到的每个顶点“v”，调查其邻居（相邻顶点）。
检查是否存在“v”的邻居“u”和“w”之间的边。
检查是否存在“u”和“w”之间的边，以确定“v”是否与“u”和“w”都相连。
如果任何三元组不满足条件，则将标志变量设置为false并结束该遍历的DFS。
直到标志变量对于任何三元组被改变为false，或者在DFS遍历过程中访问了所有顶点为止。
如果在DFS遍历之后，标志变量仍然保持为true，则表示图中的每个顶点三元组都包含两个与第三个顶点相连的顶点。如果不是这样，则即使是最小的三元组也无法满足需求。

示例

#include <iostream>
#include <vector>
using namespace std;

class Graph {
private:
   int V;
   vector<vector<int>> adj;

public:
   Graph(int V) : V(V) {
      adj.resize(V);
   }

   void addEdge(int u, int v) {
      adj[u].push_back(v);
      adj[v].push_back(u);
   }

   bool checkTriplets() {
      bool flag = true;

      for (int i = 0; i < V && flag; ++i) {
         vector<bool> visited(V, false);
         flag = flag && dfs(i, -1, visited);
      }

      return flag;
   }

   bool dfs(int curr, int parent, vector<bool>& visited) {
      visited[curr] = true;
      int connectedCount = 0;

      for (int neighbor : adj[curr]) {
         if (neighbor != parent) {
            if (visited[neighbor]) {
               connectedCount++;
            } else {
               if (!dfs(neighbor, curr, visited))
                  return false;
            }
         }
      }

      return connectedCount >= 2;
   }
};

int main() {
   Graph graph(6);

   graph.addEdge(0, 1);
   graph.addEdge(1, 2);
   graph.addEdge(1, 3);
   graph.addEdge(2, 3);
   graph.addEdge(3, 4);
   graph.addEdge(4, 5);

   bool result = graph.checkTriplets();
   cout << "Requirement Met: " << boolalpha << result << endl;

   return 0;
}