Edge list explained

An edge list is a data structure used to represent a graph as a list of its edges. An (unweighted) edge is defined by its start and end vertex, so each edge may be represented by two numbers.[1] The entire edge list may be represented as a two-column matrix.[2] [3] An edge list may be considered a variation on an adjacency list which is represented as a length

|V|

array of lists.[4] Since each edge contains just two or three numbers, the total space for an edge list is

\Theta(|E|)

.

References

  1. Munagala. Kameshwar. Ranade. Abhiram. 1999. I/O-complexity of Graph Algorithms. Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA '99. Philadelphia, PA, USA. Society for Industrial and Applied Mathematics. 687–694. 9780898714340.
  2. Web site: igraph R manual pages. igraph.org. 2019-10-16.
  3. Web site: Representing graphs. Khan Academy. en. 2019-10-16.
  4. Book: Statistical analysis of network data : methods and models. limited. Kolaczyk, Eric D.. 9780387881461. New York. 22. 405547055. 2009-04-20.

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Edge list".

Except where otherwise indicated, Everything.Explained.Today is © Copyright 2009-2024, A B Cryer, All Rights Reserved. Cookie policy.