Mewarna grafik ialah isu utama dalam teknologi maklumat dan mempunyai aplikasi yang luas dalam bidang seperti penjadualan, peruntukan daftar dan pewarnaan peta. Algoritma Welsh-Powell ialah cara yang cekap untuk mewarnakan graf, memastikan bucu berdekatan mempunyai pelbagai warna semasa menggunakan lebih sedikit warna. Dalam artikel ini, kita akan melihat 2 cara untuk mencipta algoritma Welsh-Powell menggunakan algoritma C++.
Isih bucu berurutan
Isihan bucu pertama maksimum
Dalam teknik pertama, warna diberikan kepada bucu dalam tertib menurun darjahnya. Teknik ini memastikan bahawa bucu pada tahap yang lebih besar yang biasanya mempunyai lebih banyak jiran diwarnakan terlebih dahulu.
Tentukan tahap setiap bucu graf.
Tentukan darjah bucu dan susunkannya mengikut tertib menurun.
Tetapkan warna yang ditetapkan untuk setiap kedudukan bucu dalam tatasusunan.
Ulang langkah 2 untuk bucu dalam susunan yang ditentukan di sini.
Tentukan setiap bucu warna minimum yang belum digunakan oleh bucu jirannya.
#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
Sama seperti kaedah satu, kaedah kedua melibatkan penyusunan bucu dalam tertib menurun berdasarkan darjahnya. Pendekatan ini mewarnakan bucu darjah tertinggi dahulu dan kemudian mewarnai jiran yang tidak berwarna secara rekursif, dan bukannya memberikan warna secara berurutan.
Tentukan darjah setiap bucu graf.
Tentukan darjah bucu dan susunkannya mengikut tertib menurun.
Tetapkan warna yang ditetapkan untuk setiap kedudukan bucu dalam tatasusunan.
Mulakan teduhan dari puncak dengan darjah maksimum.
Pilih warna terkecil yang tersedia untuk setiap jiran bucu yang tidak berwarna pada masa ini.
#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
Catatan blog ini menganalisis dua cara berbeza untuk membina teknik pewarnaan rajah Welsh Powell menggunakan algoritma C++. Setiap kaedah menggunakan strategi berbeza apabila menyusun bucu dan menetapkan warna, menghasilkan kaedah pewarnaan graf yang cekap dan dioptimumkan. Dengan menggunakan teknik ini, kami boleh mengurangkan bilangan warna yang diperlukan dengan berkesan sambil memastikan bucu berdekatan mengandungi warna yang berbeza. Dengan kebolehsuaian dan kesederhanaannya, algoritma Welsh-Powell kekal sebagai alat yang berguna dalam pelbagai aplikasi lorekan graf.
Atas ialah kandungan terperinci Algoritma pewarnaan plot Welsh-Powell. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!