使用度數序列創建圖形

Question

這是我的數據結構課程的第一個任務的一部分，所以如果你只是告訴我我錯在哪裏而不是發佈工作代碼，我會很高興。

我們應該編寫一個給定度數序列的程序，繪製一張圖。我爲圖形寫了數據結構，它可以正確地連接兩個頂點（graph.addConnection）。但是我無法找到一種方法來根據學位順序構建圖表。

This Wikipedia page給出了一個簡單的算法：

1. 開始與沒有條邊的圖。
2. 保持尚未達到殘差等級要求不升序的程度要求的頂點列表。
3. 將第一個頂點連接到此列表中的下一個d1頂點，然後將它從列表中移除。重新整理列表並重復，直到滿足所有 度要求。

我實現了它在Java中是這樣的：

public static void populate(Graph graph, int[] degrees) { 
    class DegreeMapping { 
     int vertice=0; 
     int degree=0; 
    } 

    ArrayList<DegreeMapping> degrees_ = new ArrayList<DegreeMapping>(degrees.length); 
    for(int i=0; i<degrees.length; i++) { 
     degrees_.add(new DegreeMapping()); 
     degrees_.get(i).vertice = i; 
     degrees_.get(i).degree = degrees[i]; 
    } 

    while(! degrees_.isEmpty()) { 
     // Sort by degrees 
     Collections.sort(degrees_, new Comparator<DegreeMapping>() { 
           @Override 
           public int compare(DegreeMapping o1, DegreeMapping o2) { 
            return o2.degree - o1.degree ; 
           } 
          }); 
     for(DegreeMapping i: degrees_) System.out.printf("{%d, #%d} ", i.degree, i.vertice); 
     System.out.println(); 

     for(int i=1; i<degrees_.get(0).degree+1; i++) { 
      degrees_.get(i).degree--; 
      graph.addConnection(degrees_.get(0).vertice, degrees_.get(i).vertice); 
      System.out.printf("#%d <-> #%d \n", degrees_.get(0).vertice, degrees_.get(i).vertice); 
     } 

     degrees_.remove(0); 
    } 
} 

它給出了這樣的輸出爲度序列2 2 2 2 2 2 2 2：

{2, #0} {2, #1} {2, #2} {2, #3} {2, #4} {2, #5} {2, #6} {2, #7} 
#0 <-> #1 
#0 <-> #2 
{2, #3} {2, #4} {2, #5} {2, #6} {2, #7} {1, #1} {1, #2} 
#3 <-> #4 
#3 <-> #5 
{2, #6} {2, #7} {1, #4} {1, #5} {1, #1} {1, #2} 
#6 <-> #7 
#6 <-> #4 
{1, #7} {1, #5} {1, #1} {1, #2} {0, #4} 
#7 <-> #5 
{1, #1} {1, #2} {0, #5} {0, #4} 
#1 <-> #2 
{0, #2} {0, #5} {0, #4} 
{0, #5} {0, #4} 
{0, #4} 

正如你所看到的，它創造了兩個截然不同的具有頂點{0,1,2}和{3,4,5,6,7}的組，它們之間沒有任何連接。但它應該只創建一個圖。

我在做什麼錯？

Answer 1

根據維基百科，該算法產生一個簡單的圖，該圖也是根據維基百科的說法是'一個無向圖，沒有任何循環且在任何兩個不同頂點之間不超過一條邊「。

你得到的是一個包含兩個不同連通組件的圖，而不是兩個圖，所以算法似乎工作正常。

如果您的任務沒有明確說明該圖應該連接，您不應該擔心它。

Answer 2

如果您還對頂點數進行排序，它似乎更好。

// Sort by degrees and then vertex number 
Collections.sort(degrees_, new Comparator<DegreeMapping>() { 
    @Override 
    public int compare(DegreeMapping o1, DegreeMapping o2) { 
     if (o1.degree == o2.degree) return o2.vertice - o1.vertice; 
     return o2.degree - o1.degree; 
    } 
}); 

結果：

{2, #0}, {2, #1}, {2, #2}, {2, #3}, {2, #4}, {2, #5}, {2, #6}, {2, #7} 
#0 <-> #1 
#0 <-> #2 
{2, #3}, {2, #4}, {2, #5}, {2, #6}, {2, #7}, {1, #1}, {1, #2} 
#3 <-> #4 
#3 <-> #5 
{2, #6}, {2, #7}, {1, #1}, {1, #2}, {1, #4}, {1, #5} 
#6 <-> #7 
#6 <-> #1 
{1, #2}, {1, #4}, {1, #5}, {1, #7}, {0, #1} 
#2 <-> #4 
{1, #5}, {1, #7}, {0, #1}, {0, #4} 
#5 <-> #7 
{0, #7}, {0, #1}, {0, #4} 
{0, #1}, {0, #4} 
{0, #4} 

---

據米哈伊爾和Vishnoi紙張"On Generating Graphs with Prescribed Degree Sequences for Complex Network Modeling Applications"，可以通過之後修改所述算法的結果創建的連通圖。

如果該圖表未被連接，則其中一個連接的組件必須包含一個循環。讓（ü，v）是在一個週期內的任何邊緣，並讓（小號，噸）是在一個不同的連接的組件的邊緣。顯然，該圖不具有邊緣之間的邊緣,的和v,t。通過消除邊緣（ü，v）和（小號，噸），並插入邊緣（ü，小號）和（v，噸），我們合併這兩個組件。請注意，結果圖仍然滿足給定的度數序列。以這種方式進行，我們可以得到一個連接的拓撲結構。