C語言中的Havel-Hakimi演算法

我正在嘗試用 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]);
        }
    }
}

uj5u.com熱心網友回復：

您有 2 個問題，存在 ifgraph[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 也不需要在第一次出現時停止

uj5u.com熱心網友回復：

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

關鍵是它通過推進指標并減小陣列的大小來從字面上洗掉陣列中的第一個元素。這樣，我們總是使用元素 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 图论

上一篇：從C中的HDF5檔案確定定長字串屬性的長度

下一篇：如何訪問作為引數傳遞的檔案內容？