Seznam hran - Edge list

An seznam hran je datová struktura slouží k reprezentaci a graf jako seznam jeho hrany. (Nevážený) okraj je definován jeho počátečním a koncovým vrcholem, takže každý okraj může být reprezentován dvěma čísly.[1] Celý seznam hran může být reprezentován jako dvousloupcová matice.[2][3] Seznam hran lze považovat za variaci na seznam sousedství který je reprezentován jako délka pole seznamů.[4] Jelikož každá hrana obsahuje pouze dvě nebo tři čísla, celkový prostor pro seznam hran je .[3]

Reference

  1. ^ Munagala, Kameshwar; Ranade, Abhiram (1999). „Složitost I / O grafových algoritmů“. Sborník z desátého výročního sympózia ACM-SIAM o diskrétních algoritmech. SODA '99. Philadelphia, PA, USA: Společnost pro průmyslovou a aplikovanou matematiku: 687–694. ISBN  9780898714340.
  2. ^ "ruční stránky igraph R". igraph.org. Citováno 2019-10-16.
  3. ^ A b „Reprezentující grafy“. Khan Academy. Citováno 2019-10-16.
  4. ^ Kolaczyk, Eric D. (2009-04-20). Statistická analýza síťových dat: metody a modely. New York. str.22. ISBN  9780387881461. OCLC  405547055.