無法找出這個圖表演示（算法需要！）

Question

我一直在掙扎了很多，沒有任何適當的解決方案，使這個圖表演示很有意義。也許有人可以想出一些東西。

我具有形成如下連接，自由循環圖的呈現：

• 刪除其具有一定程度的1個頂點（僅具有一個邊緣）逐個
• 如果存在多於一個選項，頂點與最低值將被刪除
• 當頂點被刪除，頂點旁邊將我標誌着
• 直到圖只有一個頂點這將繼續留

這裏有一個例子圖：

2 3 
    \/
    5 1 
    \/
    4 

這是怎樣的表現形式：

2 3   3 
    \/  /
    5 1 => 5 1 => 5 1 => 5 => 5 
    \/  \/  \/  \ 
    4   4   4   4 


1. Remove vertex two and mark one. 

2. Remove vertex three and mark one. 

3. Remove vertex one and mark four. 

4. Remove vertex four and mark five. 

因此，對於該圖演示將是：

1 1 4 5 

的問題是，我怎樣才能把這個演示文稿轉換成鄰接矩陣或鄰接表？ F.e. 1 1 4 5，鄰接表是這樣的：

1: 2 3 4 
2: 1 
3: 1 
4: 1 5 
5: 4 

謝謝！

Answer 1

啊！由於原始問題信息不足（特別是info：tree將有1 to n+1節點，其中n是輸入數組的長度），所以我試圖以更困難的方式解決它！無論如何，這是我的Prufer-tree生成實現，也許它會幫助： - ？ ：

#include <stdio.h> 
#include <vector> 
#include <memory.h> 
using namespace std; 

struct Node { 
    int N; 
    vector<int>list; 
    Node() { 
     N=-1; 
     list.clear(); 
    } 
}; 

vector<Node> convertPruferToTree(vector<int>& input) { 
    int n = input.size()+1; 
    vector<Node> T; 
    int *degree = new int[n+1]; 
    for (int i=1; i<=n; i++) { 
     Node tmp; 
     tmp.N = i; 
     T.push_back(tmp); 
     degree[i]=1; 
    } 
    //printf("n: %d\n", n); 
    for (int i=0; i<input.size()-1; i++) { 
     degree[input[i]]++; 
    } 

    for (int i=0; i<input.size()-1; i++) { 
     for (int j=1; j<=n; j++) { 
      if (degree[j]==1) { 
       T[j-1].list.push_back(input[i]); 
       T[input[i]-1].list.push_back(j); 
       degree[input[i]]--; 
       degree[j]--; 
       break; 
      } 
     } 
    } 
    int u=0, v=0; 

    for (int i=1; i<=n; i++) { 
     if (degree[i]==1) { 
      if (u==0) u=i; 
      else { 
       v = i; 
       break; 
      } 
     } 
    } 
    //printf("u: %d v: %d\n", u, v); 
    T[u-1].list.push_back(v); 
    T[v-1].list.push_back(u); 
    delete []degree; 
    return T; 
} 

int main() { 
    vector <int> input; 
    int n,v; 
    scanf("%d", &n); 
    while(n--) { 
     scanf("%d", &v); 
     input.push_back(v); 
    } 
    vector<Node> adjList = convertPruferToTree(input); 
    Node tmp; 
    for (int i=0; i<adjList.size(); i++) { 
     tmp = adjList[i]; 
     printf("%2d: ", tmp.N); 
     for (int j=0; j<tmp.list.size(); j++) { 
      printf("%2d ", tmp.list[j]); 
     } 
     printf("\n"); 
    } 
    return 0; 
} 

Answer 2

的「演講」（在你的例子1 1 4 5）可以變回使用以下方法（其中，從上面您的評論，是位我想你掙扎）的圖表。然後你可以簡單地生成一個鄰接矩陣/列表。

