Mettere in discussione il modo in cui vengono insegnati i grafici

Question

Sono da Argentina, ma penso che tutti coloro che hanno mai prendere un Data strutture di classe sanno cosa sia un grafo è. Se lo fai, si potrebbe sapere che tipo di implementazioni sono "comuni" o "standar". Può essere implementato attraverso un elenco o una matrice. Anche Wikipedia dice questo. Così come Mark Allen Weiss, Bruno Preiss e Luis Aguilar Joyanes.

La cosa è. Nessuno mai ha pensare che questo non è un buon modo per farlo? Il modo più consigliato è attraverso una lista. Ma considerato che i vertici possono avere solo un bordo tra di loro, non credo che una lista è l'interfaccia buona per farlo. Cioè, se il Vertex V1 è collegata con Vertex V2, allora c'è solo uno e un solo bordo.

Non pensi che sarebbe un set al posto di una lista?

Class Vertex{
    private Set edges;
    private Object data;

    /** Methods**/
}

Voglio solo sapere alcune opinioni, cosa ne pensi?

Grazie !!

Modifica Inoltre, se pensiamo che il grafico non può avere elementi ripetuti, un HashSet sarebbe una buona scelta per minimizzare la ricerca del vertice nell'inserimento.

Answer 1

Hai ragione a sottolineare che le adiacenze per un vertice sono più accuratamente modellate da un insieme (o, nel caso di un multigrafo, un multiset). Allora perché strutture dati libri scrivono di array e liste collegate, invece? Mi vengono in mente tre motivi:

1. L'idea che i linguaggi di programmazione dovrebbero includere gruppi come tipo di dati primitivo è piuttosto recente. scrittori più anziani non avrebbero considerato utilizzarla e scrittori moderni tendono a seguire le tradizioni del campo.

2. Uno degli scopi di una strutture di dati è il corso per consentire di pensare alla rappresentazione dei dati a un livello basso (calcestruzzo), nonché a un livello elevato (abstract). Un set è un tipo di dato astratto che (a differenza di liste concatenate e array) non dispone di un'implementazione ovvia a basso livello: alcuni set sono meglio rappresentate come liste collegate, alcuni come tabelle hash, alcuni come gli array, e così via. Quindi è naturale per uno strutture di dati ovviamente per saltare la rappresentazione di alto livello di set per la loro attuazione a basso livello, che dovete sapere su ogni caso, al fine di analizzare il comportamento degli algoritmi che li utilizzano.

3. E 'importante non essere dogmatico su come rappresentare i tipi di dati, perché gli algoritmi possono essere espresse in modo più efficiente utilizzando le rappresentazioni particolari. Esempio 1. Per contare i percorsi di lunghezza n tra ogni coppia di vertici in un grafico, rappresentano il grafico sua matrice di adiacenza e sollevare la matrice alla potenza n . Se ti ostini a rappresentare le adiacenze di un vertice come un insieme di bordi, allora vi perderete questo algoritmo (che può essere parallelized utilizzando tecniche standard). Esempio 2. Knuth di " Danza Link " algoritmo per l'esatto problema della copertura rappresenta set di colonne utilizzando liste doppiamente collegate, in modo che i collegamenti da elementi eliminati possono essere riutilizzati per backtracking efficiente.

Answer 2

In un tempo relativamente maggiore C / C ++ programmatore di livello, come viene implementato un grafico / rete dipende moltissimo a quali operazioni vengono eseguite su di esso. Essendo una persona O me stesso, sto probabilmente prevenuto nella mia risposta / esempio qui. Alcuni degli algoritmi più efficienti che possono essere implementate su grafici / reti sono algoritmi polinomiali. La maggior parte, se non tutti, gli algoritmi polinomiale in tempo riesco a pensare (problema del cammino minimo, problema del trasporto, problema max-flow di Dijkstra, etc.) sono casi speciali di minimo costo-flow (MCF) problema. Computazionalmente, uno dei più soluzioni efficaci un problema MCF è tramite l'algoritmo rete simplex (che di per sé è una specializzazione dell'algoritmo simplex per risolvere un programma lineare generale).

Nella rete-simplex-algoritmo, un albero di copertura (oltre l'insieme dei nodi) ha bisogno di essere rappresentato in modo efficiente. Per rappresentare un albero di copertura in un grafico, una varietà di strutture di dati può essere utilizzato. Questi includono il seguente nodo lunghezza

predecessor[], thread[] and depth[] arrays.

In implementazioni più efficienti di network-simplex-algoritmi che ho incontrato, questi non sono rappresentate come array ma una sorta di blocco creata dinamicamente della memoria tramite

calloc(number_of_nodes, sizeof(struct vertex));

Sono incerto (in un tempo relativamente inferiore di livello) interna al compilatore cosa / come viene implementato questa allocazione della memoria -. Se si tratta di un elenco / set / carta

Così, in sintesi, il migliore modo per implementare un grafico è fortemente dipendente dalle operazioni da eseguire su di esso.

algoritmo di rete simplex e le strutture dati necessarie per attuare in modo efficace lo stesso può essere trovato in questo libro .

Answer 3

Nella sua forma più astratta, un set ha un predicato per verificare se un elemento è all'interno del set. Può anche supportare gli operatori che forniscono unione e intersezione. La differenza non è necessario calcolabile.

Nella sua forma più astratta, una lista I supporti iterazione, sub-lista, e aggiungere.

La maggior parte algoritmi su grafi richiedono per scorrere i bordi, in modo da una struttura che supporta l'iterazione è preferito. La maggior parte degli algoritmi di non tentare di aggiungere lo stesso bordo due volte, quindi la rimozione dei duplicati non è necessaria.

Naturalmente, la maggior parte dei set di librerie sono finiti, insiemi estensionale che supportano anche l'iterazione, in modo da li si potrebbe usare, anche se si sarebbe ancora avere il costo di controllare i duplicati.

Alcuni sistemi basati grafi fanno uso parti come il meccanismo sottostante, ma hanno a che fare con infinite grafici, piuttosto che quelli finiti, dove insiemi intensionali diventano utile.