Grafikon (absztrakt típus)

Az informatikában , különösen a szoftverfejlesztésben , az absztrakt típusú grafikon a specifikáció formális adatai, amelyek meghatározzák az objektum matematikai grafikonját és a velük végrehajtható műveletek halmazát. Ezt az adattípust azért hívják „absztraktnak”, mert megfelel annak a specifikációnak, amelyet egy konkrét adatstruktúrának végre kell hajtania .

Leírás

Az absztrakt adatszerkezet grafikon áll egy sor kész, adott esetben változékony a csúcsok vagy csomópontok vagy tételek , egy sor rendezett párok, vagy sem az ilyen elemek Ezek párok élek , nem-orientált ívek vagy vonalak egy irányítatlan gráf, és a nyilak , orientált élek , ívek vagy orientált vonalak orientált esetben. A csúcspontok lehetnek a szerkezet részei, vagy lehetnek külső entitások, amelyeket egész számok vagy hivatkozások képviselnek .

A grafikonszerkezet minden élhez társíthat egy "értéket", például címkét vagy numerikus értéket (költség, kapacitás, hossz stb.). Általánosabban: a grafikon két objektumkészlettel is megadható, az egyik csúcs és az élek halmaza, amelyek két leképezéssel vannak ellátva, amelyek minden élhez társítják kezdő csúcsát és érkezési csúcsát. Ez a látomás lehetővé teszi az értékek társítását minden objektumhoz (csúcs vagy él).

Tevékenységek

A G grafikon adatstruktúra által biztosított alapvető műveletek általában a következőket tartalmazzák:

• sont_adjacents( G , x , y ): teszteli, hogy van-e él x- től y-ig ;
• voisins( G , X ): lista csúcsai, amelyek szomszédos x ;
• ajouter_sommet( G , x ): add hozzá az x csúcsot, ha még nincs ott;
• supprimer_sommet( G , x ): távolítsa el az x csúcsot, ha létezik;
• ajouter_arête( G , x , y ): hozzáadja a szélén x a y , ha az még nincs ott;
• supprimer_arête( G , x , y ): távolítsa el az élt x- től y-ig, ha létezik;
• retourner_valeur_sommet( G , x ): az x-hez társított értéket adja vissza ;
• fixer_valeur_sommet( G , X , v ): készletek értéke x a v .

Az élekkel értékeket társító struktúrák általában a következő műveleteket hajtják végre:

• retourner_valeur_arête( G , x , y ): az él ( x , y ) értékét adja vissza ;
• fixer_valeur_arête( G , x , y , v ): meghatározza az értéket az él ( x , y ) a v .

Képviseletek

Különböző adatstruktúrákat használnak a gyakorlatban a grafikonok ábrázolásához:

