Tutorial della struttura dei dati grafici
Un nodo in un grafico è chiamato vertice (plurale - vertici). A volte è ancora chiamato nodo; Può anche essere chiamato punto. Un collegamento in un grafico è chiamato bordo. A volte è ancora chiamato collegamento; Può anche essere chiamato una linea.
Grafico con molte caratteristiche
Questa figura mostra un grafico con molte caratteristiche:
I cerchi (dischi) sono vertici. Qualsiasi linea retta o linea curva o loop è un bordo.
Caratteristiche del grafico
Vertice
Un vertice è un oggetto. Può essere una casa; Può essere una persona; Può essere un sostantivo astratto; Può essere qualsiasi oggetto a cui puoi pensare.
Bordo
Un bordo è una connessione (relazione) tra due vertici; La connessione può essere astratta.
Ciclo continuo
Un ciclo è un bordo che collega un vertice a se stesso.
Bordo freccia
Considera due persone: John e Peter. Se John presta Peter $ 100 e se John e Peter sono vertici, allora il bordo di prestito punterà verso Peter. Se entrambi i partner dimenticano che Peter è dovuto a John, e Peter presta John $ 100, allora all'altra estremità dello stesso bordo, una punta di freccia indicherà John. Se Peter ha prestato ma $ 75 a John e non $ 100, allora un vantaggio diverso collegherebbe Peter a John. Questo secondo bordo avrà la sua punta di freccia che punta verso John. Nel secondo caso, ci sono due bordi, con una punta di freccia ciascuno, che indica le direzioni opposte.
Il vertice a cui punta un bordo, è un vertice della testa per quel bordo. Il vertice da cui lascia un bordo, è un vertice di coda.
Incidente
Un bordo collega due vertici. Si dice che il bordo sia incidente su entrambi i vertici. Il bordo non ha bisogno di avere una punta di freccia. I due vertici sono noti come gli endpoint del bordo. È possibile avere un grafico in cui un vertice non appartiene a nessun vantaggio, ma ciò non sarà considerato in questo tutorial.
Grafico non diretto
Un bordo può essere una freccia, oppure non può. Un grafico in cui nessun bordo è una freccia è un grafico non indirizzato. Un bordo può essere rappresentato da una linea retta o da una curva o da un loop.
Grafico diretto
Un grafico in cui ogni bordo è una freccia (direzione) è un grafico diretto. Un bordo freccia può essere rappresentato da una linea retta con una punta di freccia o una curva con una punta di freccia o un anello con una punta di freccia.
L'assenza di una direzione sul bordo di un grafico non orientato, significa ogni bordo del grafico non diretto, è bidirezionale.
Grado di vertice
Il numero di bordi che sono incidenti su un vertice è il grado del vertice. Un ciclo ha due incidenze su un vertice, quindi un ciclo viene conteggiato due volte.
Ordine di un grafico
L'ordine di un grafico è il numero di vertici nel grafico.
Multigrafo
Un multigraph è un grafico, in cui per alcune coppie di vertici, ci sono più di un bordi. Un multigraph non diretto è un tale grafico in cui i bordi non hanno direzioni (non sono frecce). Un multigrafo diretto è uno in cui ogni bordo è una freccia e per coppie di vertici che hanno più di una freccia, un vertice è la coda di quelle frecce e l'altro vertice è la testa delle stesse frecce. Il seguente diagramma mostra un multigtigiatto non diretto:
Più di un bordi (i.e. bordi multipli) per una coppia di vertici sono anche chiamati bordi paralleli.
Faretra
Una faretra è un multigrafo che consente loop (uno o più loop). Alcuni multigrafi non consentono i loop.
Grafico semplice
Un grafico semplice è un grafico in cui non ci sono due coppie di vertici hanno bordi multipli. I loop non sono consentiti in un grafico semplice.
Grafico vuoto
Un grafico vuoto è un grafico senza vertici e quindi senza bordi.
Grafico misto
Un grafico misto è un grafico in cui alcuni bordi sono frecce e altri no; In altre parole: alcuni bordi hanno indicazioni e altri non sono diretti.
Grafico ponderato
È possibile avere un grafico in cui un numero, noto come peso, è assegnato a ciascun bordo. Alcuni bordi hanno lo stesso numero, ma i numeri sono generalmente diversi. Un tale grafico è chiamato grafico ponderato. I numeri per un grafico particolare possono rappresentare lunghezze o costi (prezzi) o grandezza di qualche tipo, a seconda del problema.
Indegree e outdegree
Il vocabolario, indegree e outdegree sono applicabili solo a un grafico diretto. Il grafico può o meno essere un multigrafe. Il grafico può o meno avere loop.
Il numero di punte di freccia collegate a un vertice è l'indegreo di quel vertice. Una freccia con una sola punta di freccia ha una testa e un'estremità di coda. Il numero di code collegate a un vertice è l'esterno di quel vertice.
Nota: un grafico con bordi multipli per la coppia di vertici, in cui i bordi multipli sono in direzioni opposte, non è affrontato in questo tutorial.
Rappresentazione del software di un grafico
Un grafico può essere rappresentato nel software nel modo in cui viene disegnato sul diagramma. Un grafico può anche essere rappresentato nel software da una matrice matematica (array bidimensionale). Una di queste matrici si chiama Matrix adiacenza.
Matrice di adiacenza
Una matrice di adiacenza è una matrice quadrata. Le intestazioni per le righe sono tutti i vertici, scritti in ordine crescente. Le intestazioni per le colonne sono ancora gli stessi vertici, scritti in ordine crescente. Il conteggio delle righe o delle colonne di una matrice inizia da 1 e non zero come con gli array. Quando si identifica un elemento in una matrice, il numero di riga viene scritto prima del numero di colonna.
Per un grafico non orientato, ogni voce (elemento) nella matrice di adiacenza è il numero di bordi che collegano i due vertici corrispondenti. Un ciclo dovrebbe essere conteggiato due volte. Per un grafico diretto, ogni voce nella matrice di adiacenza è il numero di bordi che lasciano un vertice di riga ed entrano nel vertice della colonna corrispondente o è il numero di bordi che lasciano un vertice della colonna ed entrano nel vertice della riga corrispondente. La scelta è quella del programmatore. In questa situazione (in entrambi i casi), un ciclo dovrebbe essere ancora conteggiato una volta.
Nota: un grafico è un diagramma è una struttura di dati a sé stante. Una matrice di adiacenza è anche una struttura di dati a sé stante.
Matrix grafico non diretto e adiacenza
I seguenti diagrammi mostrano un grafico non indirizzato e la corrispondente matrice di adiacenza:
La diagonale principale di una matrice è la diagonale dall'alto-sinistra al basso a destra. Una matrice non diretta è simmetrica sulla diagonale principale. La voce della matrice per la riga A e la colonna C è 1, il che significa che esiste un bordo che collega il vertice A e il vertice C. La voce della matrice per la riga C e la colonna B è 3, il che significa che ci sono 3 bordi che collegano il vertice C e il vertice B. Le altre voci sono spiegate allo stesso modo.
La somma delle voci per una riga fornisce il numero di bordi (grado) per il vertice corrispondente. La somma delle voci per la riga A è 2, il che significa che 2 bordi sono collegati al vertice a. La somma delle voci per la riga B è 6, il che significa che 6 bordi sono collegati al vertice b. Il resto delle voci è spiegato allo stesso modo.
Matrix grafico diretto e adiacenza
I seguenti diagrammi mostrano un grafico diretto e la corrispondente matrice di adiacenza:
La matrice di adiacenza per un grafico diretto non è necessariamente simmetrica sulla diagonale principale. La voce della matrice per la riga A e la colonna C è 1, il che significa che un bordo lascia dal vertice A al vertice C. La voce della matrice per la riga C e la colonna B è 3, che significa 3 bordi lasciano dal vertice C a Vertex B. Le altre voci sono spiegate allo stesso modo.
La somma delle voci per una colonna fornisce l'indegree per il vertice (colonna). La somma delle voci per una riga dà l'esterno per il vertice (riga). La somma delle voci per la colonna A è 1, il che significa che un bordo è diretto al vertice a. La somma delle voci per la riga B è 2, che significa 2 bordi lasciano dal vertice b. Il resto delle voci è spiegato allo stesso modo.
Operazioni grafiche
Una struttura di dati, come un grafico, è costituita da un insieme di valori di dati o un insieme di oggetti, oltre alla relazione tra gli oggetti, oltre alle operazioni (funzioni) tra gli oggetti. Le relazioni in un grafico sono indicate dai bordi. Su questo, un grafico dovrebbe avere almeno le seguenti operazioni:
adiacente (g, x, y)
G significa grafico. Questa operazione verifica se un bordo collega Vertex X e Vertex Y. Il valore e la posizione di una voce in una matrice indicano la connessione di un bordo (e il suo tipo).
vicini (g, x)
Questa operazione restituisce un elenco di tutti i vertici che sono direttamente collegati al vertice x. Il valore e la posizione di una voce in una matrice indicano la connessione di un bordo.
Rimuovi_vertex (g, x)
Questa operazione rimuove un vertice, x da un grafico. Se il vertice non aveva un vantaggio, non ci sono problemi. Tuttavia, se il vertice aveva collegamenti, allora i collegamenti (bordi) dovrebbero essere rimossi anche. Il valore e la posizione di una voce in una matrice indicano la presenza di un particolare vertice. Se viene rimosso un vertice, la matrice deve essere riadattata.
add_vertex (g, x)
Questo aggiunge un vertice, x senza aggiungere bordi o sostituisce un vertice che aveva bordi ma era stato rimosso. Il valore e la posizione di una voce in una matrice indicano la presenza di un particolare vertice. Se viene aggiunto un vertice, la matrice deve essere riadattata.
add_edge (g, x, y)
Questa operazione aggiunge un nuovo bordo tra il vertice x e il vertice y se il bordo non era lì. Il valore e la posizione di una voce in una matrice indicano la presenza di un bordo particolare. Se viene aggiunto un bordo, la matrice deve essere riadattata.
Rimuovi_edge (g, x, y)
Questa operazione rimuoverebbe il bordo tra il vertice x e il vertice y se il bordo fosse lì. Il valore e la posizione di una voce in una matrice indicano la presenza di un bordo particolare. Se viene rimosso un bordo, la matrice deve essere riadattata.
get_vertex_value (g, x)
Questa operazione restituisce il valore, v associato al vertice, x. Per raggiungere questo obiettivo, hai bisogno di un set di alimentazione di sottoinsiemi per le etichette del vertice e i loro valori.
set_vertex_value (g, x, v)
Questa operazione fornisce un nuovo valore, V per il valore associato al vertice, x. Per raggiungere questo obiettivo, hai bisogno di un set di alimentazione di sottoinsiemi per le etichette del vertice e i loro valori.
Alcuni grafici associano anche i valori ai loro bordi. Tali grafici richiedono le seguenti operazioni aggiuntive:
get_edge_value (g, x, y)
Questa operazione restituisce il valore, V associato al bordo, (x, y). Per raggiungere questo obiettivo, è necessario un set di alimentazione per i bordi e i loro valori.
set_edge_value (g, x, y, v)
Questa operazione fornisce un nuovo valore, V per il valore associato al bordo, (x, y). Per raggiungere questo obiettivo, è necessario un set di alimentazione per i bordi e i loro valori.
Conclusione
Un grafico è un set di vertici collegati ai bordi. Un grafico può essere indirizzato o diretto. I bordi possono essere non direzionali o direzionali. I loop possono essere presenti o assenti in un grafico. Quello che dovresti imparare dopo è impostato, set di alimentazione e multiset relativi ai grafici. Successivamente, dovresti imparare i diversi tipi di grafici, come un grafico orientato, grafico normale, grafico completo, grafico bipartito, grafico del torneo, grafico della rete di flusso, ecc.
Chrys