Geek asks and answers

It’s impossible to figure out this graphic representation (an algorithm is needed!)

I am struggling to understand the meaning of this graphic representation without the right solution. Maybe someone can understand something.

I have a view of a connected, free chart cycle, which is formed as follows:

  • Delete vertices that have degree 1 (has only one edge) one at a time
  • If there is more than one parameter, the vertex with the smallest value will be deleted.
  • When a vertex is removed, the vertex closest to it will be marked
  • This will continue until the graph remains at only one vertex.

Here is a graph example:

    2   3
     \ /
  5   1
   \ /
    4

And here is how the presentation form is formed:

    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.

Thus, the presentation for this graph will be:

1 1 4 5

, ? F.E. 1 1 4 5 :

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

!

+5
4

! - ( : 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;
}
+1

"" (1 1 4 5 ) , (, , , , , ). /.

key, 1 - N ( N ). , , node.

  • , 4 . , 5 .
  • .

  • node , node 5. , ...

    5 - ?

  • , 4. node 4, node.

    5 - 4 - ?

  • , 1. ? 1 node.

    5 - 4 - 1 - ?A

  • , , 1 . node 1, .

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

  • . . , 2 3 - , 1 - N, 1, 2 5. ( ) . , A = 3 ? B = 2. ( , .) .

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

    ... , , .

. , , / (, , , ).

, ( ) Prüfer, , 2 ( 1). , , ( ).

+1

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

. http://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence, , , . , 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;
    }

In some cases, one vertex is inappropriate on the returned adjacency list. FE at 16, 1, 19, 9, 19, 18, 17, 10, 13, 13, 4, 19, 5, 19, 18, 4, 19, 19 vertex 3 must have edges up to 17, 19, 13, but in the mine, it has edges up to 16, 19, 13. Can someone detect a flaw?

0
source

More articles:


All Articles