Talk:Graph (abstract data type)

What's the point?

What's the point of this page? It is the same idea of graph as in mathematics. — Preceding unsigned comment added by Tyir (talk • contribs) 21:29, 27 March 2004 (UTC)

It seems to be a summary of different ways of representing a graph on a computer.

The title should perhaps be "Graph representation" or something like that?

--P0nc 18:56, 18 April 2006 (UTC)

It's about graphs as a data structure in CS. However, the section for that in Graph theory sounds complete enough to me. Should they be merged?

i think not. BUT! rename it to something like *applications* of graph theory in CS... and make it as root to access all ADT's on wiki (for they are all graphs;). like given those constrains thing we have is tree, this one is special case of tree aka linked list, that one is forest - hash ... i'm gona do it one day 84.16.123.194 (talk) 11:32, 7 January 2008 (UTC)

As someone who stumbled on this article searching for just an overview of graphs as a data structure, I liked the article, particularly the 'representation' section. I think the article is fine except for the last four lines, which make no sense (as a result of being copied from somewhere else?) Roshangeorge (talk) 12:38, 30 January 2009 (UTC)

I think the page should stay. A graph is an important data structure in Computer Science. If anything the article should be expanded to include the details of how values can be stored for each vertex or edge. 69.233.0.248 (talk) 09:43, 27 March 2009 (UTC)

How is this different from GIS databases that use vector & connector data types to represent networks and polygons, etc.? —Preceding unsigned comment added by 174.115.239.21 (talk) 17:39, 28 October 2009 (UTC)

Another opinion that it's should be it's own article. The math concept and the computer science implementation are very distinct topics. Jason Quinn (talk) 03:43, 28 October 2021 (UTC)

Need citations for time complexity table

Where are these time complexity bounds coming from?? I see that this table was introduced in June 13, 2011, and that the figures in the table have changed over time. Does anybody have a reference for this information? Klortho (talk) 03:23, 20 November 2011 (UTC)

Where have all the links gone?

There used to be a lot of useful links at the foot of this article. The ones that remain are not as useful as the ones that were removed, and seem a bit random. —Preceding unsigned comment added by 87.113.232.148 (talk) 07:41, 4 November 2010 (UTC)

A topic identical to some of the former external links is already covered by internal links in the main article body. Readers should be directed away from Wikipedia by external links only when they significantly expand the subject beyond Wikipedia's own content. A long list of links to various implementations is not appropriate for Wikipedia. See the guideline for external links for more information. ✤ JonHarder ^talk 12:53, 7 November 2010 (UTC)

Complexity

Hi there, I think there is an improving fact missing: so using a sparse matrix will offer a fast access to the nodes for reading and writing, also the advantage of finding adjacent vertexes stays preserved. Just my 2 cent. — Preceding unsigned comment added by 178.25.211.175 (talk) 16:21, 8 July 2012 (UTC)

Adjacency list time complexity?

I don't think the adjacency list is correct about the time complexity:

Query: are vertices u, v adjacent? (Assuming that the storage positions for u, v are known) O(|V|)

If we store edges in a hash-set (e.g., std::unordered_map<Edge>), we can look up the existence of any potential edge in O(1). That's assuming the data is stored on the graph object itself, but even if we insist on store it in the vertex, like it says,

and every vertex stores a list of adjacent vertices.

…if we say the "list" is a hash-set, it's still O(1). Similarly, such a data structure should allow remove edge to be O(1). Storage is still O(|V| + |E|).

Of course, the Big-O cheat sheet contradicts this, but it seems like if we simply select the correct data structure, we can achieve these complexities.

—Deathanatos (talk) 08:03, 17 July 2014 (UTC)

Storing all the edges in a hash table is a different data structure than an adjacency list. But your second variation, storing the neighbors of each vertex in a hash table, can be interpreted as a variant of the adjacency list and as you say achieves constant time adjacency tests. —David Eppstein (talk) 15:42, 17 July 2014 (UTC)

Move discussion in progress

There is a move discussion in progress on Talk:Associative array which affects this page. Please participate on that page and not in this talk page section. Thank you. —RMCD bot 00:32, 27 January 2022 (UTC)

"Graph (data structure" listed at Redirects for discussion

The redirect Graph (data structure has been listed at redirects for discussion to determine whether its use and function meets the redirect guidelines. Readers of this page are welcome to comment on this redirect at Wikipedia:Redirects for discussion/Log/2024 February 3 § Graph (data structure until a consensus is reached. Utopes _{(talk / cont)} 20:42, 3 February 2024 (UTC)