c - 如何对一个数组进行排序，该数组取决于其他数组的数量？

例如我有这个数组：

G->colour = [2,1,0,1,0,1,0,1,2];
G->vertex = [1,2,3,4,5,6,7,8,9];
G->order = [1,2,3,4,5,6,7,8,9]; //the same of vertex

顶点1具有颜色2，顶点2具有颜色1，依此类推...
我需要此解决方案G->order = [1,9,3,5,7,2,4,6,8]。我想使用相同颜色的顶点数量以增长顺序进行排序，即


我有两个具有颜色2的顶点（顶点：1、9）
我有三个顶点，颜色为0（顶点：3、5、7）
我有四个颜色为1的顶点（顶点：2、4、6、8）


我有一个函数（RMBC），可以按颜色对顶点进行排序。例如：

G->colour = [2,1,0,1,0,1,0,1,2];
G->order = [1,2,3,4,5,6,7,8,9];

这将返回函数order = [3,5,7,2,4,6,8,1,9]。

此外，我放置了图结构，以及为顶点着色的贪婪函数。

我有更多的代码，但是我认为这很不错。

谢谢！

typedef struct Graph
{
    u32** vecinos;
    u32* vertexes;  // Position of vertexes
    u32* color; //Structure type declarations do not support initializers
    u32* grados;
    u32* order; //it has the order of vertex for greedy
    u32* visitados;
    u32 m; //number of edges
    u32 n; // number of vertex
    u32 max; // number of colors
    u32* indEnVecinos;
} Graph;

//RMBC
u32* vert_color;
char RMBC(Graph* G)
{
    vert_color = G->color;
    qsort(G->order, G->n, sizeof(u32), compColoresNormal);
    return 0;
}

int compColoresNormal(const void *v1, const void *v2) {
    u32 color1 = vert_color[*(const u32 *)v1 - 1];
    u32 color2 = vert_color[*(const u32 *)v2 - 1];
    if (color1 < color2)
    {
        return -1;
    }
    else if (color1 > color2)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
// end RMBC

//Greedy
u32 Greedy(Graph* G)
{
    u32** aux = G->vecinos;
    u32 max_color = 0;
    u32 nVer = G->n;
    u32* color_vecinos = (u32*)malloc(sizeof(u32) * nVer);
    memset(color_vecinos,0,nVer*sizeof(u32));
    u32 indice = binarySearch(G->vertexes,0,nVer-1,G->order[0]);
    G->color[indice] = 0;
    G->visitados[indice] = 1;
    u32 indice2 = 0;
    u32 reset = 0;
    for (u32 i = 1; i < nVer; ++i)
    {
        memset(color_vecinos,0,(reset+1)*sizeof(u32));
        indice = binarySearch(G->vertexes,0,nVer-1,G->order[i]);
        G->visitados[indice] = 1;
        u32 color = 0;
        reset = 0;
        for (u32 i = 0; i < G->grados[indice]; ++i)
        {
            indice2 = binarySearch(G->vertexes,0,nVer-1,aux[G->indEnVecinos[indice]+i][1]);
            if(G->visitados[indice2])
            {
                color_vecinos[G->color[indice2]] = 1;
                if(reset < G->color[indice2]) reset = G->color[indice2];
            }
        }
        for (u32 i = 0; i < nVer; ++i)
        {
            if(!color_vecinos[i])
            {
                color = i;
                break;
            }
        }
        G->color[indice] = color;
        if(color > max_color) max_color = color;
        if(reset < color) reset = color;
        if(reset == nVer) reset--;
    }
    free(color_vecinos);
    printf("terminé Greedy\n");
    return max_color + 1;
}
//end Greedy

最佳答案

您的颜色和顶点很小吗？

将对编码为单个数字，然后进行排序和解码

//G->colour = [2,1,0,1,0,1,0,1,2];
//G->vertex = [1,2,3,4,5,6,7,8,9];

colour * 1000 + vertex // based on small values!!

// encode to
// [2001, 1002, 3, 1004, 5, 1006, 7, 1008, 2009]
// sort to
// [2001, 2009, 3, 5, 7, 1002, 1004, 1006, 1008]
// decode to
//G->colour = [2,2,0,0,0,1,1,1,1];
//G->vertex = [1,9,3,5,7,2,4,6,8];

关于c - 如何对一个数组进行排序，该数组取决于其他数组的数量？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/55796116/