C中的Havel-Hakimi算法

Question

我正在尝试用 C 编写 havel-hakimi 定理。但是我在 while 循环方面遇到了问题。该程序不会在 while 循环中再次对数组进行排序，这就是输出打印错误答案的原因。可以告诉我我的错是什么吗？

# include <stdio.h>
int main(){
    int j,i,vertex_number,temp1,temp2,a=0,b=0;
    printf("Vertex Number:");
    scanf("%d",&vertex_number);
    int graph[vertex_number];
    for(i=0;i<vertex_number;i++){
        scanf("%d",&graph[i]);
    }
    while(1){
        //SORTING ARRAY
        for(i=0;i<vertex_number;i++){
            for(j=i+1;j<vertex_number;j++){
                if(graph[i]<graph[j]){
                    temp1=graph[i];
                    graph[i]=graph[j];
                    graph[j]=temp1;
                }
            }
        }
        //IF ALL VERTEX DEGREES EQUAL 0 GRAPH EXIST
        for(i=0;i<vertex_number;i++){
            if(graph[i]==0){
                a++;
            }
        }
        if(a==vertex_number){
            printf(" graph exist.");
            return 0;
        }
        //NEGATIVE VERTEX DEGREE NOT EXIST
        for(i=0;i<vertex_number;i++){
            if(graph[i]<0){
                b++;
            }
        }
        if(b>0){
            printf("graph not exist.");
            return 0;
        }
        temp2=graph[0];
        for(i=0;i<temp2;i++){
            graph[i]=graph[i+1];
        }
        vertex_number--;
        for(i=0;i<temp2;i++){
            graph[i]-=1;
        }
        printf("-------------\n");
        for(i=0;i<vertex_number;i++){
            printf("%d\n",graph[i]);
        }
    }
}

Answer 1

您有 2 个问题，如果 graph[i]-=1; 为负则存在，并且应该针对 vertex_number 而不是 temp2

执行删除循环

# include <stdio.h>
int main(void) {
    int i, j, vertex_number, temp1, temp2;

    printf("Vertex Number:");
    scanf("%d", &vertex_number);
    int graph[vertex_number];
    for (i = 0; i < vertex_number; i++){
        scanf("%d", &graph[i]);
    }
    while (1) {
        //SORTING ARRAY
        for (i = 0; i < vertex_number; i++) {
            for (j = i+1; j < vertex_number; j++) {
                if (graph[i] < graph[j]) {
                    temp1 = graph[i];
                    graph[i] = graph[j];
                    graph[j] = temp1;
                }
            }
        }
        //IF ALL VERTEX DEGREES EQUAL 0 GRAPH EXIST
        if (graph[0] == 0) {
            printf(" graph exist.");
            return 0;
        }
        //NEGATIVE VERTEX DEGREE NOT EXIST
        for (i = 0; i < vertex_number; i++) {
            if (graph[i] < 0){
                printf("graph not exist.");
                return 0;
            }
        }
        temp2 = graph[0];
        vertex_number--;
        for (i = 0; i < vertex_number; i++) { // HERE was your issue
            graph[i] = graph[i + 1];
        }
        for (i = 0; i < temp2; i++) {
            graph[i]-=1;
            if (graph[i] < 0) {
                printf("graph not exist.");
                return 0;
            }
        }
        printf("-------------\n");
        for (i = 0; i < vertex_number; i++) {
            printf("%d\n",graph[i]);
        }
    }
}

你不需要一个，如果第一个为空，其他都为空或负数

你不需要 b 也不需要在第一次出现时停止

Answer 2

不是答案，而是一个有效的清理版本。

关键是它通过推进指针和减小数组的大小从字面上删除数组中的第一个元素。这样，我们始终使用元素 0..s-1 或 0..n-1.

// Destroys the contents of the provided array.
int havel_hakimi(unsigned *degrees, size_t n) {
   while (1) {
      // Yuck
      for (size_t i=0; i<n; ++i) {
        for (size_t j=i+1; j<n; ++j) {
            if (degrees[i] < degrees[j]) {
                int temp = degrees[i];
                degrees[i] = degrees[j];
                degrees[j] = temp;
            }
         }
      }

      if (degrees[0] == 0)
         return 1;  // Has a simple graph.

      // Remove first element.
      unsigned s = degrees[0];
      ++degrees;
      --n;

      if (s > n)
         return 0;  // Invalid input!

      if (degrees[s-1] == 0)
         return 0;  // Doesn't have a simple graph.

      for (size_t i=s; i--; )
         --degrees[i];
   }
}

使用以下方法测试：

#include <stdio.h>

int main(void) {
   {
      unsigned degrees[] = { 6, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1 };
      printf("%d\n", havel_hakimi(degrees, sizeof(degrees)/sizeof(degrees[0])));  // 1
   }

   {
      unsigned degrees[] = { 6, 5, 5, 4, 3, 2, 1 };
      printf("%d\n", havel_hakimi(degrees, sizeof(degrees)/sizeof(degrees[0])));  // 0
   }

   return 0;
}

C中的Havel-Hakimi算法

Havel-Hakimi Algorithm in C

c

graph-theory