Talk:Graph (abstract data type)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated Start-class, Top-importance)
WikiProject icon 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.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 Top  This article has been rated as Top-importance on the project's importance scale.
 
WikiProject Mathematics (Rated Start-class, Mid-priority)
WikiProject Mathematics
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.
Mathematics rating:
Start Class
Mid Priority
 Field: Discrete mathematics

What's the point of this page? It is the same idea of graph as in mathematics.

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)

Need citations for time complexity table[edit]

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?[edit]

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[edit]

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?[edit]

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)