Una guia per a l'estructura de dades gràfics

Un programador eficaç necessita una comprensió sòlida de les estructures i algorismes de dades. Les entrevistes tècniques sovint posaran a prova les vostres habilitats de resolució de problemes i de pensament crític.

Els gràfics són una de les moltes estructures de dades importants en programació. En la majoria dels casos, comprendre gràfics i resoldre problemes basats en gràfics no és fàcil.

MAKEUSEO VÍDEO DEL DIA

Què és un gràfic i què cal saber al respecte?

Què és un gràfic?

Un gràfic és una estructura de dades no lineal que té nodes (o vèrtexs) amb arestes que els connecten. Tots els arbres són subtipus de gràfics, però no tots els gràfics són arbres, i el gràfic és l'estructura de dades a partir de la qual es van originar els arbres.

Encara que puguis crear estructures de dades en JavaScript i altres idiomes, podeu implementar un gràfic de diverses maneres. Els enfocaments més populars són llistes de vora , llistes d'adjacència , i matrius d'adjacència .

El Guia de la Khan Academy per representar gràfics és un gran recurs per aprendre a representar un gràfic.

Hi ha molts tipus diferents de gràfics. Una distinció comuna és entre dirigit i no dirigit gràfics; aquests apareixen molt en els reptes de codificació i en els usos de la vida real.

Tipus de gràfics

Gràfic dirigit: Un gràfic en què totes les arestes tenen una direcció, també anomenada dígraf.
Gràfic no dirigit: Un gràfic no dirigit també es coneix com a gràfic de dues vies. En els gràfics no dirigits, la direcció de les vores no importa, i el recorregut pot anar en qualsevol direcció.
Gràfic ponderat: Un gràfic ponderat és un gràfic els nodes i arestes del qual tenen un valor associat. En la majoria dels casos, aquest valor representa el cost d'explorar aquest node o vora.
Gràfic finit: Un gràfic que té un nombre finit de nodes i arestes.
Gràfic infinit: Un gràfic que té una quantitat infinita de nodes i arestes.
Gràfic trivial: Un gràfic que només té un node i cap aresta.
Gràfic simple: Quan només una aresta connecta cada parell de nodes d'un graf, s'anomena gràfic simple.
Gràfic nul: Un graf nul és un gràfic que no té arestes que connectin els seus nodes.
Multigràfic: En un multigràfic, almenys un parell de nodes tenen més d'una vora que els connecta. En els multigràfics, no hi ha autobucles.
Gràfic complet: Un gràfic complet és un gràfic en què tots els nodes es connecten a tots els altres nodes del gràfic. També es coneix com a gràfic complet .
Pseudogràfic: Un gràfic que té un bucle propi a part d'altres arestes del gràfic s'anomena pseudogràfic.
Gràfic regular: Un graf regular és un gràfic on tots els nodes tenen graus iguals; és a dir, cada node té el mateix nombre de veïns.
Gràfic connectat: Un graf connectat és simplement qualsevol graf en el qual es connecten dos nodes qualsevol; és a dir, un gràfic amb almenys un camí entre cada dos nodes del gràfic.
Gràfic desconnectat: Un graf desconnectat és l'oposat directe a un graf connectat. En un gràfic desconnectat, no hi ha vores que enllacin els nodes del gràfic, com en un nul gràfic.
Gràfic cíclic: Un gràfic cíclic és un gràfic que conté almenys un cicle de gràfics (un camí que acaba on va començar).
Gràfic acíclic: Un gràfic acíclic és un gràfic sense cicles. Pot ser dirigit o no dirigit.
Subgraf: Un subgraf és un gràfic derivat. És un gràfic format per nodes i arestes que són subconjunts d'un altre gràfic.