Graph data structure explained
Tags: datastructure, graph, interview, algorithms
Published: 2022-12-06 12:41:14

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:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/v6r4cftfydk0ajd0hl8i.png)

### 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.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/e1gs751dln7uwjg8s85f.png)

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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/abe0wsxmnhvf1wjnnnoi.png)

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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ypoxr06hrlkuyjfqr541.png)

### 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.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/abzxssd8eifmnmw68kgl.png)


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4yn6hz7i2wc6vb2n42q2.png)

## 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.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/kx4jdfx3cpeqau3ldki5.png)

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.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5bxid9a6e7c2evijxqvr.png)

- 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.