DSA 11# Graph 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 illustration

Graph terminology

Adjacency

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

illustrate two adjacent vertices

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.

Show a path between two vertices

Directed Graph

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

illustrate a direct graph

Undirected Graph

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

illustrate an undirect graph

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.

weighted graph

unweighted graph

Graph representation

There is two way to represent a graph in software, adjacency matrix, and adjacency linked list.

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.

Adjacency matrix representation

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.

Adjacency Linked list representation

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

The Nothing 🔺