Adjacency lista A csúcspontok objektumokként vagy rekordokként vannak ábrázolva, és minden csúcshoz tartozik a szomszédos csúcsok társított listája . Ez a struktúra lehetővé teszi további adatok megőrzését a csúcsok számára. Az élekkel kapcsolatos további információk tárolhatók az objektumokban, ha az éleket objektumok képviselik. Ebben az esetben minden csúcs tartalmazhatja a szomszédos éleket és minden él a beeső csúcsait. Adjacencia mátrix Ez egy négyzetmátrix , ahol a sorok a kezdő csúcsokat, az oszlopok pedig a befejező csúcsokat képviselik. A bejegyzés kijelöli az ív jelenlétét, vagy lehet ívértéke. Irányítatlan gráfok esetén a mátrix szimmetrikus.|V|×|V|{\ displaystyle | V | \ times | V |} Incidencia mátrix Ez egy mátrix , ahol a vonalak a csúcsokat, az oszlopok pedig az éleket képviselik. Egy bejegyzés jelzi, hogy az él beesik-e a tetején . Pontosabban :|V|×|E|{\ displaystyle | V | \ alkalommal | E |}bx,nál nél{\ displaystyle b_ {x, a}}nál nél{\ displaystyle a}x{\ displaystyle x} bx,nál nél={-1,ha nál nél olyasmi x1,ha nál nél belép x0ha nem.{\ displaystyle b_ {x, a} = {\ begin {cases} -1, & {\ text {si}} a {\ text {fajta}} x \\ 1, és {\ text {si}} a {\ text {enter}} x \\ 0 és {\ text {különben}}. \ end {esetek}}} Oszloponként csak két nem nulla érték van (és hurok esetén csak egy).

Az alábbi táblázat bemutatja a grafikonokon megjelenő különféle műveletek időbeli összetettségét az ábrázolásoknak megfelelően. Itt van a csúcsok és az élek száma. |V|{\ displaystyle | V |}|E|{\ displaystyle | E |}

	Adjacency lista	Adjacencia mátrix	Incidencia mátrix
Készítse el a grafikont	O(|V|+|E|){\ displaystyle O (| V | + | E |)}	O(|V|2){\ displaystyle O (| V | ^ {2})}	O(|V|⋅|E|){\ displaystyle O (| V | \ cdot | E |)}
Adjon hozzá egy csúcsot	O(1){\ displaystyle O (1)}	O(|V|2){\ displaystyle O (| V | ^ {2})}	O(|V|⋅|E|){\ displaystyle O (| V | \ cdot | E |)}
Adjon hozzá egy élt	O(1){\ displaystyle O (1)}	O(1){\ displaystyle O (1)}	O(|V|⋅|E|){\ displaystyle O (| V | \ cdot | E |)}
Távolítson el egy csúcsot	O(|E|){\ displaystyle O (| E |)}	O(|V|2){\ displaystyle O (| V | ^ {2})}	O(|V|⋅|E|){\ displaystyle O (| V | \ cdot | E |)}
Töröljön egy élt	O(|V|){\ displaystyle O (| V |)}	O(1){\ displaystyle O (1)}	O(|V|⋅|E|){\ displaystyle O (| V | \ cdot | E |)}
Adjacencia teszt két csúcs között	O(|V|){\ displaystyle O (| V |)}	O(1){\ displaystyle O (1)}	O(|E|){\ displaystyle O (| E |)}
Megjegyzések	Lassan halad a törlés, mert meg kell találni a csúcsokat vagy éleket	Lassan hozzáadja vagy eltávolítja a csúcsokat, mert a mátrixot újra kell formázni	Lassan hozzáadja vagy eltávolítja a csúcsokat vagy éleket, mert a mátrixot újra kell formázni

A szomszédsági listák általában előnyösek a ritka grafikonok esetében . Éppen ellenkezőleg, egy szomszédsági mátrix előnyösebb, ha a gráf sűrű, vagyis amikor az élek száma | E | közel van a csúcsok számának négyzetéhez V | 2 , hanem akkor is, ha meg akarjuk tudni, hogyan lehet gyorsan tesztelni egy él létezését két csúcs között.

Kapcsolódó cikkek

• Grafikon bejárása
• Grafikon-orientált adatbázis
• Átírás (számítógép)
• grafikon átírás  (be)

Megjegyzések és hivatkozások

1. Manfred Broy, Martin Wirsing és Claude Pair , „  Az elvont adattípusok modelljének szisztematikus vizsgálata  ”, Elméleti informatika , 1. évf.  33, 1984, P.  139-174
2. Sébastien Veigneau , Az algoritmusok imperatív és funkcionális megközelítései: alkalmazások C és CAML Light alkalmazásban , Springer Science & Business Media, 1999( online olvasás )
3. Kurt Mehlhorn és Stefan Näher, LEDA: Platform a kombinatorikus és geometriai számításhoz , Cambridge University Press,1999, „6. fejezet: Grafikonok és adatstruktúráik”, p.  240–282.
4. Goodrich és Tamassia 2015 , 13.1.2. Szakasz: Műveletek grafikonokon, p.  360
5. Cormen és mtsai. 2002 , p.  514-515.
6. Goodrich és Tamassia 2015 , p.  361-362.
7. Cormen és mtsai. 2002 , p.  515-516.
8. Goodrich és Tamassia 2015 , p.  363.
9. Cormen és mtsai. 2002 , 22.1-7 . Gyakorlat, p.  517.
10. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest és Clifford Stein, Algorithmique , Párizs, Dunod,2002, xxix + 1188  o. ( ISBN  978-2-10-003922-7 , SUDOC  068254024 ) , „22.1. Szakasz: Grafikonok ábrázolása”, p.  514-517.
11. Michael T. Goodrich és Roberto Tamassia, algoritmus tervezés és alkalmazások , Wiley,2015, „13.1. Szakasz: Grafikon terminológia és ábrázolások”, p.  355-364.

Külső linkek

• A Boost Graph Library egy Boost könyvtár
• Networkx , egy grafikonkönyvtár a Pythonban
• GraphMatcher egy java gráf igazító program.

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">