Imagine a social network like Facebook, every user is connected to their friends, who are connected to their friends, and so on.
Or think about Google Maps navigating you through city streets, finding the quickest route from your home to work.
Even Netflix's "Because you watched..." recommendations form a complex web of connections between shows and viewers.
These real-world networks share something in common - they're all powered by graphs.
A graph is one of the most versatile ways to represent relationships in the real world. At its heart, a graph is simply a collection of points (called vertices or nodes) that are connected by lines (called edges).
What makes graphs special is their ability to model any kind of relationship: friendships between people, roads between cities, dependencies between tasks, or connections between concepts.
Think of it like this:
Each vertex (node) is something you want to track - a person, a city, a task, or any entity
Each edge is a relationship or connection between two vertices - a friendship, a road, a requirement
These connections can be one-way (like Twitter follows) or two-way (like Facebook friends)
They can have additional information like weights (like distance between cities) or types (like different kinds of relationships)
Unlike simpler data structures like arrays (which are just lists) or trees (which are hierarchical like a family tree), graphs can capture the rich, interconnected nature of real-world relationships.
They're the backbone of many technologies we use daily, from social media to GPS navigation, from recommendation systems to computer networks.
Graph are great data structures to model real world relationships representing links, graphs ideal cases where you're working with thing that connect to other things.
We can use Graphs to represent:
Friendship or family tree
Represent Networks
Roads from one city to another city.
Facebook uses graph for social network.
Amazon uses it for recommendation engine.
Google maps uses graphs for determining to where you wanna go?
There are many types of graphs, but there are certain characteristics that allow us to describe graphs.
Graphs complexity lies in the fact that there are so many variations of graph, through this section we are going to learn different variation of graph and some of the most important algorithms that are applied to these different variations of graph.
Graphs are really just collection of these nodes.
Node here is pretty much identical to the node inside a binary tree.
you can also think of it as a cycle inside of a linked list.
And a graph can have numerous different cycles. This is just a nature of graphs.
1. Directed Graphs: One way street
Twitter is more directed people can follow me, but i don't automatically follow them.
I can go from A to D, but i cannot go to D => A
These direction can be either both way or one way.
(A) <----> (B)
we can go back and forth in this case
2. Undirected Graphs: Highway between two cities
Facebook has undirected graph in friendship, i am friend with a friend, friend is also connected with me.
This means in undirected graph, you can go back and forth between nodes, in directed graphs you can only go in one direction.
Another way to describe graphs:
Not just the node but also edges can carry information or value.
3. Weighted Graphs
Going on a trip? trying to figure out the most efficient way to visit sites that interest you. Goolge maps will use wighted graph to decide what is the shortest path for you to get there and these sort of graphs are used a lot in calculating optimal paths.
When traversing from one node to another node you have to pay the cost. i.e cumulative cost of all the weighted edges that we traverse through when we go from one node to another
we can take numerous path, we want to figure out which takes the lowest cost.
Weighted graphs exist in both directed graph variations as well as undirected graphs
The only complexity that adds is that we have to consider the weight cost of traversing across an edge.
Every undirected graph can be easily converted into directed graph, very edge should be seen as two directional
4. Unweighted Graphs:
Another variation of graph that can exist with this format is one where we have different nodes that are connected to other nodes.
But the entirety of all the nodes might not be connected as one structure.
5. Cyclic Graphs:
When you have a vertices connected in a circular fashion, it's called cycle. Really common in weighted graphs, such as google maps, because there is a way to get back.
6. Acyclic Graphs:
Where you cannot go in circular fashion.
7. Directed Acyclic Graph -> DAG
A graph that goes in 1 direction.
Graph are build on the top of other data structures. DAG uses tree and linked list.
Another variation of graph that can exist with this format is one where we have different nodes that are connected to other nodes.
But the entirety of all the nodes might not be connected as one structure.
A binary tree are directed graphs.
8. Disconnected graph
One component with nodes A-B-C in a line
Another component with nodes D-E-F in a triangle
An isolated node G
Real-world examples of disconnected graphs:
Social networks with isolated groups who don't know each other
Computer networks before the internet connected them
Islands or isolated communities before transportation links
Separate friend groups that don't share any common friends
All binary trees are graphs, but all graphs are not binary tree.
Another data structure that actually represents graph is 2D array.
The reason for this is if you visualize this 2D array as a grid and you visualize every single element as a vertex.
what you will see is that every single grid cell is a vertex that is connected by pattern of edges, which represent the traversal pattern that we can make from one grid cell to another.
Now, this shows:
Each node is labeled with its exact 2D array position [row,col]
The graph maintains the same grid layout as the 2D array
The edges show how you can move:
Horizontal edges = moving left/right in the array
Vertical edges = moving up/down in the array
How to Start Building Graph?
(2) ---------(0)
/ \
/ \
(1) ------(3)
Three ways we can build a graph:
Edge list: Simply shows the connection i.e which node is connected to which?
0 and 2 as first item => 0 is connected to 2 and 2 is connected to 0
[2,3] => 2 <=>3 (2 and 3 is connected)
[2,1] => 2 <=>1 (2 and 1 is connected)
[1,3] => 1 <=>3 (1 and 3 is connected)
When it comes to performance, it get's little complicated as there are many types of graphs.
Graphs are really useful when it comes to relationship, simply indispensable because some data just needs to be in the graph form, no other way around it.
Graphs allows us to perform operations such as finding shortest path or traversing a graph.
When it comes to graph, they can get complicated scaling, you need a big resources and engineering power to make sure that you build graph data structure that scale well.
Fortunately, we never have to implement our own graphs in production, or atleast for 99% of times.
Tools like Neo4j, popular db are there for building really fast graphs database. Most of the time we use these tools to build complex structures to contain our data.
Common Pitfalls to Avoid
Over-normalization
Breaking down vertices too granularly
Creating unnecessary relationships
Poor Memory Management
Not considering space complexity
Inefficient data structures
Inadequate Indexing
Missing crucial lookup patterns
Over-indexing unnecessary properties
Conclusion
Graphs are versatile data structures that can model complex relationships efficiently. Success in implementing graph-based solutions depends on understanding the trade-offs between different representations and algorithms, and choosing the appropriate tools and technologies for your specific use case.
Imagine a social network like Facebook, every user is connected to their friends, who are connected to their friends, and so on.
Or think about Google Maps navigating you through city streets, finding the quickest route from your home to work.
Even Netflix's "Because you watched..." recommendations form a complex web of connections between shows and viewers.
These real-world networks share something in common - they're all powered by graphs.
A graph is one of the most versatile ways to represent relationships in the real world. At its heart, a graph is simply a collection of points (called vertices or nodes) that are connected by lines (called edges).
Think of it like this:
Unlike simpler data structures like arrays (which are just lists) or trees (which are hierarchical like a family tree), graphs can capture the rich, interconnected nature of real-world relationships.
They're the backbone of many technologies we use daily, from social media to GPS navigation, from recommendation systems to computer networks.
Graph are great data structures to model real world relationships representing links, graphs ideal cases where you're working with thing that connect to other things.
We can use Graphs to represent:
There are many types of graphs, but there are certain characteristics that allow us to describe graphs.
Graphs complexity lies in the fact that there are so many variations of graph, through this section we are going to learn different variation of graph and some of the most important algorithms that are applied to these different variations of graph.
Graphs are really just collection of these nodes.
Node here is pretty much identical to the node inside a binary tree.
node{ value: something connection: [left or right] || edge :new Node() }The main differences between tree vs graph is in graphs.
(D) | | (A) ----- (X) -----(Y) / \ / \ (B) (C)Here there are actually four connected nodes in this singular node (x)
A cycle is essentially where these nodes are connected in a way that form this type of circular connection.
Where you might be able to traverse from one node back to itself if these nodes are connected to each other in this circular like structure.
(D) / | / | (A) ----- (X) -----(Y) / \ / \ (B) (C)you can also think of it as a cycle inside of a linked list.
And a graph can have numerous different cycles. This is just a nature of graphs.
1. Directed Graphs: One way street
I can go from A to D, but i cannot go to D => A
These direction can be either both way or one way.
we can go back and forth in this case
2. Undirected Graphs: Highway between two cities
Another way to describe graphs:
3. Weighted Graphs
Going on a trip? trying to figure out the most efficient way to visit sites that interest you. Goolge maps will use wighted graph to decide what is the shortest path for you to get there and these sort of graphs are used a lot in calculating optimal paths.
When traversing from one node to another node you have to pay the cost. i.e cumulative cost of all the weighted edges that we traverse through when we go from one node to another
we can take numerous path, we want to figure out which takes the lowest cost.
Weighted graphs exist in both directed graph variations as well as undirected graphs
The only complexity that adds is that we have to consider the weight cost of traversing across an edge.
4. Unweighted Graphs:
Another variation of graph that can exist with this format is one where we have different nodes that are connected to other nodes.
But the entirety of all the nodes might not be connected as one structure.
5. Cyclic Graphs:
When you have a vertices connected in a circular fashion, it's called cycle. Really common in weighted graphs, such as google maps, because there is a way to get back.
6. Acyclic Graphs:
Where you cannot go in circular fashion.
7. Directed Acyclic Graph -> DAG
A graph that goes in 1 direction.
Another variation of graph that can exist with this format is one where we have different nodes that are connected to other nodes.
But the entirety of all the nodes might not be connected as one structure.
8. Disconnected graph
Real-world examples of disconnected graphs:
Another data structure that actually represents graph is 2D array.
The reason for this is if you visualize this 2D array as a grid and you visualize every single element as a vertex.
what you will see is that every single grid cell is a vertex that is connected by pattern of edges, which represent the traversal pattern that we can make from one grid cell to another.
Now, this shows:
How to Start Building Graph?
(2) ---------(0) / \ / \ (1) ------(3)Three ways we can build a graph:
0 and 2 as first item => 0 is connected to 2 and 2 is connected to 0
[2,3] => 2 <=>3 (2 and 3 is connected) [2,1] => 2 <=>1 (2 and 1 is connected) [1,3] => 1 <=>3 (1 and 3 is connected)class Graphs{ constructor(){ this.vertices = [] this.totalVertex = 0 } addVertex(node){ this.vertices[node] = [] this.totalVertex ++ } addEdges(node1, node2){ this.vertices[node1].push(node2) this.vertices[node2].push(node1) } }myGraph.addVertex('0'); myGraph.addVertex('1'); myGraph.addVertex('2'); myGraph.addVertex('3'); myGraph.addVertex('4'); myGraph.addVertex('5'); myGraph.addVertex('6');myGraph.addEdge('3', '1'); myGraph.addEdge('3', '4'); myGraph.addEdge('4', '2'); myGraph.addEdge('4', '5'); myGraph.addEdge('1', '2'); myGraph.addEdge('1', '0'); myGraph.addEdge('0', '2'); myGraph.addEdge('6', '5');Pros and Cons of Graph:
When it comes to performance, it get's little complicated as there are many types of graphs.
When it comes to graph, they can get complicated scaling, you need a big resources and engineering power to make sure that you build graph data structure that scale well.
Fortunately, we never have to implement our own graphs in production, or atleast for 99% of times.
Tools like Neo4j, popular db are there for building really fast graphs database. Most of the time we use these tools to build complex structures to contain our data.
Common Pitfalls to Avoid
Conclusion
Graphs are versatile data structures that can model complex relationships efficiently. Success in implementing graph-based solutions depends on understanding the trade-offs between different representations and algorithms, and choosing the appropriate tools and technologies for your specific use case.