Graph

Graph is a collection of vertices connected to each other through edges. In mathematical notation the graph can be represented in following way:

G = (V, E)

Where G is an ordered pair of a set V of vertices and a set E of edges.

The edges can be either directed or undirected. If a graph has directed edges it can be named directed graph or digraph.

graph_2

Every edge in digraph has origin vertex and destination vertex. In some cases these origin and destination vertices can point to the same vertex. This is called a self-loop.

graph_7

An example of self-loop, is a web site that can be represented as a graph. Then, all pages will be vertices and links are edges. Some pages can have a link to it self which is a self-loop.

The number of edges between two vertices is unlimited and if this number is greater than one the edge is named multi-edge.

graph_8

 

The graph that doesn’t have self-loops and multi-edges is called simple graph.

Another useful property of the edges is weight. For instance, the most common example of a graph is when vertices represent cities and edges represent roads. The roads may have different distance that we can associate with weight.

graph_5

Basing on the weight we can find the shortest path from Berlin to Frankfurt.

It is not necessary that all the vertices are connected in one piece. We can have a graph which consists of two or more unconnected graphs.

graph_6

Or in other words the set of edges E might be empty.

Implementation

What are the maximum numbers of edges in a simple directed and undirected graph? The simple graph, in general, doesn’t have self-loops and multi-edges. Thus, if a graph is directed, the range of possible number of edges is:

0 <= |E| <= |V|(|V|-1)

and if a graph is undirected, the range is following:

0 <= |E| <= |V|(|V|-1) * 1/2

The graph is called sparse if the number of edges is very close to the number of vertices. Otherwise if number of edges is close to the N^2 we can call this graph dense.

Knowing whether the graph is sparse or dense we can choose right implementation. There are two well-known implementations of a graph, the adjacency matrix and adjacency list.

For dense graph we can use adjacency matrix because sparse graph leaves many empty cells. In matrix representation rows and columns represent vertices. Value in the intersection of a row and column represents edge.

graph_am

 

Instead of “X” you can save weight and positive/negative values can act role of direction.

Here is my version of the graph that based on adjacency matrix: https://github.com/alexvolov/algorithms-and-data-structures/blob/master/src/main/java/com/alexvolov/ads/ds/impl/AdjacencyMatrix.java.

If graph is sparse and we want to efficiently use memory then our choice is adjacency list. In this version of the graph we have one list of all vertices and each vertex maintain it’s own list of vertices that it is connected to. You can use associative array to keep vertices as keys and weights as values.

graph_list

Here is my version of the graph that based on adjacency list: https://github.com/alexvolov/algorithms-and-data-structures/blob/master/src/main/java/com/alexvolov/ads/ds/impl/AdjacencyList.java.

Complexity
Adjacency Matrix Adjacency List
Memory O(|V|^2) O(|V|+|E|)
Add edge O(1) O(1)
Remove edge O(1) O(|E|)

Leave a Reply