Cosa sono i grafici, in informatica, e a cosa servono per? Preferibilmente in parole povere.
Ho letto la definizione su Wikipedia :
In informatica, un grafo è un tipo di dati astratto che ha lo scopo di implementare i concetti di grafo e ipergrafo dalla matematica.
Una struttura di dati di grafo consiste in un dato finito (e possibilmente mutabile ) insieme di coppie ordinate, chiamate bordi o archi, di certe entità chiamate nodi o vertici. Come in matematica, si dice che un arco (x, y) punti o vada da x a y. I nodi possono essere parte della struttura del grafo , o possono essere entità esterne rappresentate da indici o riferimenti interi.
ma sto cercando una definizione meno formale e più facile da capire.
Commenti
- Intendi rappresentare graficamente la struttura dei dati?
- Sì, mi dispiace. Grafici come descritto qui en.wikipedia.org/wiki/Graph_(abstract_data_type) , solo io ‘ sto cercando una definizione meno formale e più facile da capire.
- @ Justin984 Wikipedia si collega con le parentesi (e ce ne sono così tante) non ‘ t funzionano, le parentesi non ‘ t funziona bene con il formato Markdown per i link. Ora, per riferimento futuro, aggiungi eventuali chiarimenti alla tua domanda nella domanda stessa, non nei commenti, non sono ‘ così visibili e ‘ è facile perderli. ‘ modificherò il tuo commento sopra nella domanda …
- @ Justin984 Tieni inoltre presente che Informatica Stack Exchange potrebbe essere un po più appropriato per domande come questa rispetto ai programmatori. Non ‘ fraintendetemi, la domanda è perfettamente sullargomento qui e ha ottenuto ottime risposte, ma ‘ non guasterebbe se hai controllato una community che ‘ è un po più concentrata sui concetti fondamentali dellinformatica di quanto lo siamo noi (non ‘ t pubblicare la stessa domanda in più siti però, se ti capita di pubblicarlo nel sito sbagliato, possiamo spostarlo automaticamente in quello giusto).
Risposta
Un perfetto esempio per laico potrebbe essere Facebook . La rete di te, i tuoi amici e i loro amici e così via sono collettivamente denominati grafico sociale .
In questo “grafico” le persone sono considerate nodi del grafico e
bordi sono link di amicizia .
In Facebook amico è una relazione bidirezionale (A è lamico di B => B è lamico di A) quindi il grafico è un Grafico non indirizzato . Una rete come Google+ o Twitter sarebbe considerata un Grafico diretto poiché la direzione della relazione qui ha un significato.
Tutti questi grafici sono indicati come grafici ciclici , poiché le relazioni tra i nodi possono formare cicli . Un Albero genealogico , daltra parte, è un tipo speciale di grafico che, tra le altre cose, è Aciclico poiché non possono esserci cicli nella relazione dellalbero genealogico. (Tecnicamente è chiamato Grafico aciclico diretto (DAG) poiché è sia diretto che aciclico)
Questo dovrebbe coprire tutto il gergo di base che coinvolge i grafici, quindi ora dovresti essere in grado di seguire il resto del materiale sul campo.
Commenti
- Non posso ‘ credere che non ‘ Mi viene in mente che ‘ si chiama API del grafico di Facebook. Buon esempio!
- Albero genealogico non ciclico? Non dovrebbe ‘ essere, ma sfortunatamente è …
- @MarjanVenema, lalbero genealogico è ciclico ? (È ‘ un grafico diretto, quindi la direzione è importante per determinare i cicli e presumibilmente le relazioni tra i passi don ‘ non conta davvero.)
- @dbaupp: non desidero entrare nei dettagli qui, quindi ‘ ne menzionerò solo uno parola: incesto.
- @MarjanVenema, ‘ ti manca il punto.Un ciclo in un grafico orientato è uno schema come
A -> B -> C -> A(cioè un cerchio di frecce), lincesto dà soloA -> B -> CeA -> D -> C(cioè un diamante). Un ciclo in un albero genealogico richiede un viaggio nel tempo.
Risposta
I grafici sono uno dei concetti matematici più importanti utilizzato in informatica.
Hai visto grafici molte volte. Immagina di prendere un volo aereo da una città allaltra. Troverai inevitabilmente una bella rivista patinata della compagnia aerea sul sedile tasca davanti a te. Sul retro di quella rivista puoi quasi sempre trovare una mappa che raffigura le città servite da quella compagnia aerea rappresentate da cerchi, con i voli che collegano quelle città rappresentate da linee curve. Quello “un grafico! Le città, rappresentate come cerchi, sono i nodi di questo grafico e i voli, rappresentati come linee curve, sono i bordi. I grafici sono solo cose con nodi e bordi che collegano i nodi.
Puoi abbellire questi grafici semplici in vari modi. Non vuoi vedere solo un gruppo di cerchi e linee quando guardi quella mappa. Quelle città hanno nomi. Etichettando queste città si ottiene un grafico etichettato. (Puoi anche etichettare i bordi, ad esempio, il volo 1234.) Linformatica spesso associa i dati ai nodi, a volte ai bordi, ma questa è solo unestensione delletichetta. È ancora un grafico etichettato. Un altro abbellimento si ottiene se puoi volare direttamente dalla città A alla città B, ma non dalla città B alla città A. Un modo ovvio per descrivere questo è mettere una freccia sulla linea che collega le città per rappresentare questa relazione unidirezionale. Ora hai un grafico diretto.
Elenchi collegati, alberi, diagrammi di transizione di stato e molte altre strutture di dati di informatica sono tutti esempi di grafici. È un concetto.
Commenti
- ‘ estendere lesempio per notare che tutto le entità descritte nel tuo esempio potrebbero essere rappresentate come vertici in un grafico (città, aereo, rivista, mappa, ecc.), la mappa stessa essendo solo un singolo vertice.
Risposta
Una domanda migliore sarebbe “Per cosa non vengono utilizzati i grafici t?”. Linformatica è, per molti aspetti, lo studio dei grafici.
Un grafo, in parole povere, è una raccolta di oggetti astratti arbitrari chiamati “nodi” o “vertici” che rappresentano punti di connessione. Sono quindi collegati tramite “percorsi” o “bordi”. Il tipo di dati astratto “Grafico” è unimplementazione del “Grafico” matematico. Quindi, in pratica, hai nodi e archi come campi e varie operazioni che puoi eseguire su di essi. può, ad esempio, aggiungere un nuovo nodo alla raccolta del grafico (potrebbe essere un elenco o un array o qualche altra struttura a seconda della lingua). È quindi possibile collegare quel nodo a nodi esistenti. Le operazioni includerebbero anche lattraversamento del grafico, il controllo se due nodi condividono un bordo (sono collegati), il recupero di valori da nodi o bordi e leliminazione di nodi o bordi dal grafico.
Per quanto riguarda lutilizzo va, i grafici sono usati ovunque. Il networking ne fa un uso particolarmente intenso, ma si trovano nellintelligenza artificiale, nel data mining, nello sviluppo di giochi, nella geoinformatica e in una miriade di altre discipline. Nellinformatica formale, vedono ancora più uso, vale a dire come un modo di rappresentare lo stato.
In effetti tutto ciò che puoi rappresentare come un insieme di connessioni può essere rappresentato come un grafico e implementato tramite quellADT in alcuni form.
Ecco un esempio grafico che ho realizzato:
Risposta
Un grafo è solo una raccolta di oggetti collegati tra loro da linee chiamate vertici.
Il termine “grafo” è unastrazione e una generalizzazione di molti strutture di dati utilizzate nello sviluppo di software. Elenchi collegati, alberi binari e AST “ sono tutti grafici.
Fondamentalmente, qualsiasi raccolta di oggetti che ha puntatori che associano gli oggetti tra loro è un grafico. Una volta che hai un grafico, puoi applicare i principi della teoria dei grafi ad esso, per risolvere alcuni problemi .