Talk:Graph (abstract data type)

This  level-5 vital article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Computer science Top‑importance This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science Top This article has been rated as Top-importance on the project's importance scale. Things you can help WikiProject Computer science with: Here are some tasks awaiting attention: Article requests : Requested articles/Applied arts and sciences/Computer science, computing, and Internet Cleanup : Computer science articles needing attention Computer science articles needing expert attention Copyedit : Computing Expand : Computer science Infobox : Computer science articles without infoboxes Maintain : Timeline of computing 2020–present Photo : Find pictures for the biographies of computer scientists (see List of computer scientists) Computing articles needing images Stubs : Computer science stubs Unreferenced : WikiProject Computer science/Unreferenced BLPs Project-related : Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}} Mathematics Mid‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Mid This article has been rated as Mid-priority on the project's priority scale.

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)Reply

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)Reply

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)Reply

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)Reply

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)Reply

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)Reply

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)Reply

The subject of this article is distinct from the mathematical notion of a graph. Property graphs, or labeled property graphs, are a family of data models used in connection with graph databases. Property graphs now have an ISO standard in the form of GQL (https://en.wikipedia.org/wiki/Graph_Query_Language), but are also distinct from that standard. The article has some issues -- including being slightly out of date w.r.t. GQL and not linking to Neo4j (which originated the data model) or TinkerPop/Gremlin (which popularized it) -- but I would definitely retain it as a separate page. Joshsh (talk) 17:44, 31 July 2024 (UTC)Reply

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)Reply

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)Reply

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)Reply

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)Reply

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)Reply

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)Reply

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)Reply

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)Reply

Planning to merge Property graphs into this page. Weebney (talk) 06:07, 19 July 2024 (UTC)Reply

Oppose proposed merge. That appears to be a topic in graph databases, not in the general-purpose computer representation of graphs. If it should be merged somewhere, it should be merged to graph database, not to here. —David Eppstein (talk) 07:37, 20 July 2024 (UTC)Reply

Oppose proposed merge

Property graphs are a different topic altogether< They are related to graph databases, but are more general than these, as explained in th article. They deserve a separate article Steyncham (talk) 13:11, 5 September 2024 (UTC)Reply