无法理解此图形表示（需要算法！）

Question

我一直在努力理解这个图表演示文稿，但没有任何适当的解决方案。也许有人能想出办法。

我有一个连接的，无周期的图形的演示，其形式如下：

< li >逐个删除度数为1(只有一条边)的顶点 < li >如果有多个选项，将移除具有最低值的顶点 < li >当顶点被删除时，它旁边的顶点将被标记 < li >这将继续下去，直到图形只剩下一个顶点

这是一个示例图：

    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

可以使用下面的技术将“表示”(在您的示例中为1 1 4 5)转换回图表(从您上面的评论来看，我认为这是您正在努力解决的问题)。然后，您可以轻松地生成一个邻接矩阵/列表。

该技术依赖于图中的节点被标记为1 - N(其中图中有N个节点)的关键假设。如果不是这样，基本上不可能重建原始图，因为您永远无法确定第一个被删除的节点的身份。

>

请注意，演示文稿中有 4 个项目。因此，图中有 5 个节点。

从演示文稿结束时向后工作。

删除最后一个节点时，剩余的节点为 5。因此，该图看起来像...

5-

删除前一项时，标记为4。因此，原始问号实际上必须是节点4，我们有一个新的未知节点。

5-4 - ?

删除上一项时，标记了 1。因此，？必须是 1 并且存在新的未知节点。

5 - 4 - 1 - ？一个

最后，当前一项被删除时，1被标记。我们已经有一个节点1，所以我们必须附加到它。

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

我们已经完成了对输入的解析。现在我们只需要标记未完成的？s。我们知道这些值为 2 和 3，因为上面所述的假设是节点标记为 1 - N，并且我们已经有 1， 2

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

...这很好，因为这和我们开始的地方一样。

由此你可以迭代节点并生成邻接矩阵。或者，so可以生成一个邻接表/矩阵(这可能更有效，但会使实现稍微有些混乱)。

正如David在上面指出的，这与Prüfer序列非常相似（但不完全相同），当剩下2个节点（而不仅仅是1个）时，该序列停止。链接文章给出了一种有效的伪码算法，可以通过跳过最后一步（将最后两个节点链接在一起）进行调整。

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

Answer 3

啊！由于原问题中的信息不足（尤其是info： tree将有1到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;
}