Confrontando rappresentazione grafica oggetto lista di adiacenza e la matrice Rappresentazioni

Question

Attualmente sto seguendo il consiglio di Steve Yegge sulla preparazione per un colloquio di programmazione tecnica: http://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html

Nella sua sezione su grafici, afferma:

Ci sono tre modi fondamentali per rappresentare un grafico in memoria (oggetti e puntatori, matrice e adiacenza elenco), e si dovrebbe familiarizzare te stesso con ogni rappresentazione e suoi pro e contro.

I pro ei contro di matrice e lista di adiacenza rappresentazioni sono descritti in CLRS, ma non sono stati in grado di trovare una risorsa che mette a confronto questi per una rappresentazione dell'oggetto.

Solo a pensarci, posso dedurre un po 'di questo me stesso, ma mi piacerebbe essere sicuro di non aver perso qualcosa di importante. Se qualcuno potesse descriverlo in modo esauriente, o indicarmi una risorsa che lo fa, lo apprezzerei molto.

Answer 1

Gli oggetti e i puntatori sono in gran parte equivalenti all'elenco di adiacenze, almeno allo scopo di confrontare gli algoritmi che utilizzano queste rappresentazioni.

Confronta

struct Node { 
    Node *neighbours[]; 
}; 

con

struct Node { 
    Node *left; 
    Node *right; 
}; 

Si può facilmente costruire l'elenco dei vicini on-the-fly in quest'ultimo caso, se è più facile da lavorare rispetto puntatori nome.

Answer 2

oggetti e puntatori

Questi sono solo Datastructures di base come Hammar ha detto in altra risposta, in Java si dovrebbe rappresentare questo con le classi come spigoli e vertici. Ad esempio un bordo collega due vertici e può essere diretto o indiretto e può contenere un peso. Un vertice può avere un ID, un nome, ecc. Per lo più entrambi hanno proprietà aggiuntive. Così si può costruire il grafico con loro come

Vertex a = new Vertex(1); 
Vertex b = new Vertex(2); 
Edge edge = new Edge(a,b, 30); // init an edge between ab and be with weight 30 

Questo approccio è comunemente utilizzato per implementazioni object oriented, dal momento che è più leggibile e conveniente per gli utenti orientati agli oggetti;).

matrice

Una matrice è un semplice 2 matrice bidimensionale. Supponendo di aver ID vertex di che può essere rappresentato come un array int simili:

int[][] adjacencyMatrix = new int[SIZE][SIZE]; // SIZE is the number of vertices in our graph 
adjacencyMatrix[0][1] = 30; // sets the weight of a vertex 0 that is adjacent to vertex 1 

Questo è comunemente utilizzato per grafi densi cui è necessario accedere indice. Puoi rappresentare una struttura un/diretta e ponderata con questo.

lista di adiacenza

Questo è solo un semplice mix datastructure, io di solito implementare questo utilizzando un HashMap<Vertex, List<Vertex>>.Simile usato può essere il HashMultimap in Guava.

Questo approccio è interessante, perché hai una ricerca di vertici O (1) (ammortizzata) e mi restituisce una lista di tutti i vertici adiacenti a questo particolare vertice che ho richiesto.

ArrayList<Vertex> list = new ArrayList<>(); 
list.add(new Vertex(2)); 
list.add(new Vertex(3)); 
map.put(new Vertex(1), list); // vertex 1 is adjacent to 2 and 3 

Questo è usato per rappresentare grafi sparsi, se si sta applicando a Google, si dovrebbe sapere che il webgraph è scarsa. Puoi gestirli in modo più scalabile usando BigTable.

Oh, e BTW, here è una buona sintesi di questo post con le immagini di fantasia;)

Answer 3

Vantaggio della rappresentazione dell'oggetto (incidence list) è che due vertici adiacenti condividono la stessa istanza del bordo. Ciò facilita la manipolazione con i dati di bordo non orientati (lunghezza, costo, flusso o direzione uniforme). Tuttavia utilizza memoria extra per i puntatori.

Answer 4

Un'altra buona risorsa: Khan Academy - "Representing Graphs"

Oltre lista di adiacenza e matrice di adiacenza, elencano "liste bordo" come un terzo tipo di rappresentazione grafica. Una lista di spigoli può essere interpretata come una lista di "oggetti di bordo" come quelli nella risposta di "oggetti e puntatori" di Thomas.

Vantaggio: Siamo in grado di memorizzare più informazioni circa il bordo (citato da Michal)

Svantaggio: E 'una struttura dati molto lento per lavorare con:

• Lookup un vantaggio: O (log e)
• Rimuovere un bordo: O (e)
• Trova tutti i nodi adiacenti a un dato nodo: O (e)
• Determinare se esiste un percorso tra due nodi: O (e^2)

e = numero di bordi