Nie mogę wykreślić tej prezentacji wykresu (potrzebny algorytm!)

Question

Bardzo często zmagałem się z sensem tej prezentacji wykresu bez odpowiedniego rozwiązania. Może ktoś coś wymyśli.

mam przedstawienie połączonego, cykl wolne wykresie, który tworzy się, gdy następuje:

• usunąć wierzchołki która ma stopień 1 (ma tylko jedną krawędź) pojedynczo
• Jeśli istnieje więcej niż jedna opcja, wierzchołek o najmniejszej wartości zostaną usunięte
• Kiedy wierzchołek jest usuwany, wierzchołek obok niego będzie mi oznaczony
• będzie to trwać aż wykres ma tylko jeden wierzchołek lewy

Herezje przykład wykres:

2 3 
    \/
    5 1 
    \/
    4 

A to, w jaki sposób formy prezentacji:

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. 

Więc prezentacja na tym wykresie byłoby:

1 1 4 5 

Problemem jest to, , jak mogę przekształcić tę prezentację w macierz sąsiedztwa lub listę sąsiedztwa? F.e. z 1 1 4 5, lista sąsiedztwa będzie wyglądać następująco:

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

Dziękujemy!

Answer 1

Ah! ze względu na niewystarczające informacje w pierwotnym pytaniu (zwłaszcza informacje: drzewo będzie miało węzły 1 to n+1, gdzie n jest długością tablicy wejściowej), starałem się rozwiązać go w znacznie trudniejszy sposób! Tak czy inaczej, oto moja implementacja generowania Prufer-tree, może to pomoże: -? :

#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

"Prezentacja" (1 1 4 5 w twoim przykładzie) można zawrócić do wykresu za pomocą poniższej techniki (która, z twojego komentarza powyżej, jest tym, o czym myślę, że walczysz). Możesz wtedy trywialnie utworzyć matrycę/listę sąsiedztwa. Ta technika polega na kluczowym założeniu , że węzły na wykresie zostały oznaczone jako 1 - N (gdzie na wykresie jest N węzłów). Jeśli tak nie jest, zasadniczo niemożliwe jest zrekonstruowanie oryginalnego wykresu, ponieważ nigdy nie można ustalić tożsamości pierwszego usuniętego węzła.

1. Uwaga: w prezentacji są 4 pozycje. Dlatego na wykresie jest 5 węzłów.
2. Odsyłamy od końca prezentacji.

3. Kiedy ostatni węzeł został usunięty, węzeł, który pozostał był 5. W związku z tym, wykres wygląda ...

   5 - ?

4. Kiedy poprzedni element został usunięty, 4 została oznaczona. Dlatego oryginalny znak zapytania musi w rzeczywistości być węzłem 4, a my mamy nowy nieznany węzeł.

   5 - 4 - ?

5. Kiedy poprzedni element został usunięty, 1 został oznaczony. Dlatego też ? musi wynosić 1 i pojawia się nowy nieznany węzeł.

   5 - 4 - 1 - ?A

6. Wreszcie, kiedy poprzedni element został usunięty, 1 został oznaczony. Mamy już węzeł 1, więc musimy dołączyć do tego.

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

7. Skończyliśmy parsować dane wejściowe. Teraz musimy tylko opisać wybitne? Wiemy, że wartości wynoszą 2 i 3, ponieważ założono powyżej, że węzły mają etykietę 1 - N i mamy już 1, 2 & 5. Ponieważ węzły najniższej wartości są usuwane jako pierwsze (podczas przekształcania wykresu w prezentację), są one dodawane jako ostatnie podczas konwertowania prezentacji na wykres. A zatem: A = 3 i? B = 2. (W tym przypadku nie ma to znaczenia, ale w ogólnym przypadku tak się dzieje.) Pozostawia to ostatni wykres w następujący sposób.

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

   ... co jest dobre, ponieważ jest to to samo, co miejsce rozpoczęcia.

Z tego można wykonywać iteracje po węzłach i tworzyć macierz sąsiedztwa. Alternatywnie, można utworzyć listę/tabelę sąsiednich ścieżek (co może być bardziej wydajne, ale nieco myli implementację).

Jak zauważył David, jest to bardzo podobne (ale nie do końca identyczne) z Prüfer sequence, które zatrzymuje się, gdy pozostały 2 węzły (a nie tylko 1). Powiązany artykuł podaje skuteczny algorytm pseudokodowania, który można dostosować, pomijając ostatni krok (połączenie dwóch ostatnich węzłów).

Answer 3

Oto naiwna implementacja w Pythonie:

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 

i wyjście:

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

Answer 4

mam wymyślić tego algorytmu. To bardzo podobne do tego http://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence, ale jak powiedział Andrew, zostawiłem ostatnią część z tego. Histop jest dla listy przyległości, a lista do prezentacji k służy do prezentacji.

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

W niektórych przypadkach jeden wierzchołek jest nieprawidłowo umieszczony na zwróconej liście przyległości. F.e. w 16, 1, 19, 9, 19, 18, 17, 10, 13, 13, 4, 19, 5, 19, 18, 4, 19, 19 wierzchołek 3 powinien mieć krawędzie do 17, 19, 13, ale w moim ma krawędzie do 16, 19, 13. Czy ktoś może wykryć wadę?