Graph data structure explained

A graph is a non-linear data structure consisting of a node (vertex) and edge. The nodes are sometimes also referred to as vertices and edges are lines or arcs that connect two nodes in the graph.

Graph terminology

Adjacency

A vertex is said to be adjacent to another vertex if there is an edge connecting them:

Path

It’s a sequence of edges that allows you to go from vertex a to vertex b. In the illustration below, the path between vertex and vertex is marked in red.

Directed Graph

A graph in which there is only one direction between two vertices. An arrow represents the direction.

Undirected Graph

A graph in which we can have two directions between two vertices, it’s represented by a line without an arrow.

Unweighted or weighted Graph

if the edges in your graph have weights then your graph is said to be a weighted graph, if the edges do not have weights, the graph is said to be unweighted. Weight is a numerical value attached to each individual edge. In a weighted graph relationships between nodes have a magnitude and this magnitude is essential to the relationship we’re studying.

Graph representation

Adjacency Matrix

An adjacency matrix is a way of representing a graph as a matrix of booleans. A finite graph can be represented in the form of a square matrix the boolean value of the matrix is indicated if there is a direct path between two vertices.

If the cell at row i and column j have the value 1, it means that the node i and j are adjacent.

• Space complexity: O(n²)
• Time complexity: Check if two nodes are adjacent takes O(1). Getting all adjacent nodes to a given node takes O(n).

Adjacency Linked List

It's a way to represent a graph as an array of linked lists but since I mostly use javascript, I use the built-in Map and Set data structure instead of a linked list.

• Space complexity: O(n+e)
• Time complexity: Check if two nodes are adjacent takes O(n). Getting all adjacent nodes to a given node takes O(1).

Graph Traversal

Like Tree, there is two way to traverse a graph, Breadth-first and Depth-first traversal. To keep this article as short as possible, those two traversals will be tackled in the different articles that will be published soon.

Conclusion

Well, we have learned a lot of things in this one, I hope you enjoy reading this as much as I enjoyed the writing process.