Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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 ...

like image 228
Srikanth Avatar asked Dec 03 '22 07:12

Srikanth


2 Answers

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.

like image 67
Roee Adler Avatar answered Jan 13 '23 11:01

Roee Adler


Vertices are the nodes of the graph. Edges are the arcs that connect pairs of nodes.

like image 44
cedrou Avatar answered Jan 13 '23 10:01

cedrou