algorithmdata-structuresgraph-theory

Difference between vertices and edges [Graphs, Algorithm and DS]


I've just now started reading an Algorithms book that defined Graphs as follows:

Graphs – which represent relationships between arbitrary pairs of objects. Figure 1.8(b) models a network of roads as a graph, where the vertices are cities and the edges are roads connecting pairs of cities. Graphs are likely the object in question whenever you seek a “network,” “circuit,” “web,” or “relationship.”

Figure 1.8(b) is this: alt text

What confuses me here is the following line:

... where the vertices are cities and the edges are roads connecting pairs of cities ...


Solution

  • Vertices are the dots, edges are the lines. Hence cities and roads.

    I'm not sure what confuses you, but in general graphs are indeed used to model connections between objects.

    If you have a bunch of objects (vertices) that may be "connected" to one another, a Graph would be the high level data structure to maintain it. I'm saying "high level" because in practice you will probably need supporting data structures to maintain a graph in memory/database/file: matrices, lists of links, many-to-many tables etc.

    If the "direction" is not important, like in the case of the plot above (i.e. all roads are bidirectional), you have an "undirected graph". If the connection direction does have an importance (for example if there are unidirectional roads between cities), you'll have a "directed graph", where every edge is actually an "arrow", pointing at a certain direction.

    If you're very new to this, I recommend reading the relevant Wikipedia entry. For some "real" studying, I recommend Cormen et al's Introduction to Algorithms, the book I studied from, which is in my opinion one of the best computer science books ever written.