該技術依賴於關鍵假設，該圖中的節點被標記爲1-N（其中圖中有N個節點）。如果情況並非如此，則根本不可能重建原始圖形，因爲您永遠無法確定首先移除的節點的身份。

1. 注意，有演示文稿中的4項。因此，圖中有5個節點。
2. 從演示結束工作倒退。

3. 當除去最後一個節點，所剩下的節點是5。因此，圖形看起來像......

   5 - ?

4. 在拆卸前一個項目，4個被標記。因此，原始問號實際上必須是節點4，並且我們有一個新的未知節點。

   5 - 4 - ?

5. 當除去前一個項目，1被標記。因此，必須是1，並且有一個新的未知節點。

   5 - 4 - 1 - ?A

6. 最後，除去以前的項目時，1被標記。我們已經有了一個節點1，所以我們必須重視這一點。

   5 - 4 - 1 +- ?A 
         | 
         += ?B 
   

7. 我們已經完成了解析輸入。現在我們只需要標註出色的？我們知道值爲2和3，因爲上面假設節點被標記爲1-N，並且我們已經擁有1,2個節點。因爲最低值節點首先被移除（當將圖形轉換爲演示文稿時），將演示文稿轉換爲圖形時最後添加它們。那麼？A = 3和？B = 2（在這種情況下，它並不重要，但在一般情況下它是這樣的。）最終的圖形如下。

   5 - 4 - 1 +- 3 
         | 
         += 2 
   

   ...這是很好的，因爲這是我們開始的地方。

從這裏就可以遍歷節點和產生你的鄰接矩陣。或者，你也可以隨時產生鄰接表/矩陣（這可能更有效，但稍微混淆了實現）。

正如David在上面指出的，這與Prüfer sequence非常相似（但不完全相同），當有2個節點（而不是1個）時，它會停止。鏈接的文章給出了一個有效的僞代碼算法，可以通過跳過最後一步（將最後兩個節點鏈接在一起）進行修改。

Answer 3

這裏是蟒蛇天真實現：

from collections import defaultdict 

prufer_sequence = [1, 1, 4, 5] 
all_vertices = range(1, len(prufer_sequence) + 2) 

adjacency = defaultdict(list) 
for vertex in prufer_sequence: 
    searched_vertex = filter(lambda v: v != vertex, all_vertices)[0] 
    all_vertices.remove(searched_vertex) 
    adjacency[vertex].append(searched_vertex) 
    adjacency[searched_vertex].append(vertex) 

print adjacency 

輸出：

defaultdict(<type 'list'>, {1: [2, 3, 4], 2: [1], 3: [1], 4: [1, 5], 5: [4]}) 

Answer 4

我想出了這個算法。這很像這個http://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence，但像安德魯說，我離開了最後一部分。 hashmap用於鄰接列表，arraylist k用於表示。

public static HashMap<Integer, HashSet<Integer>> toGraph(ArrayList<Integer> k) { 
     HashMap<Integer, HashSet<Integer>> hm = new HashMap<Integer, HashSet<Integer>>(); 
     for(int i=1; i<=k.size()+1; i++){ 
      hm.put(i, new HashSet<Integer>()); 
     } 
     int degree[] = new int[k.size()+1]; 
     for(int i=0; i<degree.length; i++){ 
      degree[i]=1; 
     } 
     for(int a : k){ 
      degree[a-1]++; 
     } 
     for(int n : k){ 
      for(int j : hm.keySet()){ 
       if(degree[j-1]==1){ 
        hm.get(j).add(n); 
        hm.get(n).add(j); 
        degree[n-1]--; 
        degree[j-1]--; 
        break; 
       } 
      } 
     } 
     return hm; 
    } 

在某些情況下，返回的鄰接表中有一個頂點錯位。 F.E.在16,1,19,9,19,18,17,10,13,13,4,19,5,19,18,4,19,19頂點3應該具有邊緣17,19,13，但是在我的它有邊緣到16,19,13。有人可以發現一個缺陷？