❮❮ PREV NEXT ❯❯

EDGE LIST DATA STRUCTURE

We have had enough theory about Graph. Now, it's time to see, how to implement them.

As the name suggests, in 'Edge List Data Structure', all the edges will be represented as a Linked List.

Let us understand 'Edge List Data Structure' with the below directional Graph example :

Let us look at the below diagram, that says, there are a few cities a, b, c, d, and e represented as vertices.

And the Edges represents the bus names that travels through that edge/road.

So, the bus 13A, travels from city(or vertex) 'a' to 'b'.

Now, let us list out the edge/road through which the Bus travels from one city to other(vertex a to b) .

Now, we will see something, Well! Something out of the box.

As we have seen each edge represents a Bus Name. So, we will take all edges, combine them and put into a linked list.

Sounds Strange?

Just pause! Think for a second!

Each edge represents a bus name. Now, if we want to represent the edges in Algorithms.

Could it not be a Linked List?

So let's construct a Linked List representing the Edges.

Similarly, let us put the Vertices(That represents the cities) in a separate Linked List.

Now, let us establish a relation between Edge Linked List and Vertices Linked List.

As seen in the above diagram :

The first element of the Edge Linked List i.e. Bus number 13A, travels from city/Vertex 'a' to city/Vertex 'b'.

So, we will be having two pointers in the first element of Linked List,

The first pointer will be pointing to 'a' element in Vertices Linked List and the second pointer will be pointing to element 'b'.

Similarly, the second element of the Edge Linked List i.e. Bus number 13A, travels from city/Vertex 'b' to city/Vertex 'a'.

So, we will be having two pointers in the second element of Linked List,

The first pointer will be pointing to 'b' element in Vertices Linked List and the second pointer will be pointing to element 'a'.

And So on.

Running Time of Edge List Data Structure

Edge List Data Structure is easy to construct and quite efficient, except to find the incident edges(Two edges are called incident, if they share a vertex).

To find an Incident edge, the entire Edge Linked List has to be traversed completely.

❮❮ PREV NEXT ❯❯