无法理解这个图表展示（需要算法！）

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

问题是，我如何将此演示文稿转换为邻接矩阵或邻接表？例如，对于1 1 4 5，邻接表看起来像这样：

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

谢谢你！

- Kaltsoon

---

这对我来说看起来像是一棵树 o_O - Despicable

我认为你已经有了一个算法（这就是你的文本描述实际上是什么）。你需要一种实现方式。这确实需要一些工作，但你已经拥有了所需的所有东西 - 除了编程语言和实现的开始。你必须先完成这个，然后再回来。 - towi

问题不在于如何将图形转换为此演示文稿，而在于如何将其转换回图形。我认为这个描述并不适合我的算法。如果您有解决方案，能否稍微启发一下我？ - Kaltsoon

普鲁弗序列 - David Eisenstat

Answer 1

"presentation"（在您的示例中为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. 我们完成了解析输入。现在我们只需要为未知节点打标签。根据上述假设，节点标记为1-N，我们已经有1、2和5。由于最低值节点首先被删除（将图形转换为演示文稿时），它们在将演示文稿转换为图形时最后添加。因此，?A = 3，?B = 2。（在这种情况下无关紧要，但在一般情况下是有关的。）那么最终的图形如下所示。

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

   ...这很好，因为这与我们开始的位置相同。

通过这种方式，您可以遍历节点并生成邻接矩阵。或者，您也可以在进行操作时一边生成邻接表/矩阵（这样可能更有效率，但会稍微使实现变得复杂）。

正如David在上面指出的那样，这与Prüfer序列非常相似（但不完全相同），它在只剩下2个节点时停止（而不是只剩下1个）。链接的文章给出了一个高效的伪代码算法，可以通过跳过最后一步（将最后两个节点连接在一起）来进行适应。

- Andrew Rose

Answer 2

这是Python中的一个朴素实现：

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]})

- Marcin Pietraszek

Answer 3

啊！由于原问题中信息不足（尤其是信息：树将有 1 到 n+1 个节点，其中 n 是输入数组的长度），我试图用更困难的方式解决它！无论如何，这是我的Prufer树生成实现，也许它会有所帮助 :-? :

#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;
}

- sowrov

---

这似乎可行。只需要将它转换成Java，但我想我能应付得了。非常感谢！ - Kaltsoon

Answer 4

我想出了这个算法。它很像http://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence，但就像Andrew说的那样，我省略了最后一部分。哈希映射用于邻接表，数组列表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;
    }

在某些情况下，邻接表中的一个顶点被放错了位置。例如，在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的边。有人能发现问题吗？

- Kaltsoon