Oggetto e puntatore grafico rappresentazioni

Question

io continuo a vedere in tutto il mondo che ci sono 3 modi per rappresentare i grafici:

1. oggetti e puntatori
2. matrice di adiacenza
3. liste di adiacenza

Tuttavia, ho appena non capisco cosa siano queste rappresentazioni Object e pointer - eppure ogni recruiter, e molti blog citano il blog Steve Yegge's che sono in effetti una rappresentazione separata.

This widely accepted answer a una domanda molto simile sembra suggerire che le strutture dei vertici stesse non hanno puntatori interni ad altri vertici, e invece tutti i bordi sono rappresentati da strutture di bordo che contengono puntatori ai vertici adiacenti.

In che modo questa rappresentazione offre vantaggi analitici visibili in qualsiasi scenario?

Answer 1

Dall'alto della mia testa, spero di avere i fatti corretti.

Concettualmente, il grafico tenta di rappresentare come un insieme di nodi (o vertici) sono correlati (connessi) tra loro (tramite i bordi). Tuttavia, nel dispositivo fisico reale (memoria), abbiamo una matrice continua di celle di memoria.

Quindi, per rappresentare il grafico, possiamo scegliere di utilizzare una matrice. In questo caso, usiamo l'indice del vertice come riga e colonna e la voce ha valore 1 se i vertici sono adiacenti l'uno all'altro, 0 altrimenti.

In alternativa, è anche possibile rappresentare un grafico allocando un oggetto per rappresentare il nodo/vertice che punta a un elenco di tutti i nodi ad esso adiacenti.

La rappresentazione a matrice offre il vantaggio quando il grafico è denso, ovvero quando la maggior parte dei nodi/vertici sono collegati tra loro. Questo perché in questi casi, utilizzando la voce di matrice, ci salva dal dover allocare un puntatore aggiuntivo (che richiede una memoria di dimensione parola) per ogni connessione.

Per il grafico sparse, l'approccio elenco è migliore perché non è necessario tenere conto delle voci 0 quando non vi è alcuna connessione tra i vertici.

Spero che aiuti.

Answer 2

Per ora ho difficoltà a trovare un "algoritmo grafico" pro w.r.t tipico. Ma è certamente possibile rappresentare un grafico con oggetti e puntatori e una cosa molto naturale da fare se la pensi come una rappresentazione di qualcosa che hai appena disegnato su una lavagna.

Pensa a uno scenario in cui desideri combinare i nodi di un grafico in un determinato ordine. I nodi hanno payload che contengono dati di dominio, la struttura del grafico stessa non è un aspetto fondamentale del programma.

Certo, è possibile aggiornare gli elenchi/matrice per ogni operazione, ma data una struttura "oggetti e puntatori", è possibile effettuare l'unione localmente. Inoltre, se i nodi hanno payload, significa che liste/matrice conterranno id di nodo che identificano gli oggetti del nodo reale. Una combinazione significherebbe aggiornare la rappresentazione del grafico, seguire gli identificatori del nodo ed eseguire l'elaborazione effettiva. Potrebbe sembrare più intuitivo lavorare sugli oggetti del tuo nodo reale e semplicemente rimuovere i puntatori quando collassa un vicino (ed elimina quel nodo).

Inoltre, ci sono altri modi per rappresentare un grafico:

• Ad es altrettanto triple, come Turle fa
• O come sfalsati rappresentazione (offset per nodo in una matrice bordo), ad esempio this Boost data structure (disclaimer: non ho ancora testato il collegato implementazione me)
• ecc

Answer 3

Ecco un modo ho utilizzato per creare grafico con questo concetto:

#include <vector> 

class Node 
{ 
    public: 
     Node(); 
     void setLink(Node *n); // *n as argument to pass the address of the node 
     virtual ~Node(void); 
    private: 
     vector<Node*> m_links; 
}; 

E la funzione responsabile la creazione del collegamento tra i vertici è:

void Node::setLink(Node *n) 
{ 
    m_links.push_back(n); 
}