このアルゴリズムを C++ で実装しようとしましたが、いくつか問題があります。より速く適切に機能させる方法についてアドバイスが必要です。
アルゴリズム Batagelj & Zaversnik (2003) が説明しているように、最小次数の頂点を繰り返し削除することにより、線形時間で順序付けの彩色数を最適化する有限グラフ G の頂点順序付けを見つけることができます。より詳細には、アルゴリズムは次のように進みます。
- 出力リスト L を初期化します。
- G の各頂点 v の数 dv を計算します。これは、まだ L にない v の近傍の数です。最初は、これらの数は頂点の次数です。
- D[i] が dv = i である L にまだ存在しない頂点 v のリストを含むように、配列 D を初期化します。
- k を 0 に初期化します。
n 回繰り返します。
1. D[i] が空でない i が見つかるまで、配列セル D[0]、D[1]、... をスキャンします。
2.k を max(k,i) に設定します。
3.D[i]から頂点vを選ぶ。v を L の先頭に追加し、D[i] から削除します。
4. v の隣接 w ごとに、dw から 1 を引き、w を dw の新しい値に対応する D のセルに移動します。
アルゴリズムの最後で、k には G の縮退が含まれ、L には色番号の最適な順序で頂点のリストが含まれます。G の i-core は、k が最初に i 以上の値を取った後に L に追加された頂点から構成される L のプレフィックスです。変数 L、dv、D、および k の初期化は、線形時間で簡単に実行できます。連続して削除された各頂点 v を見つけ、v の近傍を含む D のセルを調整するには、そのステップでの dv の値に比例する時間がかかります。ただし、これらの値の合計はグラフのエッジの数です (各エッジは、2 つのエンドポイントの後半の合計の項に寄与します)。したがって、合計時間は線形です。
これが私のコードです（Susedia = Neighbors）
int his_place_inArray(int x,vector<int> A)
{
for(int i=0;i<A.size();i++)
if(*(A.begin()+i)==x) return i;
}
vector<int> vertex_ordering(vector<int> A) {
vector<int> L;
vector<vector<int>> D(100);
vector<int> d(A.size());
vector<int> N; //tsusedia
//Compute a number dv for each vertex v in G, the number of neighbors of v
//that are not already in L. Initially, these numbers are just the degrees
//of the vertices.
for (int i = 0; i < A.size(); i++) {
N = susedia(A[i], L);
d[i] = N.size();
//Initialize an array D such that D[i] contains a list of the vertices
//v that are not already in L for which dv = i.
D[d[i]].push_back(A[i]);
}
int i;
int k = 0; //Initialize k to 0.
int chosen; //chosen
vector<int> chosen_N; //Neighbors of chosen
for (int j = 0; j < A.size(); j++) { //for n times
for (i = 0; i < 10; i++) {
if (D[i].empty() == false) {
k = max(k, i);
break;
}
}
chosen = D[i][0];
L.push_back(chosen);
D[i].erase(D[i].begin());
chosen_N = susedia(chosen, L);
int n; //neighbor
//For each neighbor w of v, subtract one from dw and move w to the cell of D corresponding to the new value of dw.
for (int w = 0; w < chosen_N.size(); w++) {
n = chosen_N[w];
int p = his_place_inArray(n,A); //chosen neighbor place in A
int p_inD = his_place_inArray(n,D[d[p]]); //chosen neighbor place in D
D[d[p]].erase(D[d[p]].begin()+p_inD);
d[p]--;
D[d[p]].push_back(n);
}
}
return L;
}