Can't figure out this graph presentation (Algorithm needed!)

Question

I've been struggling a lot to make sense out of this graph presentation without any proper solution. Maybe someone could figure something out.

I have a presentation of connected, cycle free graph that forms as follows:

• Remove vertices which has a degree of 1 (has only one edge) one by one
• If there is more than one option, vertex with the lowest value will be removed
• When vertex is removed, the vertex next to it will me marked
• This will go on until graph has only one vertex left

Heres an example graph:

    2   3
     \ /
  5   1
   \ /
    4

And this is how the presentation forms:

    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.

So the presentation for this graph would be:

1 1 4 5

The problem is, how can I turn this presentation into adjacency matrix or adjacency list? F.e. with 1 1 4 5, the adjacency list would look like this:

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

Thank you!

Answer 1

Ah! because of the insufficient info in the original question (especially the info: tree will have 1 to n+1 nodes, where n is the length of input array), I tried to solve it in much harder way! Anyway, here is my Prufer-tree generation implementation, maybe it will help :-? :

#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

Here is the naive implementation in 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

And output:

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