最大化图中与所有其他节点断开连接的节点数量

我们必须找到并隔离连接最少的节点，以便最大化图中与所有其他节点断开连接的节点数量。该策略需要重复消除度数最低（连接最少）的节点，直到找不到更多这些节点。这样做的结果是提供彼此分离的最大数量的节点，从而不断隔离图中的不同组件。该策略通过保证其余节点可以忽略不计地关联，从而扩展了图中与任何其他节点没有关联的节点的数量。

使用的方法

• 贪婪方法

• 最大独立集 (MIS) 方法

贪婪方法

贪婪方法涉及重复删除度数最低（连接最少）的节点，以便最大化图中未连接到任何其他节点的节点数量。直到不再有这样的节点为止，该过程将继续进行。通过重复消除连接最少的节点来增加孤立节点的数量，以便在图中创建断开连接的组件。重要的是要记住，贪婪方法可能无法持续保证精确的最大断开节点数量，因此可能会根据节点被消除的顺序而变化。尽管如此，它提供了一种简单且成功的策略来增加图中未连接的节点的数量。

算法

• 从初始图 G 开始。

• 在开头创建一个空列表来存储断开连接的节点。

• 重复以下步骤，直到无法删除更多节点：

a.在当前图 G 中，识别度数最低（连接最少）的节点。

b.如果有多个节点具有相同的最低度数，则选择任意节点。

c.将所选节点从图 G 中删除后添加到断开连接的节点列表中。

• 继续搜索，直到没有剩下最低度数的节点。

• 图表中相互隔离的节点数量由策略结束时获得的撤回节点列表表示。

示例

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Graph {
   int V;
   vector<vector<int>> adj;

   Graph(int vertices) : V(vertices) {
      adj.resize(V, vector<int>());
   }

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

   int findLowestDegreeNode() {
      int minDegree = V + 1;
      int node = -1;

      for (int i = 0; i < V; ++i) {
         if (adj[i].size() < minDegree) {
            minDegree = adj[i].size();
            node = i;
         }
      }

      return node;
   }

   vector<int> getDisconnectedNodes() {
      vector<int> disconnected;
      while (true) {
         int node = findLowestDegreeNode();
         if (node == -1)
            break;

         disconnected.push_back(node);
         for (int neighbor : adj[node]) {
            adj[neighbor].erase(remove(adj[neighbor].begin(), adj[neighbor].end
(), node), adj[neighbor].end());
         }
         adj[node].clear();
      }
      return disconnected;
   }
};

void printGraph(Graph& G) {
   for (int i = 0; i < G.V; ++i) {
      cout << "Node " << i << " : ";
      for (int neighbor : G.adj[i]) {
         cout << neighbor << " ";
      }
      cout << endl;
   }
}

int main() {
   Graph G(5);
   G.addEdge(0, 1);
   G.addEdge(0, 2);
   G.addEdge(1, 2);
   G.addEdge(3, 4);

   cout << "Initial Graph:" << endl;
   printGraph(G);

   G.getDisconnectedNodes();

   cout << "Graph after removing nodes:" << endl;
   printGraph(G);

   return 0;
}

输出

Initial Graph:
Node 0 : 1 2 
Node 1 : 0 2 
Node 2 : 0 1 
Node 3 : 4 
Node 4 : 3 

最大独立集 (MIS) 方法

最大独立集 (MIS) 方法旨在识别其中没有两个节点相邻（连接）的节点的最大可行子集，目的是增加图中与所有其他节点断开连接的节点数量。查找图中没有共享边的节点并将它们添加到独立集中的过程就是这样。通过最大化断开连接的节点数量，这可以确保所选节点不会相互连接。随着算法的继续，选定的节点及其邻居将从图中迭代地删除。通过重复此过程，直到无法将更多节点添加到独立集中，我们获得了图中与每个其他节点断开连接的节点的最大数量。

算法

• 从初始图 G 开始。

• 要存储最大独立集 (MIS)，请初始化一个空集。

• 重复以下步骤，直到无法向 MIS 添加更多节点为止：

a.定位当前图 G 中的一个节点，该节点未通过任何公共边或邻居连接到任何其他节点。

b.将选定的节点包含在 MIS 集中。

c.从图 G 中减去所选节点及其邻居。

• 继续执行此操作，直到 MIS 集不再包含任何节点。

示例

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

class Graph {
private:
   vector<set<int>> adjacencyList;
public:
   Graph(int numNodes) : adjacencyList(numNodes) {}
   void addEdge(int u, int v);
   set<int> findIndependentSet();
};

void Graph::addEdge(int u, int v) {
   adjacencyList[u].insert(v);
   adjacencyList[v].insert(u);
}

set<int> Graph::findIndependentSet() {
   set<int> independentSet;
   vector<bool> included(adjacencyList.size(), false);
   
   while (true) {
      int nodeToAdd = -1;
      for (int i = 0; i < adjacencyList.size(); ++i) {
         if (!included[i]) {
            bool canAdd = true;
            for (const int& neighbor : adjacencyList[i]) {
               if (included[neighbor]) {
                  canAdd = false;
                  break;
               }
            }
            if (canAdd) {
               nodeToAdd = i;
               break;
            }
         }
      }
      if (nodeToAdd == -1) {
         break;
      }
      independentSet.insert(nodeToAdd);
      included[nodeToAdd] = true;
      for (const int& neighbor : adjacencyList[nodeToAdd]) {
         included[neighbor] = true;
      }
   }
   return independentSet;
}

int main() {
   // Example graph with 7 nodes and 6 edges
   Graph graph(7);
   graph.addEdge(0, 1);
   graph.addEdge(0, 2);
   graph.addEdge(1, 3);
   graph.addEdge(1, 4);
   graph.addEdge(2, 5);
   graph.addEdge(2, 6);

   set<int> maxIndependentSet = graph.findIndependentSet();
   for (const int& node : maxIndependentSet) {
      cout << node << " ";
   }
   cout << endl;

   return 0;
}

输出

0

结论

我们使用两种主动方法，即贪婪方法和最大独立集 (MIS) 方法，来最大化图中相互断开的节点数量。贪婪方法涉及创建断开连接的组件、重复删除度数最低的节点以及增加孤立节点的数量。虽然简单，但它可能并不总是确保精确的最大计数。另一方面，MIS 方法试图通过定位没有任何相邻连接的最大可行节点子集来将节点彼此隔离。 MIS 方法提供了一种更可靠的方法，通过迭代地将节点添加到独立集中并将它们及其邻居从图中删除，有条不紊地达到断开节点的最大数量。

以上是最大化图中与所有其他节点断开连接的节点数量的详细内容。更多信息请关注PHP中文网其他相关文章！