Graph Theory in Computer Science- Fundamentals

What Graph Theory Actually Is

Graph theory is the study of graphs — mathematical structures made of vertices (nodes) connected by edges (lines). That's it. No fancy definitions needed.

If you've ever used Google Maps, scrolled through social media, or searched for a route online, you've used graph theory without knowing it. The algorithms behind these tools are built on graph structures.

This isn't a theoretical exercise. Graphs power:

Navigation systems
Social network analysis
Network infrastructure design
Recommendation engines
Dependency resolution in package managers

Core Terminology You Need to Know

Before diving deeper, memorize these terms:

Vertex (Node) — A point in the graph. A city on a map, a user in a social network.
Edge — A connection between two vertices. A road between cities, a friendship link between users.
Degree — Number of edges connected to a vertex. High-degree nodes are hubs.
Path — A sequence of vertices where each adjacent pair is connected by an edge.
Cycle — A path that starts and ends at the same vertex.
Weight — A value assigned to an edge, often representing cost, distance, or time.

Types of Graphs

Directed vs. Undirected

In an undirected graph, edges have no direction. A connection from A to B works both ways. Think of a two-way street.

In a directed graph (digraph), edges point in a specific direction. A follows B doesn't mean B follows A. Think one-way streets or Twitter followers.

Weighted vs. Unweighted

Weighted graphs assign values to edges. A road between cities might have a weight of 150 miles. Unweighted graphs treat all edges equally.

Cyclic vs. Acyclic

A cycle exists when you can start at a vertex, follow edges, and return to the starting point. Graphs without cycles are acyclic. Trees are a common example of acyclic graphs.

Complete, Dense, and Sparse Graphs

A complete graph has edges between every pair of vertices. Dense graphs have many edges relative to the total possible. Sparse graphs have few edges — most real-world networks are sparse.

How to Represent Graphs in Code

Two main approaches exist. Pick based on your use case.

Adjacency Matrix

A 2D array where matrix[i][j] shows the connection between vertex i and vertex j.

``` int[][] graph = new int[5][5]; graph[0][1] = 1; // Edge between 0 and 1 graph[1][0] = 1; // And back ```

Pros: O(1) edge lookup. Cons: O(V²) space, even for sparse graphs.

Adjacency List

Each vertex stores a list of its neighbors.

``` List[] graph = new ArrayList[5]; graph[0] = Arrays.asList(1, 2, 3); ```

Pros: Space-efficient for sparse graphs. Cons: Slower edge existence checks.

Graph Representation Comparison

Aspect	Adjacency Matrix	Adjacency List
Space Complexity	O(V²)	O(V + E)
Check if edge exists	O(1)	O(V)
Find neighbors	O(V)	O(degree)
Best for	Dense graphs, frequent edge checks	Sparse graphs, iterating neighbors

Most real applications use adjacency lists. They're faster to iterate and use less memory for sparse data.

Essential Graph Algorithms

Breadth-First Search (BFS)

BFS explores vertices by distance from the source. It uses a queue and visits all neighbors before moving deeper.

Use it for:

Shortest path in unweighted graphs
Level-order traversal
Finding connected components

Depth-First Search (DFS)

DFS goes as deep as possible down a path before backtracking. Uses a stack (or recursion).

Use it for:

Detecting cycles
Topological sorting
Finding connected components
Maze solving

Dijkstra's Algorithm

Finds the shortest path between nodes in a weighted graph. Works only with non-negative weights.

Time complexity: O((V + E) log V) with a priority queue.

Bellman-Ford Algorithm

Handles negative weights. Can detect negative cycles. Slower than Dijkstra at O(VE).

Topological Sort

Orders vertices so every edge points from earlier to later. Only works on DAGs (Directed Acyclic Graphs).

Used for build systems, task scheduling, and course prerequisites.

Practical Applications

Social Networks

Facebook's friend suggestions use graph algorithms. When you see "People You May Know," the system is analyzing your graph — friends of friends, mutual connections, common groups.

Google Maps and Navigation

Every route calculation is a shortest path problem. Roads are edges, intersections are vertices, distances are weights. Dijkstra's algorithm (or its variants like A*) runs behind the scenes.

Package Managers

npm, pip, and cargo resolve dependencies using graph algorithms. They detect circular dependencies and install packages in the correct order.

Network Routing

Internet routers use graph theory to find optimal paths for data packets. Algorithms like OSPF and BGP model the internet as a weighted graph.

Recommendation Systems

Netflix recommendations, Amazon products, Spotify playlists — all use graph-based approaches to find relationships between users and content.

Getting Started: Build Your First Graph

Here's a minimal implementation in Python:

``` class Graph: def __init__(self): self.adj_list = {} def add_vertex(self, v): if v not in self.adj_list: self.adj_list[v] = [] def add_edge(self, v1, v2, directed=False): self.add_vertex(v1) self.add_vertex(v2) self.adj_list[v1].append(v2) if not directed: self.adj_list[v2].append(v1) def bfs(self, start): visited = set() queue = [start] while queue: vertex = queue.pop(0) if vertex not in visited: print(vertex) visited.add(vertex) queue.extend(self.adj_list[vertex]) def dfs(self, start, visited=None): if visited is None: visited = set() visited.add(start) print(start) for neighbor in self.adj_list[start]: if neighbor not in visited: self.dfs(neighbor, visited) # Usage g = Graph() g.add_edge('A', 'B') g.add_edge('A', 'C') g.add_edge('B', 'D') g.add_edge('C', 'D') print("BFS:") g.bfs('A') print("DFS:") g.dfs('A') ```

What to Practice

Implement both matrix and list representations
Code BFS and DFS from scratch
Solve LeetCode graph problems (start with #200, #133, #207)
Build a simple recommendation engine using graph traversal

Common Mistakes to Avoid

Forgetting to track visited nodes — leads to infinite loops on cyclic graphs
Choosing the wrong representation — matrix for sparse graphs wastes memory
Ignoring directed vs. undirected — always clarify the graph type before coding
Using Dijkstra on graphs with negative weights — it breaks. Use Bellman-Ford instead

When to Use What

Problem Type	Algorithm
Unweighted shortest path	BFS
Weighted shortest path (positive)	Dijkstra
Weighted shortest path (negative)	Bellman-Ford
Cycle detection	DFS with visited set
Dependency resolution	Topological Sort (Kahn's or DFS-based)
Connectivity check	BFS/DFS from arbitrary node

The Bottom Line

Graph theory isn't optional knowledge in computer science. It's foundational. Trees, linked lists, social networks, road systems — all graphs. Once you internalize the terminology and core algorithms, problems that seemed complex become straightforward.

Start coding. Practice traversal. The concepts stick faster when you implement them.