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.

Anwendungsmethode

• Sequentielle Scheitelpunktsortierung

• Maximale erste Scheitelpunktsortierung

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

Algorithmus

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

Beispiel

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

Ausgabe

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

Maximale erste Scheitelpunktsortierung

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

Algorithmus

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

Beispiel

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

Ausgabe

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

Fazit

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!