Edge Lists Visually Explained

Visually Explained Algorithms

The edge list is another way to represent adjacent vertices. Why would you want to create an edge list? Again, to save time. The edge list is much more efficient when trying to figure out the adjacent nodes in a graph. Let’s look at an example of how someone would create an edge list from a directed graph.

The edge list contains a list of edges in alphanumerical order. We start by filling in all the outbound edges from vertex 1. Vertex 1 has one outbound edge to vertex 6, so that edge is stored.

Moving through the graph in alphanumerical order, the next vertex that will be considered is vertex 2. Vertex 2 has two outbound edges: to vertex 1 and to vertex 5. Both of those edges will be recorded into the edge list table.

Vertex 3 has two outbound edges: to vertex 2 and vertex 5.

Vertex 4 has one outbound edge to vertex 6.

Vertex 5 has 4 outbound edges: Edge 5–1, Edge 5–3, Edge 5–4, and Edge 5–6. All the edges are stored into the edge list.

Finally, vertex 6 has 3 outbound edges to vertices 1, 2, and 5. They’re added to the edge list.

The edge list is complete and contains all the directed edges. If the graph was weighted, an additional column can be created next to each edge to contain the weight of that edge. i.e. (1–6 | 12)

If you liked what you read, my book, An Illustrative Introduction to Algorithms, covers this Graph Representation and many more.

 

Leave a Reply