Deepak Soundappan

Graphs Graphs are very important data structure.

The graph data structure represents entities (nodes/vertices) and their relationships (edges), and it has many real-life equivalents where connections or networks matter. Common real-world examples include:

Social Networks (e.g., Facebook, LinkedIn): People are nodes, and friendships or connections are edges.
Road Maps or City Navigation: Locations (cities, intersections) are nodes, and roads are edges. Navigation apps use graph algorithms like Dijkstra’s.
Internet/Web: Webpages are nodes, and hyperlinks are edges—forming a massive directed graph.

Sample Code

There are 2 major categories of graph:

Weighted graph: Where the weights of the edges are to be considered. Eg. distance or time taken to travel between 2 nodes. Capacity of a route in a shop floor.
Unweighted graph: Where are no weights in the relationships. Eg. Facebook friends, Twitter followers or Internet web page links

There are 2 main ways of storing graph data:

Adjacency List: Its very useful where the relationships between vertices / nodes are very sparse. It helps storing information more efficiently. Space complexity and iterating all edges takes O(N + E).
Adjacency Graph: It is quite useful in dense data relationships where in almost all the nodes are connected to each other. It is quite easy to store and visualize the data in the form of a 2 dimensional matrix. Space complexity and iterating all edges takes is O(N^2)

The directionality is also critical. There are 2 types with regards to direction:

Unidirectional Graph: A unidirectional graph (also known as a directed graph or digraph) is a graph where edges have a direction—meaning each edge goes from one vertex to another specific vertex (e.g., A → B but not necessarily B → A)
1. Modeling Dependencies: Build systems (like Make, Maven, Gradle): A directed edge A → B means "A must be built before B."
2. Package managers: Represent dependency chains among libraries.
3. Web Crawling / Internet Links: The web graph: Each webpage is a node, and hyperlinks are directed edges from one page to another.
4. Access Control and Authorization. In role-based access control (RBAC) systems, you might model who can delegate rights to whom. Edge A → B might mean "A has granted B a certain permission."
Bi Directional Graph: A bidirectional graph (or undirected graph) is a graph where edges imply a two-way connection between nodes. That is, if there’s an edge between A and B, you can go from A to B and from B to A equally—no directionality. These graphs are used in real-world scenarios where relationships are mutual, symmetric, or reversible.
1. Social Networks - Friendships: If Alice is friends with Bob, Bob is friends with Alice — modeled as undirected edges. Platforms like Facebook often use undirected graphs to model mutual connections.
2. Road Maps and Navigation Systems - Two-way streets: Cities and transportation systems where roads can be traversed in both directions. For routing and pathfinding algorithms (e.g., Dijkstra’s), undirected graphs are often used when roads are bidirectional.

Data Storage methodology:

Connection class for any vertex - Having 2 attributes : Vertex and Weight (For unweighted graphs keep the weight as 1)
Graph class (We will use adjacency list) - Which contain 2 attributes: Is is directed, the dictionary for all the vertices and list of the connections associated

Methodology to insert the edges graph:

insert_edge(self, start, end, weight=1) will be used to insert the edge.

Underlying process,

insert_vertex(start)
insert_vertex(end)
Add the connection of the end vertice to the start vertice if uni-directed
If bi-directional, add the connection of the end_vertice to the start_vertex

Reference code

Page updated

Google Sites

Report abuse