无法弄清楚这个图表演示(算法需要!)

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

问题是,如何将此演示文稿转换为邻接矩阵或邻接列表？Fe与1 1 4 5,邻接列表如下所示:

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

谢谢!

Answer 1

啊! 由于原始问题中的信息不足（尤其是信息：树将有1 to n+1节点，n输入数组的长度在哪里），我尝试以更困难的方式解决它！不管怎样，这是我的普鲁弗树生成实现，也许它会有所帮助:-？:

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