Algoritma pewarnaan plot Welsh-Powell

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++.

Kaedah penggunaan

• Isih bucu berurutan

• Isihan bucu pertama maksimum

Isih Pucuk Berurutan

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.

Algoritma

• 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.

Contoh

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

Output

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

Isihan puncak pertama maksimum

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.

Algoritma

• 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.

Contoh

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

Output

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

Kesimpulan

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!