Hola a tots
En aquesta nota, vaig decidir enumerar les principals estructures de dades utilitzades per emmagatzemar gràfics en informàtica, i també parlar d'un parell d'estructures més que d'alguna manera vaig "cristal·litzar" per si mateix.
Així doncs, comencem. Però no des del principi: crec què és un gràfic i què són (dirigit, no dirigit, ponderat, sense ponderar, amb o sense múltiples arestes i bucles), tots ja ho sabem.
Així que anem. Quines són les opcions per a les estructures de dades per a "emmagatzematge de gràfics" que tenim.
1. Estructures de dades matricials
1.1 Matriu d'adjacència. La matriu d'adjacència és una matriu on els encapçalaments de fila i columna corresponen als números dels vèrtexs del gràfic, i el valor de cadascun dels seus elements a(i,j) està determinat per la presència o absència d'arestes entre els vèrtexs i i j (és clar que per a un gràfic no dirigit aquesta matriu serà simètrica, o podem estar d'acord que emmagatzemem tots els valors només per sobre de la diagonal principal). Per als gràfics no ponderats, a(i,j) es pot establir pel nombre d'arestes de i a j (si no hi ha tal aresta, aleshores a(i,j) = 0), i per als gràfics ponderats, també pel pes (pes total) de les vores esmentades.
1.2 Matriu d'incidència. En aquest cas, el nostre gràfic també s'emmagatzema en una taula, en la qual, per regla general, els nombres de files corresponen als nombres dels seus vèrtexs i el nombre de columnes corresponen a arestes prenumerades. Si un vèrtex i una aresta són incidents entre si, aleshores s'escriu un valor diferent de zero a la cel·la corresponent (per als gràfics no dirigits, s'escriu 1 si el vèrtex i l'aresta són incidents, per als gràfics dirigits - "1" si el l'aresta "deixa" el vèrtex i "-1" si hi "inclou" (es recorda amb força facilitat, perquè el signe "menos" també és, per dir-ho, "inclòs" al nombre "-1")) . Per als gràfics ponderats, de nou, en lloc d'1 i -1, podeu especificar el pes total de l'aresta.
2. Estructures de dades enumerades
2.1 llista d'adjacència. Bé, aquí, sembla, tot és senzill. Cada vèrtex del gràfic es pot associar, en general, a qualsevol estructura enumerativa (llista, vector, matriu, ...), que emmagatzemarà els números de tots els vèrtexs adjacents al donat. Per als gràfics dirigits, inclourem en aquesta llista només aquells vèrtexs que tenen una vora "dirigida" del vèrtex de la característica. Per als gràfics ponderats, la implementació serà més complexa.
2.2 Llista de costelles. Una estructura de dades força popular. La llista d'arestes, com ens diu Captain Evidence, és en realitat una llista d'arestes de gràfic, cadascuna de les quals està especificada pel vèrtex inicial, vèrtex final (per als gràfics no dirigits, l'ordre no és important aquí, tot i que es poden utilitzar diverses regles per la unificació, per exemple, especifica els vèrtexs en l'ordre creixent) i el pes (només per als gràfics ponderats).
Podeu veure amb més detall (i amb il·lustracions) les llistes de matrius enumerades anteriorment, per exemple, .
2.3 Matriu d'adjacència. No és l'estructura més comuna. En el seu nucli, és una forma d'"empaquetar" llistes d'adjacència en una estructura enumerativa (matriu, vector). Els primers n (segons el nombre de vèrtexs del gràfic) d'aquesta matriu contenen els índexs inicials de la mateixa matriu, a partir dels quals tots els vèrtexs adjacents a la matriu donada s'escriuen en una fila.
Aquí he trobat l'explicació més entenedora (per a mi):
3. Vector d'adjacència i matriu d'adjacència associativa
Va succeir que l'autor d'aquestes línies, no essent un programador professional, sinó que es dedicava periòdicament a gràfics, sovint es tractava de llistes d'arestes. De fet, és convenient que el gràfic tingui múltiples bucles i arestes. Per tant, en el desenvolupament de les clàssiques llistes d'arestes, proposo parar atenció al seu "desenvolupament / branca / modificació / mutació", és a dir: el vector d'adjacència i la matriu d'adjacència associativa.
3.1 Vector d'adjacència
Cas (a1): gràfic no ponderat
Anomenarem el vector d'adjacència d'un gràfic sense ponderar un conjunt ordenat d'un nombre parell d'enters (а[2i], a[2i+1],..., on i es numera c 0), en el qual cada parell de nombres a[ 2i], a[2i+1 ] especifica la vora del gràfic entre els vèrtexs a[2i] i a[2i+1], respectivament.
Aquest format de registre no conté informació sobre si el gràfic està dirigit (ambdues opcions són possibles). Quan s'utilitza el format per a un dígraf, es considera que l'aresta es dirigeix des de a[2i] a a[2i+1]. Aquí i a continuació: per als gràfics no dirigits, si cal, es poden aplicar els requisits per a l'ordre d'escriptura dels vèrtexs (per exemple, que el vèrtex amb el valor més baix del nombre assignat vagi primer).
En C++, té sentit definir un vector d'adjacència utilitzant std::vector, per tant es va triar el nom d'aquesta estructura de dades.
Cas (a2): gràfic no ponderat, els pesos de les vores són enters
Per analogia amb el cas (a1), anomenarem el vector d'adjacència d'un gràfic ponderat amb pesos enters d'arestes un conjunt ordenat (matriu dinàmic) de nombres (а[3i], a[3i+1], a[3i+2 ],…, on i es numera c 0), on cada “triplet” de nombres a[3i], a[3i+1], a[3i+2] defineix una vora gràfica entre els vèrtexs numerats a[3i] i a [3i+1], respectivament, i el valor a [3i+2] és el pes d'aquesta aresta. Aquest gràfic pot ser o no dirigit.
Cas (b): gràfic no ponderat, pesos de les vores no enters
Com que els elements heterogenis no es poden emmagatzemar en una matriu (vector), és possible, per exemple, la implementació següent. El gràfic s'emmagatzema en un parell de vectors, en els quals el primer vector és el vector d'adjacència del gràfic sense pesos, i el segon vector conté els pesos corresponents (possible implementació per a C++: std::pair). ). Així, per a una aresta definida per un parell de vèrtexs als índexs 2i, 2i+1 del primer vector, el pes serà igual a l'element de l'índex i del segon vector.
Bé, per què és necessari?
Bé, a l'autor d'aquestes línies li va semblar força útil per resoldre una sèrie de problemes. Bé, des d'un punt de vista formal, hi haurà aquests avantatges:
- El vector d'adjacència, com qualsevol altra estructura "enumerativa", és bastant compacte, ocupa menys memòria que la matriu d'adjacència (per a gràfics dispersos) i és relativament fàcil d'implementar.
- Els vèrtexs de la gràfica, en principi, es poden marcar amb nombres negatius. De sobte, sí, cal tal "perversió".
- Els gràfics poden contenir múltiples arestes i múltiples bucles, amb diferents pesos (positiu, negatiu, fins i tot zero). Aquí no hi ha restriccions.
- També podeu assignar diferents propietats a les vores, però consulteu la Secció 4 per obtenir-ne més informació.
Tanmateix, cal admetre que aquesta "llista" no implica un accés ràpid a la vora. I aquí la matriu d'adjacència associativa ve al rescat, que es comenta a continuació.
3.2 Matriu d'adjacència associativa
Per tant, si l'accés a una vora concreta, el seu pes i altres propietats és crític per a nosaltres, i els requisits de memòria no ens permeten utilitzar la matriu d'adjacència, pensem com podem canviar el vector d'adjacència per resoldre aquest problema. Per tant, la clau és la vora del gràfic, que es pot especificar com un parell ordenat d'enters. Quin aspecte té? Ja sigui en una clau en una matriu associativa? I si és així, per què no ho implementem? Tinguem una matriu associativa d'aquest tipus, on a cada clau, un parell ordenat de nombres enters, se li assignarà un valor: un nombre enter o real que especifica el pes de la vora. En C++, és convenient implementar aquesta estructura basada en el contenidor std::map (std::map , int> o std::map , double>), o std::multimap si s'esperen múltiples arestes. Bé, aquí tenim una estructura d'emmagatzematge de gràfics que ocupa menys memòria que les estructures de "matriu", pot definir gràfics amb múltiples bucles i arestes i ni tan sols té requisits estrictes per a la no-negativitat dels números de vèrtex (no ho sé). qui ho necessita, però encara).
4. Almenys "omple" les estructures de dades, però falta alguna cosa
I la veritat és que quan resolem una sèrie de problemes, és possible que hàgim d'assignar algunes característiques a les vores del gràfic i, en conseqüència, emmagatzemar-les. Si és possible reduir sense ambigüitats aquestes característiques a nombres enters, llavors és possible emmagatzemar aquests "gràfics de característiques complementaris" utilitzant versions ampliades del vector d'adjacència i la matriu associativa d'adjacència.
Per tant, tinguem un gràfic no ponderat, per a cada aresta del qual cal emmagatzemar, per exemple, 2 característiques addicionals especificades per nombres enters. En aquest cas, és possible definir el seu vector d'adjacència com un conjunt ordenat de no "parells", sinó "quartets" de nombres enters (а[2i], a[2i+1], a[2i+2], a[ 2i+3]…) , on a[2i+2] i a[2i+3] definiran les característiques de l'aresta corresponent. Per a un gràfic amb pesos enters d'arestes, l'ordre és generalment similar (l'única diferència és que les característiques seguiran el pes de l'aresta i estan donades pels elements a[2i+3] i a[2i+4], mentre que la vora en si vindrà no 4, sinó 5 números ordenats). I per a un gràfic amb pesos de vora no enters, les característiques es poden escriure en el seu component no ponderat.
Quan s'utilitza una matriu d'adjacència associativa per a gràfics amb peses d'arestes enters, és possible establir com a valor no un nombre únic, sinó una matriu (vector) de nombres que especifiquen, a més del pes de la vora, totes les altres característiques necessàries. Al mateix temps, un inconvenient per al cas de pesos no enters serà la necessitat d'establir la característica com a nombre de coma flotant (sí, això és un inconvenient, però si no n'hi ha tantes, i si no No els poseu un doble massa "complicat", llavors pot ser que no sigui res). Així, en C++, les matrius d'adjacència associativa ampliades es poden definir de la següent manera: std::map , std::vector> o std::map , std::vector, amb el primer valor del "valor per clau-vector" el pes de la vora, seguit de les designacions numèriques de les seves característiques.
Literatura:
Sobre els gràfics i els algorismes en general:
1. Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algoritmes: construcció i anàlisi, 2a edició: Per. de l'anglès. – M.: Williams Publishing House, 2011.
2. Harari Frank. Teoria dels grafs. M.: Mir, 1973.
Informe de l'autor sobre aquests mateixos vectors i matrius d'adjacència associativa:
3. Txernoukhov S.A. Vector d'adjacència i matriu d'adjacència associativa com a maneres de representar i emmagatzemar gràfics / SA Chernouhov. Vector d'adjacència i mapa d'adjacència com a estructures de dades per representar un gràfic // Recull d'articles de la Conferència Científica i Pràctica Internacional "Problemes d'implementació dels resultats de desenvolupaments innovadors i maneres de resoldre'ls" (Saratov, 14.09.2019/2019/65). – Sterlitamak: AMI, 69, p. XNUMX-XNUMX
Fonts en línia útils sobre el tema:
4.
5.
Font: www.habr.com