Quale struttura dati rappresenta un grafico triangolare non orientato

4

Volevo creare un grafico simile a questo in C ++:

Quello che implementerò avrà più bordi e vertici, ma userà questo stile triangolare. Volevo creare qualcosa su cui avrei potuto eseguire vari algoritmi di ricerca per trovare percorsi più brevi verso i vertici selezionati (o il più lungo senza loop ecc.). È un grafico non ponderato per cominciare; tuttavia, stavo progettando di dare i pesi in futuro.

Ho avuto qualche problema con il modo in cui rappresentavo questo grafico per un paio di motivi: dato che voglio avere più vertici (forse 105 vertici), qualsiasi tipo di lista sarebbe noioso scrivere quali vertici sono connessi a in ogni oggetto (o c'è un modo per automatizzare l'assegnazione dei membri di un oggetto vertice che indica la connessione?). Inoltre, stavo trovando strano provare a implementarlo in un array 2d perché la matrice è di natura quadrata, e io mi occupo di triangoli; pensare alla ponderazione dei bordi e assegnare un valore tra due vertici ha reso ancora meno intuitivo un array.

    
posta han42 21.05.2012 - 14:11
fonte

1 risposta

2

Potresti non aver necessariamente bisogno di risolvere il tuo problema attraverso una struttura dati specializzata; puoi, per esempio, trovare uno schema di indirizzamento per ogni nodo, che ti permette di localizzare nodi vicini nel tempo O (1) e utilizzare una struttura dati generica per navigare.

Un semplice schema qui assegnerebbe a ogni nodo una tupla (n, m) , dove n è il livello e m è l'indice del nodo (presupponendo 0-indexed, per un nodo valido 0 < = m < = n ). Per ogni nodo, derivare tutti i possibili nodi vicini (ni, mi) è semplice (smth (n-1, m-1), (n-1, m), (n, m-1), (n, m + 1) ecc. - di questi si mantengono quelli che sono validi (0 < = mi < = ni < la dimensione del triangolo qui ).

I valori possono essere memorizzati in un vettore, l'indice del nodo (n, m) è, in modo univoco, n (n + 1) / 2 + m .

    
risposta data 22.05.2012 - 15:47
fonte

Leggi altre domande sui tag