An llista d'adjacència és una estructura de dades utilitzada per representar un gràfic on cada node del gràfic emmagatzema una llista dels seus vèrtexs veïns.

Representació gràfica del gràfic dirigit a la llista d'adjacència

Característiques de la llista d'adjacència:

• La mida de la matriu ve determinada pel nombre de nodes de la xarxa.
• El nombre d'arestes del gràfic es calcula fàcilment.
• La llista d'adjacència és a matriu irregular .

Com crear una llista d'adjacència?

És molt fàcil i senzill construir una llista d'adjacència per a un gràfic, hi ha alguns passos que s'indiquen a continuació que cal seguir:

• Creeu una matriu de llistes enllaçades de mida N , on N és el nombre de vèrtexs del gràfic.
• Creeu una llista enllaçada de vèrtexs adjacents per a cada vèrtex del gràfic.
• Per a cada vora (u, v) al gràfic, afegeix en a la llista enllaçada de en , i afegeix en a la llista enllaçada de en si el gràfic no està orientat, en cas contrari, sumeu en a la llista de en si es dirigeix ​​des de en a en . (En cas de gràfics ponderats, emmagatzemeu el pes juntament amb les connexions).

Aplicacions de la llista d'adjacència:

• algorisme de Dijkstra , Primera recerca d'amplada , i Primera recerca en profunditat utilitzar llistes d'adjacència per representar gràfics.
• Processament d'imatge : Les llistes d'adjacència es poden utilitzar per representar les relacions d'adjacència entre píxels d'una imatge.
• Desenvolupament del joc : Aquestes llistes es poden utilitzar per emmagatzemar informació sobre les connexions entre diferents àrees o nivells que els desenvolupadors del joc utilitzen gràfics per representar mapes o nivells del joc.

Avantatges d'utilitzar una llista d'adjacència:

• Una llista d'adjacència és senzilla i fàcil d'entendre.
• Afegir o eliminar vores d'un gràfic és ràpid i fàcil.

Desavantatges d'utilitzar una llista d'adjacència:

• A les llistes d'adjacència, accedir a les vores pot trigar més que la matriu d'adjacència.
• Requereix més memòria que la matriu d'adjacència per a gràfics densos.

Què més pots llegir?

• Significat i definició de la matriu d'adjacència a DSA
• Afegeix i elimina una vora a la representació de la llista d'adjacència d'un gràfic
• Converteix la matriu d'adjacència a la representació de la llista d'adjacència del gràfic
• Converteix la llista d'adjacència en la representació de matriu d'adjacència d'un gràfic
• Comparació entre la llista d'adjacència i la representació de la matriu d'adjacència del gràfic