1

我试图在 C++ 中实现这个算法，但它有一些问题。我需要一些建议如何让它更快、更正确地工作。

算法 正如 Batagelj & Zaversnik (2003) 所描述的，有可能找到有限图 G 的顶点排序，通过重复删除最小度数的顶点，在线性时间内优化排序的着色数。更详细地说，算法进行如下：

  • 初始化一个输出列表 L。
  • 为 G 中的每个顶点 v 计算一个数字 dv，即不在 L 中的 v 的邻居数。最初，这些数字只是顶点的度数。
  • 初始化一个数组 D，使得 D[i] 包含一个顶点 v 的列表，这些顶点 v 不在 L 中，其中 dv = i。
  • 将 k 初始化为 0。

  • 重复n次：

    1. 扫描数组单元 D[0], D[1], ... 直到找到 D[i] 不为空的 i。

    2.将k设置为max(k,i)

    3.从D[i]中选择一个顶点v。将 v 添加到 L 的开头并将其从 D[i] 中删除。

    4. 对于 v 的每个邻居 w，从 dw 中减去一个并将 w 移动到与 dw 的新值对应的 D 的单元格中。

在算法结束时，k 包含 G 的简并性，L 包含一个顶点列表，该列表以着色数的最佳顺序排列。G 的 i 核是 L 的前缀，由在 k 首先取大于或等于 i 的值之后添加到 L 的顶点组成。初始化变量 L、dv、D 和 k 可以很容易地在线性时间内完成。找到每个连续移除的顶点 v 并调整包含 v 邻居的 D 的单元格所花费的时间与该步骤中 dv 的值成正比；但是这些值的总和是图的边数（每条边都对两个端点中的后者的总和中的项有贡献），因此总时间是线性的。

这是我的代码（Susedia = 邻居）

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

0 回答 0