Algorithm

Graph : Construction

There are many different way to construct a Graph, but one of the most commonly used method would be to construct a Graph using LinkedList (If you are not familiar with Graph, read this page first.)

Let's suppose that we have a graph as shown below and try to construct a data structure for this graph.

Before trying to write any code, I would recommend you to construct a adjacency matrix for the graph. This is not a mandatory, but this matrix will be helpful for clarity and will be helpful if you want to do some mathematical analysis for the graph.

We can think of roughly two different way of implementing this graph as show below.

< Case 1 >

One simple way of constructing the graph is to use an array and linked list as illustrated below.

• Example in C

< Case 2 >

Then you can create a linked list to represent the graph as shown below. In this case, the both nodes (Vertex) and edges are implemented as linkedlist.

Reference :

[1] Graph - Linked Implementation  

[2] C++ Program to Represent Graph Using Linked List