No reason to prefer using an edge list to an adjacency list for a graph structure implementation?
in [Theory]
|
Prev: CFP Applied Computing 2010: submissions until 28 May 2010
Next: "Hewlett Packard’s are made for Printing"
From: Merciadri Luca on 17 May 2010 10:17 -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hi, Consider the following matrices' representations. One is an edge list, the other an adjacency list. == ..-------------------------------------------------------------. | Matrices representations | +------------------------+-----------+------------------------+ | Method | Edge List | Adjacency List | +------------------------+-----------+------------------------+ | vertices | O(n) | O(n) | | edges | O(m) | O(m) | | endVertices | O(1) | O(1) | | areAdjacent | O(m) | O(min(deg(v), deg(w))) | | incidentEdges | O(m) | O(deg(v)) | | replace | O(1) | O(1) | | insertEdge, removeEdge | O(1) | O(1) | | insertVertex | O(1) | O(1) | | removeVertex | O(1) | O(1) | '------------------------+-----------+------------------------' == Why would the edge list _ever_ be preferred to the adjacency list? `m' is evidently #(edges) and `n' #(vertices). If it was preferred, at least under some circumstances, it would mean that m <= min(deg(v), deg(w)) || m <= deg(v) equivalent to m <= min(deg(v), deg(w)). Thanks. - -- Merciadri Luca See http://www.student.montefiore.ulg.ac.be/~merciadri/ - -- - -- Courage doesn't always roar. Sometimes courage is the little voice at the end of the day that says I'll try again tomorrow. (Mary Anne Radmacher) -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Processed by Mailcrypt 3.5.8 <http://mailcrypt.sourceforge.net/> iEYEARECAAYFAkvxT+oACgkQM0LLzLt8MhzZSwCePhJkt+RmpZaRIr2nPzz6qftF maAAoK7M9QY5O1D+4w50cah+tpVAQKSI =aQyi -----END PGP SIGNATURE----- |