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.
Top comments (0)