Graphs – Report
1. Introduction
A graph is a non-linear data structure consisting of nodes (or vertices) and edges (connections
between the nodes). Graphs are used to model relationships, such as networks, social connections,
or paths between cities. They are widely used in many fields like computer science, operations
research, and social networks.
2. Basic Terminology
• Vertex (Node): A fundamental unit in a graph, representing an entity.
• Edge: A connection between two vertices.
• Adjacent: Two vertices are adjacent if they are connected by an edge.
• Degree: The number of edges connected to a vertex.
• Path: A sequence of vertices connected by edges.
• Cycle: A path where the first and last vertices are the same.
• Directed vs Undirected Graphs:
o Directed: Edges have a direction (arrows from one vertex to another).
o Undirected: Edges do not have a direction (no arrows, just a connection between
two vertices).
3. Types of Graphs
Type Description
Simple Graph No loops or multiple edges.
Multigraph Allows multiple edges between the same pair of vertices.
Weighted Graph Edges have weights or costs associated with them.
Complete Graph Every pair of distinct vertices is connected by an edge.
Vertices can be divided into two disjoint sets such that no two vertices
Bipartite Graph
within the same set are adjacent.
Cyclic Graph Contains at least one cycle.
Acyclic Graph Does not contain any cycles.
Directed Acyclic Graph
Directed graph with no cycles.
(DAG)
4. Representations of Graphs
• Adjacency Matrix: A 2D array A[][] where A[i][j] is 1 (or the weight) if there is an edge
between vertex i and vertex j, and 0 otherwise.
o Space Complexity: O(V²)
o Efficient for dense graphs.
• Adjacency List: An array of lists where each list represents the neighbors of a vertex.
o Space Complexity: O(V + E)
o Efficient for sparse graphs.
• Edge List: A list of all edges in the graph, where each edge is represented as a pair of
vertices.
5. Graph Traversal Algorithms
Algorithm Description
Depth-First Search
Explores as far as possible along a branch before backtracking.
(DFS)
Breadth-First Search Explores all neighbors at the present depth level before moving on to nodes
(BFS) at the next depth level.
DFS (Pseudocode):
python
CopyEdit
def DFS(graph, node, visited):
if node not in visited:
visited.add(node)
for neighbor in graph[node]:
DFS(graph, neighbor, visited)
BFS (Pseudocode):
python
CopyEdit
from collections import deque
def BFS(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
vertex = queue.popleft()
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
6. Shortest Path Algorithms
• Dijkstra’s Algorithm: Used to find the shortest path in a graph with non-negative edge
weights.
• Bellman-Ford Algorithm: Can handle negative edge weights, but slower than Dijkstra's.
• Floyd-Warshall Algorithm: A dynamic programming algorithm to find shortest paths
between all pairs of vertices.
7. Time and Space Complexity
Algorithm Time Complexity Space Complexity
DFS O(V + E) O(V)
BFS O(V + E) O(V)
Dijkstra (with priority queue) O((V + E) log V) O(V + E)
Bellman-Ford O(VE) O(V)
Floyd-Warshall O(V³) O(V²)
8. Advantages
• Modeling real-world problems: Graphs represent networks (e.g., social, transportation,
and communication networks).
• Efficient for sparse and large datasets: Graph algorithms scale well for large and sparse
graphs.
• Versatile structure: Can be used to represent many kinds of data and relationships.
9. Disadvantages
• Complexity: Graph algorithms can be complex and require significant computation time for
large graphs.
• Memory consumption: Dense graphs, particularly with adjacency matrices, require
significant space.
• Algorithmic challenges: Some graph problems are NP-complete (e.g., the traveling
salesman problem).
10. Applications
• Social Networks: Representing connections between users.
• Web Crawling: Navigating the structure of the web.
• Recommendation Systems: Modeling relationships between items or users.
• Routing Algorithms: GPS systems for finding shortest paths.
• Network Flow Problems: Used in telecommunications, transport, and logistics.
11. Real-World Analogy
Imagine a city map with locations (vertices) connected by roads (edges). Finding the shortest path
between two locations is a graph problem that can be solved using algorithms like Dijkstra's.
