Heim > Artikel > Backend-Entwicklung > Welsh-Powell-Plotfärbungsalgorithmus
Grafikfärbung ist ein zentrales Thema in der Informationstechnologie und findet breite Anwendung in Bereichen wie Terminplanung, Registerzuordnung und Kartenfärbung. Der Welsh-Powell-Algorithmus ist eine effiziente Methode zum Färben eines Diagramms und stellt sicher, dass benachbarte Scheitelpunkte eine Vielzahl von Schattierungen aufweisen, während weniger Farben verwendet werden. In diesem Artikel betrachten wir zwei Möglichkeiten, den Welsh-Powell-Algorithmus mithilfe von C++-Algorithmen zu erstellen.
Sequentielle Scheitelpunktsortierung
Maximale erste Scheitelpunktsortierung
Bei der ersten Technik werden den Scheitelpunkten Farben in absteigender Reihenfolge ihres Grades zugewiesen. Diese Technik stellt sicher, dass Scheitelpunkte größerer Ausdehnung, die normalerweise mehr Nachbarn haben, zuerst eingefärbt werden.
Bestimmen Sie die Ebene jedes Diagrammscheitelpunkts.
Bestimmen Sie den Grad der Scheitelpunkte und sortieren Sie sie in absteigender Reihenfolge.
Legen Sie die zugewiesene Farbe für jede Scheitelpunktposition im Array fest.
Wiederholen Sie Schritt 2 für die Eckpunkte in der hier festgelegten Reihenfolge.
Weisen Sie jedem Scheitelpunkt die Mindestfarbe zu, die noch nicht von den benachbarten Scheitelpunkten verwendet wird.
#include <iostream> #include <vector> #include <algorithm> using namespace std; // Graph structure struct Graph { int V; // Number of vertices vector<vector<int>> adj; // Adjacency list // Constructor Graph(int v) : V(v), adj(v) {} // Function to add an edge between two vertices void addEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } }; // Function to compare vertices based on weight bool compareWeights(pair<int, int> a, pair<int, int> b) { return a.second > b.second; } // Function to perform graph coloring using Welsh-Powell algorithm void graphColoring(Graph& graph) { int V = graph.V; vector<pair<int, int>> vertexWeights; // Assign weights to each vertex based on their degree for (int v = 0; v < V; v++) { int weight = graph.adj[v].size(); vertexWeights.push_back(make_pair(v, weight)); } // Sort vertices in descending order of weights sort(vertexWeights.begin(), vertexWeights.end(), compareWeights); // Array to store colors assigned to vertices vector<int> color(V, -1); // Assign colors to vertices in the sorted order for (int i = 0; i < V; i++) { int v = vertexWeights[i].first; // Find the smallest unused color for the current vertex vector<bool> usedColors(V, false); for (int adjVertex : graph.adj[v]) { if (color[adjVertex] != -1) usedColors[color[adjVertex]] = true; } // Assign the smallest unused color to the current vertex for (int c = 0; c < V; c++) { if (!usedColors[c]) { color[v] = c; break; } } } // Print the coloring result for (int v = 0; v < V; v++) { cout << "Vertex " << v << " is assigned color " << color[v] << endl; } } int main() { // Create a sample graph Graph graph(6); graph.addEdge(0, 1); graph.addEdge(0, 2); graph.addEdge(1, 2); graph.addEdge(1, 3); graph.addEdge(2, 3); graph.addEdge(3, 4); graph.addEdge(4, 5); // Perform graph coloring graphColoring(graph); return 0; }
Vertex 0 is assigned color 2 Vertex 1 is assigned color 0 Vertex 2 is assigned color 1 Vertex 3 is assigned color 2 Vertex 4 is assigned color 0 Vertex 5 is assigned color 1
Ähnlich wie bei Methode eins beinhaltet die zweite Methode die Anordnung der Scheitelpunkte in absteigender Reihenfolge basierend auf ihren Graden. Dieser Ansatz färbt zuerst den Scheitelpunkt höchster Ordnung und färbt dann rekursiv seine ungefärbten Nachbarn ein, anstatt Farben nacheinander zuzuweisen.
Bestimmen Sie den Grad jedes Diagrammscheitelpunkts.
Bestimmen Sie den Grad der Scheitelpunkte und sortieren Sie sie in absteigender Reihenfolge.
Legen Sie die zugewiesene Farbe für jede Scheitelpunktposition im Array fest.
Beginnen Sie mit der Schattierung vom Scheitelpunkt aus mit maximalem Grad.
Wählen Sie die kleinste verfügbare Farbe für jeden Nachbarn des derzeit ungefärbten Scheitelpunkts.
#include <iostream> #include <vector> #include <algorithm> #include <unordered_set> using namespace std; class Graph { private: int numVertices; vector<unordered_set<int>> adjacencyList; public: Graph(int vertices) { numVertices = vertices; adjacencyList.resize(numVertices); } void addEdge(int src, int dest) { adjacencyList[src].insert(dest); adjacencyList[dest].insert(src); } int getNumVertices() { return numVertices; } unordered_set<int>& getNeighbors(int vertex) { return adjacencyList[vertex]; } }; void welshPowellLargestFirst(Graph graph) { int numVertices = graph.getNumVertices(); vector<int> colors(numVertices, -1); vector<pair<int, int>> largestFirst; for (int i = 0; i < numVertices; i++) { largestFirst.push_back(make_pair(graph.getNeighbors(i).size(), i)); } sort(largestFirst.rbegin(), largestFirst.rend()); int numColors = 0; for (const auto& vertexPair : largestFirst) { int vertex = vertexPair.second; if (colors[vertex] != -1) { continue; // Vertex already colored } colors[vertex] = numColors; for (int neighbor : graph.getNeighbors(vertex)) { if (colors[neighbor] == -1) { colors[neighbor] = numColors; } } numColors++; } // Print assigned colors for (int i = 0; i < numVertices; i++) { cout << "Vertex " << i << " - Color: " << colors[i] << endl; } } int main() { Graph graph(7); graph.addEdge(0, 1); graph.addEdge(0, 2); graph.addEdge(0, 3); graph.addEdge(1, 4); graph.addEdge(1, 5); graph.addEdge(2, 6); graph.addEdge(3, 6); welshPowellLargestFirst(graph); return 0; }
Vertex 0 - Color: 0 Vertex 1 - Color: 0 Vertex 2 - Color: 1 Vertex 3 - Color: 1 Vertex 4 - Color: 0 Vertex 5 - Color: 0 Vertex 6 - Color: 1
In diesem Blogbeitrag werden zwei verschiedene Möglichkeiten zum Aufbau der Maltechnik für walisische Powell-Diagramme mithilfe von C++-Algorithmen analysiert. Jede Methode wendet beim Sortieren von Scheitelpunkten und beim Zuweisen von Farben eine andere Strategie an, was zu einer effizienten und optimierten Methode zum Färben von Diagrammen führt. Durch die Verwendung dieser Techniken können wir die Anzahl der erforderlichen Farben effektiv reduzieren und gleichzeitig sicherstellen, dass benachbarte Scheitelpunkte unterschiedliche Farben enthalten. Aufgrund seiner Anpassungsfähigkeit und Einfachheit bleibt der Welsh-Powell-Algorithmus ein nützliches Werkzeug für eine Vielzahl von Diagrammschattierungsanwendungen.
Das obige ist der detaillierte Inhalt vonWelsh-Powell-Plotfärbungsalgorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!