Non riesco a capire questa presentazione del grafico (necessario Algoritmo!)

Question

Ho faticato molto per dare un senso a questa presentazione del grafico senza alcuna soluzione adeguata. Forse qualcuno potrebbe capire qualcosa.

ho una presentazione di collegato grafico, ciclo libero che si forma come segue:

• Rimuovere vertici che ha un grado di 1 (ha solo un bordo) uno per uno
• Se v'è più di un'opzione, il vertice con il valore più basso sarà rimosso
• Quando vertice viene rimosso, il vertice accanto ad esso sarà mi ha segnato
• Questo andrà avanti fino a quando grafico ha un solo vertice sinistro

Ecco un grafico di esempio:

2 3 
    \/
    5 1 
    \/
    4 

Ed è così che le forme di presentazione:

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. 

Così la presentazione per questo grafico potrebbe essere:

1 1 4 5 

Il problema è , come posso trasformare questa presentazione in matrice di adiacenza o lista di adiacenza? F.e. con 1 1 4 5, la lista di adiacenza sarebbe simile a questa:

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

Grazie!

Answer 1

Ah! a causa delle informazioni insufficienti nella domanda originale (in particolare le informazioni: l'albero avrà i nodi 1 to n+1, dove n è la lunghezza della matrice di input), ho provato a risolverlo in un modo molto più difficile! Comunque, ecco la mia implementazione della generazione di alberi Prufer, forse aiuterà: -? :

#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

La "presentazione" (1 1 4 5 nel tuo esempio) può essere trasformata in un grafico usando la seguente tecnica (che, dal tuo commento sopra, è il bit che penso tu stia combattendo). È quindi possibile produrre banalmente una matrice/lista di adiacenza.

Questa tecnica si basa sull'assunzione della chiave in cui i nodi del grafico erano etichettati 1 - N (dove ci sono N nodi nel grafico). Se questo non è il caso, è fondamentalmente impossibile ricostruire il grafico originale perché non si può mai determinare l'identità del primo nodo rimosso.

1. Si noti che ci sono 4 elementi nella presentazione. Pertanto, ci sono 5 nodi nel grafico.
2. Torna indietro alla fine della presentazione.

3. Quando l'ultimo nodo è stato rimosso, il nodo che è stato lasciato era 5. Pertanto, il grafico sembra ...

   5 - ?

4. Quando l'elemento precedente è stato rimosso, 4 è stato caratterizzato. Pertanto, il punto interrogativo originale deve essere effettivamente il nodo 4 e abbiamo un nuovo nodo sconosciuto.

   5 - 4 - ?

5. Quando l'elemento precedente è stato rimosso, 1 è stato contrassegnato. Quindi, il ? deve essere un 1 e c'è un nuovo nodo sconosciuto.

   5 - 4 - 1 - ?A

6. Infine, quando l'elemento precedente è stato rimosso, 1 è stato contrassegnato. Abbiamo già un nodo 1, quindi dobbiamo collegarci a questo.

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

7. Abbiamo finito di analizzare l'input. Ora abbiamo solo bisogno di etichettare gli eccezionali? Sappiamo che i valori sono 2 e 3 a causa dell'ipotesi sopra affermata che i nodi sono etichettati come 1 - N e abbiamo già 1, 2 & 5. Poiché i nodi con valore più basso vengono rimossi per primi (quando si trasforma il grafico nella presentazione), vengono aggiunti per ultimi quando si converte una presentazione in un grafico. Quindi? A = 3 e? B = 2. (In questo caso non importa, ma nel caso generale lo fa.) Questo lascia il grafico finale come segue.

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

   ... che è buono perché è lo stesso di dove abbiamo iniziato.

Da questo è possibile scorrere i nodi e produrre la matrice di adiacenza. In alternativa, così puoi produrre una lista/matrice di adiacenze mentre procedi (che è probabilmente più efficiente, ma confonde leggermente l'implementazione).

E come David ha sottolineato sopra, questo è molto simile (ma non del tutto identico) a uno Prüfer sequence che si arresta quando rimangono 2 nodi (anziché 1). L'articolo collegato fornisce un efficiente algoritmo di pseudo-codice che può essere adattato saltando il passaggio finale (collegando gli ultimi due nodi).

Answer 3

Ecco l'attuazione ingenuo 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 

E uscita:

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

Answer 4

mi è venuta in mente questo algoritmo. È molto simile a questo http://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence, ma come Andrew ha detto che ho lasciato l'ultima parte fuori. L'hashmap è per la lista di adiacenza e l'arraylist k è per la presentazione.

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 alcuni casi un vertice è posizionato in modo errato nell'elenco di adiacenza restituito. F.e. in 16, 1, 19, 9, 19, 18, 17, 10, 13, 13, 4, 19, 5, 19, 18, 4, 19, 19 il vertice 3 dovrebbe avere bordi a 17, 19, 13 ma nella mia ha bordi a 16, 19, 13. Qualcuno può individuare un difetto?