C中的圖着色無法識別邏輯錯誤

我想在C中實現圖着色算法，該實現基於如何通過迭代遍歷鄰接矩陣來分配顏色。將顏色分配給第二個頂點後，我無法得到它。C中的圖着色無法識別邏輯錯誤

這是我的程序的代碼：

int n, a[10][10], i, j, k, c[10], max = 0, col, ct = 0, rt = 0, m, count = 2; 
void main() { 
    printf("enter n\n"); 
    scanf("%d", &n); 
    printf("enter the Adjacency Matrix for %d rows and %d columns\n", n, n); 
    for (i = 0; i < n; i++) { 
     c[i] = 0; 
     for (j = 0; j < n; j++) 
      scanf("%d", &a[i][j]); 
    } 
    c[0] = 1; 
    c[1] = 2; 
    for (i = 1; i < n; i++) { 
     for (j = 0; j < n; j++) 
      if (a[i][j] > 0) { 
       m = 0; 
       for (col = 0; col < n; col++) { 
        if (a[i][col] > 0) 
         rt++; 
        if (a[col][i] > 0) 
         ct++; 
       } 
       m = rt; 
       if (ct > rt) 
        m = ct; 
       if (m < 2) { 
        if (a[0][i] > 0) 
         c[i] = 2; 
        else 
         c[i] = 1; 
       } else { 
        c[i] = count; 
        if (m > max) { 
         max = m; 
         count++; 
        } 
       }  
       rt = 0; 
       ct = 0; 
      } 
     if (c[i] < 1) 
      if (c[i - 1] > 1) 
       c[i] = 1; 
      else 
       c[i] = 2; 
    } 
    printf("The proper coloring is\n"); 
    for (i = 0; i < n; i++) 
     printf("c%d=%d ", i + 1, c[i]); 
    printf("\n"); 
}

示例輸入：考慮一個完整的圖：

預期輸出：

c1=1 c2=2 c3=3 c4=4

觀測輸出：

c1=1 c2=2 c3=3 c4=3

來源

2016-03-04 Prithvi

我重新格式化了您的代碼，您可以驗證邏輯是否正確？ – chqrlie

不完全。我仍然得到一個不正確的輸出其他圖。 – Prithvi

我沒有改變邏輯，只是使它更具可讀性。您是否可以重新閱讀代碼並驗證您的算法是否已正確實施？每個人都難以遵循縮進代碼，包括任何人編寫代碼。 – chqrlie

錯誤似乎是在邏輯上，因爲你可能已經推斷問題標題的外觀。您檢查m是否大於max，然後更新max和count的條件語句似乎不正確。

我無法準確理解預期的邏輯是什麼，但我可以告訴它爲什麼不正確。

在您的使用中，您保持max中遇到的鄰居的最大數量，並在找到具有更多鄰居的頂點時更新它。有了它，你也更新了計數，我認爲它保持了目前的最高價值。現在，除非在每一步中遇到更多鄰居的頂點（遍歷每一行時），否則不會更新最大值，因此不會更新計數。因此，除非遇到這樣的頂點，否則您一直將同樣的當前最高的計數分配給您遇到的所有頂點。

你應該更多地解釋你實現的算法。然而，僅僅通過查看你的代碼，我認爲你至少應該在不同的地方增加計數。

一個好主意可能只是保持一個數組等於頂點數。然後對於每個頂點（在最外層的循環中），您可以重置該數組，並遍歷頂點的所有鄰居，您可以設置它們中使用的顏色，並選取最小的未使用顏色。

這可能不是最有效的方法，但你已經有了一個O算法，所以我認爲這樣做不會受到傷害。

以下是您的代碼，已更新以反映我提到的更改。

int n,a[10][10],i,j,k,c[10],max=0,col,ct=0,rt=0,m,count=2; 
int used[11]; /* indices used are from 1 to n, inclusive */ 
void main() 
{ 
    printf("enter n\n"); 
    scanf("%d",&n); 
    printf("enter the Adjacency Matrix for %d rows and %d columns\n",n,n); 
    for(i=0; i < n ; i++) 
    { 
     c[i]=0; 
     for(j=0;j<n;j++) 
      scanf("%d",&a[i][j]); 
    } 
    c[0]=1; 
    c[1]=2; 
    for(i = 1 ;i < n;i++) 
    { 
     for(j = 1 ;j <= n ;j++) 
      used[j] = 0; 
     for(j = 0 ;j < i ;j++) 
     { 
      if(a[i][j] > 0) 
       used[c[j]] = 1; 
     } 
     for(j = 1 ;j <= n ;j++) 
      if(!used[j]) 
      { 
       c[i] = j; 
       break; 
      } 
    } 
    printf("The proper coloring is\n"); 
    for(i = 0;i < n ;i++) 
      printf("c%d=%d ",i+1,c[i]); 
     printf("\n"); 
}

來源

2016-03-04 07:01:27 ilim

你可以通過'j'來縮短第二個循環，擺脫測試'c [j]> 0）'：所有到'i'的頂點都已經被着色，其他所有頂點都沒有着色。 –

我最初做到了這一點，但我不想解釋這些細節，並想專注於邏輯本身。但是，謝謝，現在你已經解釋了它，我更新了代碼以反映這一點。 – ilim

什麼是一種簡單的算法來爲verice顏色看起來像？

考慮循環中的所有頂點並分配一種顏色。已經訪問過的頂點已經有一個顏色;仍然會被訪問的頂點仍然無色。
確定哪些顏色被已被着色的相鄰頂點使用。
有了這些信息，請選擇儘可能最低的顏色。

什麼是你的算法是這樣的：

指定顏色1至頂點1和顏色2到頂點2（注意，頂點2可以使用相同的顏色作爲頂點1如果兩個麥凱納t連接）
循環遍歷所有剩餘的頂點;然後循環遍歷所有頂點。
計算在另一個循環中到第二個頂點的傳入和傳出鏈接的數量。（請注意，僅計算鏈接並不能提供關於哪些顏色仍然可用的信息，例如，可以使用顏色3和4對許多頂點着色，但是您將新顏色基於鏈接數量。，顏色1將是一個不錯的選擇。）
選擇新顏色的標準是鏈接的數量是大於還是等於2.然後分配count，但在增加之前。這給你在你的例子中的第二個3，在那裏應該是4.

所以你循環一次太多，並有一個糟糕的標準選擇一種顏色。您應該在相鄰節點中保留使用的顏色列表，並將新顏色基於該列表，而不是計算孤立點。

其他文體的問題與您的代碼：

所有的變量應該是本地的main;沒有理由讓它們成爲全局的，特別是因爲你不使用函數。
請對你的變量聲明更系統。爲了讓他們全部掌握在一個大的定義中，甚至會破壞數組和標量，使他們難以理解。
請在所有代碼塊周圍使用大括號，即使它們不是絕對必要的。它使閱讀代碼更容易。在if (ct > rt) m = ct;這樣的內部塊中沒有else的小if不需要花括號，但可以考慮在其他地方使用它們。

來源

2016-03-04 07:07:11

C中的圖着色無法識別邏輯錯誤

回答

相關問題