Graph theory is a key area of study in Data Structures and Algorithms (DSA), and it deals
with graphs, which are mathematical structures used to model pairwise relations between objects.
Graphs are foundational for representing networks like social networks, computer networks,
transportation systems, etc.
What is a Graph?
A graph is a collection of nodes (vertices) and edges that connect pairs of nodes. It is
represented as G = (V, E), where:
V is a set of vertices (nodes).
E is a set of edges (connections between the nodes).
Types of Graphs
1. Directed Graph (Di-Graph): In a directed graph, edges have a direction, meaning that
each edge goes from one vertex to another (denoted as u → v).
2. Undirected Graph: In an undirected graph, edges do not have a direction (i.e., they go
both ways).
3. Weighted Graph: A graph where edges have weights or costs associated with them.
These weights represent the "cost" to traverse an edge.
4. Unweighted Graph: A graph where all edges have the same weight or cost, typically
represented as 1 for each edge.
5. Cyclic vs. Acyclic Graphs:
o Cyclic: Contains at least one cycle (a path that starts and ends at the same vertex).
o Acyclic: Does not contain any cycles.
A Directed Acyclic Graph (DAG) is particularly useful for tasks like
scheduling (e.g., project tasks or dependencies).
6. Connected vs. Disconnected Graph:
o Connected Graph: A graph where there is a path between every pair of vertices.
o Disconnected Graph: A graph where some vertices are not reachable from
others.
Graph Representation
There are mainly two ways to represent graphs in computer memory:
1. Adjacency Matrix:
o A 2D array where each cell [i][j] represents the presence (or absence) of an edge
between vertex i and vertex j.
Example (undirected graph):
yaml
CopyEdit
Adjacency Matrix:
0 1 1 0
1 0 1 0
1 1 0 1
0 0 1 0
2. Adjacency List:
o A collection of lists or arrays, where each list corresponds to a vertex and stores
all its adjacent vertices.
Example:
rust
CopyEdit
Vertex 0 -> 1, 2
Vertex 1 -> 0, 2
Vertex 2 -> 0, 1, 3
Vertex 3 -> 2
Graph Traversal Algorithms
1. Depth-First Search (DFS):
o Starts at a source vertex and explores as far as possible along each branch before
backtracking.
o DFS can be implemented using recursion or using a stack.
Time Complexity: O(V + E).
2. Breadth-First Search (BFS):
o Starts at a source vertex and explores all neighboring vertices level by level
before moving to the next level.
Time Complexity: O(V + E).
Graph Algorithms
1. Dijkstra’s Algorithm:
o Finds the shortest path from a source node to all other nodes in a weighted graph
(with non-negative weights).
o Time complexity: O(V^2) for simple implementation.
2. Bellman-Ford Algorithm:
o Finds the shortest paths in graphs, but it can handle graphs with negative weights
(but not negative weight cycles).
o Time complexity: O(VE).
3. Floyd-Warshall Algorithm:
o Finds the shortest paths between all pairs of vertices.
o Time complexity: O(V^3).
4. Kruskal’s Algorithm:
o A greedy algorithm for finding the Minimum Spanning Tree (MST) of a graph.
o Time complexity: O(E log E), where E is the number of edges.
5. Prim’s Algorithm:
o Another greedy algorithm for finding the MST. It starts from an arbitrary vertex
and grows the MST by adding edges with the smallest weights.
o Time complexity: O(E log V) with a priority queue.
6. Topological Sort:
o A linear ordering of vertices in a directed acyclic graph (DAG) where for every
directed edge u → v, vertex u comes before vertex v in the ordering.
Union-Find (Disjoint Set Union - DSU)
A data structure used to efficiently handle the merging and finding of disjoint sets,
commonly used in algorithms like Kruskal’s.
Find: Determines the representative or root of the set containing a particular element.
Union: Merges two sets into one.
Applications of Graph Theory
1. Social Networks: Representing connections between users (friends, followers, etc.).
2. Computer Networks: Modeling the topology of routers, servers, and internet
connections.
3. Search Engines: Link analysis (e.g., PageRank) to rank web pages.
4. Scheduling Problems: Topological sorting of tasks or jobs.
5. Route Planning: Shortest path algorithms (e.g., GPS navigation)
