Ce sunt graficele, în informatică, și la ce se utilizează pentru? De preferință, în termeni laici.
Am citit definiția pe Wikipedia :
În informatică, un grafic este un tip de date abstract care este menit să implementeze conceptele de grafic și hipergraf din matematică.
O structură de date a graficului constă dintr-un element finit (și posibil mutabil) ) set de perechi ordonate, numite muchii sau arcuri, ale anumitor entități numite noduri sau vârfuri. La fel ca în matematică, se spune că o muchie (x, y) indică sau merge de la x la y. Nodurile pot face parte din structura graficului , sau pot fi entități externe reprezentate prin indici întregi sau referințe.
dar caut o definiție mai puțin formală, mai ușor de înțeles.
Comentarii
- Adică graficele structurii datelor?
- Da, îmi pare rău. Graficele descrise aici en.wikipedia.org/wiki/Graph_(abstract_data_type) , numai eu ‘ caut o definiție mai puțin formală, mai ușor de înțeles.
- @ Justin984 linkurile Wikipedia cu paranteze (și sunt atât de multe dintre ele) nu funcționează aranteze ‘ nu se joacă bine cu formatul Markdown pentru linkuri. Acum, pentru referințe viitoare, vă rugăm să adăugați orice clarificare la întrebarea dvs. în întrebarea însăși, nu în comentarii, acestea nu sunt ‘ t vizibile și ‘ e ușor să le ratezi. ‘ voi edita comentariul dvs. de mai sus în întrebare …
- @ Justin984 Rețineți, de asemenea, că Informatică Stack Exchange ar putea să fie un pic mai potrivit pentru întrebări ca aceasta decât Programatorii. ‘ nu mă înțelegeți greșit, întrebarea este perfect subiect aici și are răspunsuri grozave, dar nu ar fi ‘ dacă nu ar fi rău dacă ați verificat o comunitate care ‘ este puțin mai concentrată pe conceptele de bază ale informaticii decât noi (nu ‘ nu postați aceeași întrebare în mai multe site-uri, totuși, dacă se întâmplă să-l postați pe un site greșit, îl putem muta automat pe cel corect).
Răspundeți
Exemplul unui profan perfect ar putea fi Facebook . Rețeaua dvs., a prietenilor dvs. și prietenii lor etc, sunt denumiți în mod colectiv ca grafic social .
În acest „grafic” oamenii sunt considerați noduri ale graficului și ale
margini sunt legături de prietenie .
În Facebook prieten este o relație bidirecțională (A este prietenul lui B „= B este prietenul lui A”), astfel încât graficul este un Grafic nedirectat . O rețea precum Google+ sau Twitter ar fi considerată un Grafic direcționat , deoarece direcția relației are sens aici.
Toate aceste grafice sunt denumite grafice ciclice , deoarece relațiile dintre noduri pot forma cicluri . Un Arborele genealogic , pe de altă parte, este un tip special de grafic care, printre altele, este Aciclic deoarece nu pot exista cicluri în relația dintre arborele genealogic. (Se numește tehnic un grafic aciclic direcționat (DAG) deoarece este direcționat și aciclic)
Aceasta ar trebui să acopere tot jargonul de bază care implică grafice, așa că acum ar trebui să puteți urmări restul materialului din teren.
Comentarii
- ‘ nu pot crede că nu ‘ nu mi-a trecut prin cap că ‘ s-a numit api graficul facebook. Bun exemplu!
- Arborele genealogic nu ciclic? Nu ar trebui să ‘ să fie, dar din păcate este …
- @MarjanVenema, arborele genealogic este ciclic ? (Este ‘ un grafic direcționat, deci direcția este importantă în determinarea ciclurilor și, probabil, relațiile de pași nu ‘ nu contează.)
- @dbaupp: Nu am nicio dorință de a intra în detalii aici, așa că ‘ voi menționa unul cuvânt: incest.
- @MarjanVenema, ‘ îmi lipsește ideea.Un ciclu într-un grafic direcționat este un model ca
A -> B -> C -> A(adică un cerc de săgeți), incestul doar dăA -> B -> CșiA -> D -> C(adică un diamant). Un ciclu dintr-un arbore genealogic are nevoie de călătorie în timp.
Răspuns
Graficele sunt unul dintre cele mai importante concepte matematice folosit în informatică.
Ați văzut grafice de multe ori. Imaginați-vă că luați un zbor cu avionul dintr-un oraș în altul. Veți găsi inevitabil o revistă frumoasă lucioasă de la compania aeriană pe scaun buzunar în fața ta. Aproape din spatele acelei reviste puteți găsi aproape întotdeauna o hartă care descrie orașele deservite de acea companie aeriană reprezentate ca cercuri, cu zborurile care leagă acele orașe reprezentate ca linii curbe. Acel „este un grafic! Orașele, reprezentate ca cercuri, sunt nodurile acestui grafic, iar zborurile, reprezentate ca linii curbe, sunt marginile. Graficele sunt doar lucruri cu noduri și margini care conectează noduri.
Puteți înfrumuseța aceste grafice simple în diferite moduri. Nu doriți să vedeți doar o grămadă de cercuri și linii când vă uitați la harta respectivă. Orașele respective au nume. Etichetarea acestor orașe are ca rezultat un grafic etichetat. etichetați marginile, de exemplu, zborul 1234.) Informatica asociază deseori datele cu nodurile, uneori cu marginile, dar aceasta este doar o extensie a etichetei. Este încă un grafic etichetat. O altă înfrumusețare rezultă dacă puteți zbura direct din orașul A în orașul B, dar nu din orașul B în orașul A. O modalitate evidentă de a descrie acest lucru este să puneți o săgeată pe linia care leagă orașele. pentru a descrie această relație unidirecțională. Acum aveți un grafic direcționat.
Listele legate, arborii, diagramele de tranziție a stării și o mulțime de alte structuri de date din domeniul informaticii sunt toate exemple de grafice. Este un instrument foarte puternic. concept.
Comentarii
- Am ‘ de fapt extind acel exemplu pentru a observa că toate entitățile descrise în exemplul dvs. ar putea fi descrise ca vârfuri într-un grafic (oraș, avion, revistă, hartă etc.), harta în sine fiind doar un singur vârf.
Răspuns
O întrebare mai bună ar fi „Pentru ce nu sunt utilizate graficele?”. Informatica este, în multe privințe, studiul graficelor.
Un grafic, în termeni laici, este o colecție de obiecte abstracte arbitrare numite „noduri” sau „vârfuri” care reprezintă puncte de conexiune. Acestea sunt apoi conectate prin „căi” sau „margini”. Tipul de date abstracte „Grafic” este o implementare a „Graficului” matematic. Deci, practic aveți noduri și margini ca câmpuri și diverse operații pe care le puteți efectua pe ele. poate, de exemplu, să adauge un nou nod în colecția graficului (aceasta ar putea fi o listă sau o matrice sau o altă structură în funcție de limbă). Apoi, puteți conecta acel nod la nodurile existente. Operațiunile ar include, de asemenea, parcurgerea graficului, verificarea dacă două noduri au o margine (sunt conectate), recuperarea valorilor din noduri sau margini și ștergerea nodurilor sau marginilor din grafic.
În ceea ce privește utilizarea merge, graficele sunt folosite peste tot. Rețeaua le folosește în mod deosebit, dar acestea se găsesc în inteligența artificială, mineritul datelor, dezvoltarea jocurilor, geoinformatica și o serie de alte discipline. În informatică formală, ei văd și mai multă utilizare, și anume ca o modalitate de a reprezenta starea.
În mod efectiv orice puteți reprezenta ca un set de conexiuni poate fi reprezentat ca un grafic și implementat prin acel ADT în unele formular.
Iată un exemplu de grafic pe care l-am realizat:
Răspuns
Un grafic este doar o colecție de obiecte conectate între ele prin linii numite vârfuri.
Termenul „grafic” este o abstractizare și generalizare a multor structuri de date utilizate în dezvoltarea de software. Listele legate, arborii binari și AST „s sunt toate grafice.
Practic, orice colecție de obiecte care are indicii care asociază obiectele între ele este un grafic. După ce aveți un grafic, puteți aplica principiile teoria graficului , pentru a rezolva anumite probleme .