A Cuthill-McKee-algoritmus egy gráf-alapú rendezési algoritmus, amelyet ritka mátrixok szerkezeti sávszélességének minimalizálására használnak. Az algoritmus célja a mátrix sorainak és oszlopainak újrarendezése oly módon, hogy a nem nulla elemek a mátrix átlójához közelebb kerüljenek, ezáltal csökkentve a mátrix sávszélességét.
CuthillMcKee(G):
kezdet = válassz egy csúcsot minimális fokszámmal
queue = üres sor
látogatott = üres halmaz
rendezés =
queue.push(kezdet)
látogatott.add(kezdet)
amíg queue nem üres:
u = queue.pop()
rendezés.append(u)
szomszédok = G szomszédai
szomszédok.sort(fokszám szerint növekvő sorrendben)
minden v szomszéd in szomszédok:
ha v nincs látogatottban:
látogatott.add(v)
queue.push(v)
térj vissza rendezés
from collections import deque, defaultdict
def cuthill_mckee(graph):
# Kezdeti csúcs választása minimális fokszám alapján
start = min(graph.keys(), key=lambda x: len(graph))
# Kezdjük az algoritmust
visited = set()
queue = deque()
ordering =
while queue:
node = queue.popleft()
if node not in visited:
visited.add(node)
ordering.append(node)
# Szomszédok rendezése fokszám szerint növekvő sorrendben
neighbors = sorted(graph, key=lambda x: len(graph))
for neighbor in neighbors:
if neighbor not in visited:
queue.append(neighbor)
return ordering
# Példa gráf reprezentáció
graph = {
0: ,
1: ,
2: ,
3: ,
4:
}
ordering = cuthill_mckee(graph)
print("Cuthill-McKee rendezés:", ordering)
Kimenet:
Cuthill-McKee rendezés:
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
using namespace std;
vector<int> cuthill_mckee(const unordered_map<int, vector<int>>& graph) {
// Kezdeti csúcs választása minimális fokszám alapján
int start = -1;
int min_degree = INT_MAX;
for (const auto& : graph) {
if (neighbors.size() < min_degree) {
min_degree = neighbors.size();
start = node;
}
}
// Algoritmus inicializálása
unordered_set<int> visited;
queue<int> q;
vector<int> ordering;
q.push(start);
visited.insert(start);
while (!q.empty()) {
int node = q.front();
q.pop();
ordering.push_back(node);
vector<int> neighbors = graph.at(node);
sort(neighbors.begin(), neighbors.end(), (int a, int b) {
return graph.at(a).size() < graph.at(b).size();
});
for (int neighbor : neighbors) {
if (visited.find(neighbor) == visited.end()) {
visited.insert(neighbor);
q.push(neighbor);
}
}
}
return ordering;
}
int main() {
unordered_map<int, vector<int>> graph = {
{0, {1, 2}},
{1, {0, 2, 3}},
{2, {0, 1, 3}},
{3, {1, 2, 4}},
{4, {3}}
};
vector<int> ordering = cuthill_mckee(graph);
cout << "Cuthill-McKee rendezés: ";
for (int node : ordering) {
cout << node << " ";
}
cout << endl;
return 0;
}
Kimenet:
Cuthill-McKee rendezés: 0 1 2 3 4
A Cuthill-McKee algoritmus eredményének megfordítása (azaz a sorrend visszafelé történő bejárása) gyakran tovább csökkenti a sávszélességet. Ehhez az algoritmus végén egyszerűen megfordítjuk az eredményt:
ordering.reverse()
print("Fordított Cuthill-McKee rendezés:", ordering)
A Cuthill-McKee-algoritmus egyszerűsége és hatékonysága miatt népszerű numerikus matematikai alkalmazásokban, különösen ritka mátrixok optimalizálásában.