Maximieren Sie die Anzahl der Knoten im Diagramm, die von allen anderen Knoten getrennt sind

Wir müssen die am wenigsten verbundenen Knoten finden und isolieren, um die Anzahl der Knoten im Diagramm zu maximieren, die von allen anderen Knoten getrennt sind. Diese Strategie erfordert die wiederholte Eliminierung von Knoten mit dem niedrigsten Grad (am wenigsten verbunden), bis keine dieser Knoten mehr gefunden werden können. Das Ergebnis ist, dass eine maximale Anzahl voneinander getrennter Knoten bereitgestellt wird, wodurch unterschiedliche Komponenten im Diagramm ständig isoliert werden. Diese Strategie erhöht die Anzahl der Knoten im Diagramm, die nicht mit anderen Knoten verknüpft sind, indem sichergestellt wird, dass die verbleibenden Knoten vernachlässigbar verknüpft sind.

Anwendungsmethode

• Gierige Methode

• Maximum Independent Set (MIS)-Methode

Gierige Methode

Bei der gierigen Methode werden die Knoten mit dem niedrigsten Grad (am wenigsten verbunden) wiederholt entfernt, um die Anzahl der Knoten im Diagramm zu maximieren, die mit keinem anderen Knoten verbunden sind. Der Prozess wird fortgesetzt, bis keine solchen Knoten mehr vorhanden sind. Erhöhen Sie die Anzahl der verwaisten Knoten, indem Sie wiederholt die am wenigsten verbundenen Knoten entfernen, um nicht verbundene Komponenten im Diagramm zu erstellen. Es ist wichtig zu bedenken, dass der Greedy-Ansatz möglicherweise nicht immer die genaue maximale Anzahl getrennter Knoten garantiert und daher je nach der Reihenfolge, in der Knoten entfernt werden, variieren kann. Dennoch bietet es eine einfache und erfolgreiche Strategie, um die Anzahl der nicht verbundenen Knoten im Diagramm zu erhöhen.

Algorithmus

• Beginnen Sie mit dem Anfangsdiagramm G.

• Erstellen Sie zu Beginn eine leere Liste, um nicht verbundene Knoten zu speichern.

• Wiederholen Sie die folgenden Schritte, bis keine Knoten mehr gelöscht werden können:

a. Identifizieren Sie im aktuellen Diagramm G den Knoten mit dem niedrigsten Grad (am wenigsten verbunden).

b. Wenn es mehrere Knoten mit demselben Mindestgrad gibt, wählen Sie einen beliebigen Knoten aus.

c. Fügen Sie den ausgewählten Knoten zur Liste der nicht verbundenen Knoten hinzu, nachdem Sie ihn aus dem Diagramm G entfernt haben.

• Suchen Sie weiter, bis keine Knoten mit dem niedrigsten Grad mehr vorhanden sind.

• Die Anzahl der voneinander isolierten Knoten im Diagramm wird durch die Liste der zurückgezogenen Knoten dargestellt, die am Ende der Strategie erhalten wird.

Beispiel

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

Ausgabe

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

Maximum Independent Set (MIS)-Methode

Die Maximum Independent Set (MIS)-Methode zielt darauf ab, die größtmögliche Teilmenge von Knoten zu identifizieren, in der keine zwei Knoten benachbart (verbunden) sind, mit dem Ziel, die Anzahl der Knoten im Diagramm zu erhöhen, die von allen anderen Knoten getrennt sind. Dabei handelt es sich um den Prozess, Knoten im Diagramm zu finden, die keine gemeinsamen Kanten haben, und sie einer unabhängigen Menge hinzuzufügen. Dadurch wird sichergestellt, dass ausgewählte Knoten nicht miteinander verbunden sind, indem die Anzahl der getrennten Knoten maximiert wird. Während der Algorithmus fortfährt, werden ausgewählte Knoten und ihre Nachbarn iterativ aus dem Diagramm entfernt. Indem wir diesen Vorgang wiederholen, bis der unabhängigen Menge keine weiteren Knoten mehr hinzugefügt werden können, erhalten wir die maximale Anzahl von Knoten, die von allen anderen Knoten im Diagramm getrennt sind.

Algorithmus

• Beginnen Sie mit dem Anfangsdiagramm G.

• Um Maximum Independent Set (MIS) zu speichern, initialisieren Sie einen leeren Satz.

• Wiederholen Sie die folgenden Schritte, bis dem MIS keine Knoten mehr hinzugefügt werden können:

a. Suchen Sie einen Knoten im aktuellen Diagramm G, der nicht über gemeinsame Kanten oder Nachbarn mit einem anderen Knoten verbunden ist.

b.Ausgewählte Knoten in den MIS-Satz aufnehmen.

c. Subtrahieren Sie den ausgewählten Knoten und seine Nachbarn vom Diagramm G.

• Fahren Sie damit fort, bis der MIS-Satz keine Knoten mehr enthält.

Beispiel

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

Ausgabe

0

Fazit

Wir verwenden zwei aktive Methoden, die Greedy-Methode und die Maximum Independent Set (MIS)-Methode, um die Anzahl der Knoten im Diagramm zu maximieren, die nicht miteinander verbunden sind. Bei gierigen Methoden werden getrennte Komponenten erstellt, wiederholt Knoten mit dem niedrigsten Grad gelöscht und die Anzahl verwaister Knoten erhöht. Obwohl es einfach ist, gewährleistet es möglicherweise nicht immer eine genaue Maximalzählung. MIS-Methoden hingegen versuchen, Knoten voneinander zu isolieren, indem sie die größtmögliche Teilmenge von Knoten ohne benachbarte Verbindungen lokalisieren. Die MIS-Methode bietet eine zuverlässigere Möglichkeit, die maximale Anzahl getrennter Knoten methodisch zu erreichen, indem Knoten iterativ zur unabhängigen Menge hinzugefügt und sie und ihre Nachbarn aus dem Diagramm entfernt werden.

Das obige ist der detaillierte Inhalt vonMaximieren Sie die Anzahl der Knoten im Diagramm, die von allen anderen Knoten getrennt sind. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!