Metode de reprezentare Listele vecinilor

Pentru fiecare nod i , cu i{1,2,…,n}, formăm lista vecinilor lui i. Aceasta cuprinde toate nodurile care sunt extremităţi ale muchiilor ce trec prin nodul i.

Avem pentru graful considerat :

  • X = { 1,2,3,4,5,6,7 } → multimea vârfurilor (nodurilor)
  • U= { u1,u2,u3,u4,u5 }→ multimea muchiilor (arcelor)
  • Muchiile sunt : u1 = (1,2) ; u2 = (2,3) ; u3 = (3,4) ; u4 = (2,4) ; u5 = (5,6) ;
  • d(1) = 1 ; d(2) = 3 ; d(3) = 2 ; d(4) = 2 ; d(5) = 1 ; d(6) = 1 ; d(7) = 0 ;
  • vârful 7 este vârf izolat ; vâfurile 5 şi 6 sunt vârfuri terminale .

Pe fiecare linie i din listele vecinilor conţine indicii coloanelor pe care se găsesc valori de 1 în linia i a matricei de adiacenţă.