找到有限图G的顶点排序-Java 学习之路

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

算法正如Batagelj和Zaversnik（2003）所描述的那样，有可能找到有限图G的顶点排序，它通过重复去除最小程度的顶点，在线性时间内优化排序的着色数 . 更详细地，算法如下进行：

初始化输出列表L.
为G中的每个顶点v计算一个数字dv，v中的邻居数量不在L中 . 最初，这些数字只是顶点的度数 .
初始化数组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中减去1并将w移动到对应于dw的新值的D的单元格 .

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

这是我的代码（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;
}

找到有限图G的顶点排序

相关问题