Loading...
Master graph theory concepts, representations, algorithms, and real-world applications. Learn about different types of graphs and their use cases in computer science.
A graph is a non-linear data structure consisting of vertices (nodes) connected by edges. Unlike trees, graphs can have cycles and multiple paths between nodes.
A graph G = (V, E) where:
Edges have no direction. If vertex A is connected to B, then B is also connected to A.
Examples: Facebook friendships, road networks
Edges have direction. Connection from A to B doesn't imply B to A.
Examples: Twitter followers, web page links
All edges are equal. Only connection matters, not the "cost" of traversal.
Examples: Social networks, family trees
Edges have weights representing cost, distance, time, or other metrics.
Examples: GPS navigation, network latency
Contains at least one cycle
No cycles present (DAG if directed)
Every vertex connected to every other
2D array where element [i][j] indicates if there's an edge between vertex i and j.
A B C D E A [ 0 1 1 0 0 ] B [ 1 0 1 1 0 ] C [ 1 1 0 1 1 ] D [ 0 1 1 0 1 ] E [ 0 0 1 1 0 ]
Pros: O(1) edge lookup, simple implementation
Cons: O(V²) space, inefficient for sparse graphs
Array of lists where each list contains neighbors of a vertex.
A: [B, C] B: [A, C, D] C: [A, B, D, E] D: [B, C, E] E: [C, D]
Pros: O(V + E) space, efficient for sparse graphs
Cons: O(V) edge lookup in worst case
List of all edges, each represented as a pair (or triple for weighted graphs).
Edges: (A, B) (A, C) (B, C) (B, D) (C, D) (C, E) (D, E)
Pros: O(E) space, simple for edge operations
Cons: O(E) to find neighbors
class Graph {
constructor() {
this.adjacencyList = new Map();
}
addVertex(vertex) {
if (!this.adjacencyList.has(vertex)) {
this.adjacencyList.set(vertex, []);
}
}
addEdge(vertex1, vertex2) {
this.adjacencyList.get(vertex1).push(vertex2);
this.adjacencyList.get(vertex2).push(vertex1); // For undirected
}
removeEdge(vertex1, vertex2) {
this.adjacencyList.set(
vertex1,
this.adjacencyList.get(vertex1).filter(v => v !== vertex2)
);
this.adjacencyList.set(
vertex2,
this.adjacencyList.get(vertex2).filter(v => v !== vertex1)
);
}
removeVertex(vertex) {
while (this.adjacencyList.get(vertex).length) {
const adjacentVertex = this.adjacencyList.get(vertex).pop();
this.removeEdge(vertex, adjacentVertex);
}
this.adjacencyList.delete(vertex);
}
}Explores neighbors level by level, visiting all vertices at distance k before visiting vertices at distance k+1.
function BFS(graph, start) {
const visited = new Set();
const queue = [start];
const result = [];
visited.add(start);
while (queue.length > 0) {
const vertex = queue.shift();
result.push(vertex);
for (let neighbor of graph[vertex]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
return result;
}Time Complexity: O(V + E)
Space Complexity: O(V)
Use Cases: Shortest path (unweighted), level-order traversal
Explores as far as possible along each branch before backtracking. Goes deep before going wide.
function DFS(graph, start, visited = new Set()) {
visited.add(start);
console.log(start);
for (let neighbor of graph[start]) {
if (!visited.has(neighbor)) {
DFS(graph, neighbor, visited);
}
}
}
// Iterative version using stack
function DFSIterative(graph, start) {
const visited = new Set();
const stack = [start];
const result = [];
while (stack.length > 0) {
const vertex = stack.pop();
if (!visited.has(vertex)) {
visited.add(vertex);
result.push(vertex);
for (let neighbor of graph[vertex]) {
if (!visited.has(neighbor)) {
stack.push(neighbor);
}
}
}
}
return result;
}Time Complexity: O(V + E)
Space Complexity: O(V)
Use Cases: Cycle detection, topological sorting, pathfinding
Finds shortest path from source to all vertices in weighted graphs with non-negative weights.
Time: O((V + E) log V) with priority queue
Space: O(V)
Use: GPS navigation, network routing
Handles negative weights and detects negative cycles. Slower but more versatile than Dijkstra's.
Time: O(VE)
Space: O(V)
Use: Currency arbitrage, network optimization
Finds shortest paths between all pairs of vertices. Uses dynamic programming approach.
Time: O(V³)
Space: O(V²)
Use: All-pairs shortest path, transitive closure
Finds MST by sorting edges and adding smallest edges that don't create cycles.
Time: O(E log E)
Space: O(V)
Uses: Union-Find data structure
Builds MST by starting from a vertex and adding minimum weight edges to unvisited vertices.
Time: O(E log V) with priority queue
Space: O(V)
Better for: Dense graphs
Linear ordering of vertices in DAG such that for every directed edge (u,v), u comes before v.
Time: O(V + E)
Use: Task scheduling, dependency resolution
Model relationships between users, friend recommendations, community detection.
GPS navigation, route optimization, traffic management systems.
Internet routing, network topology, bandwidth optimization.
Search engines use graphs to model web page relationships and links.
Collaborative filtering, content recommendations, user behavior analysis.
Pathfinding in games, AI decision trees, game state representation.