Understanding Graphs
Graphs represent relationships between entities. They consist of vertices (nodes) connected by edges (links).
typescript
interface Graph {
vertices: number;
edges: [number, number][];
}
interface AdjacencyList {
[vertex: number]: number[];
}Graph Representations
Adjacency List
typescript
function createAdjacencyList(edges: [number, number][]): AdjacencyList {
const list: AdjacencyList = {};
for (const [from, to] of edges) {
if (!list[from]) list[from] = [];
list[from].push(to);
// For undirected graphs
if (!list[to]) list[to] = [];
list[to].push(from);
}
return list;
}Adjacency Matrix
typescript
function createAdjacencyMatrix(
vertices: number,
edges: [number, number][]
): number[][] {
const matrix = Array(vertices).fill(0).map(() => Array(vertices).fill(0));
for (const [from, to] of edges) {
matrix[from][to] = 1;
matrix[to][from] = 1; // For undirected
}
return matrix;
}Graph Traversals
Depth-First Search (DFS)
typescript
function dfs(graph: AdjacencyList, start: number, visited = new Set<number>()): number[] {
const result: number[] = [];
function traverse(vertex: number) {
if (visited.has(vertex)) return;
visited.add(vertex);
result.push(vertex);
for (const neighbor of graph[vertex] || []) {
traverse(neighbor);
}
}
traverse(start);
return result;
}Breadth-First Search (BFS)
typescript
function bfs(graph: AdjacencyList, start: number): number[] {
const result: number[] = [];
const visited = new Set<number>();
const queue: number[] = [start];
visited.add(start);
while (queue.length > 0) {
const vertex = queue.shift()!;
result.push(vertex);
for (const neighbor of graph[vertex] || []) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
return result;
}Shortest Path Algorithms
Dijkstra's Algorithm
typescript
function dijkstra(
graph: AdjacencyList,
start: number,
end: number
): number | null {
const distances: Map<number, number> = new Map();
const visited = new Set<number>();
const pq: [number, number][] = [[0, start]]; // [distance, vertex]
// Initialize distances
for (const vertex in graph) {
distances.set(Number(vertex), Infinity);
}
distances.set(start, 0);
while (pq.length > 0) {
pq.sort((a, b) => a[0] - b[0]);
const [dist, current] = pq.shift()!;
if (current === end) return dist;
if (visited.has(current)) continue;
visited.add(current);
for (const neighbor of graph[current] || []) {
const newDist = dist + 1; // Assuming unweighted
if (newDist < (distances.get(neighbor) || Infinity)) {
distances.set(neighbor, newDist);
pq.push([newDist, neighbor]);
}
}
}
return distances.get(end) || null;
}A* Algorithm
typescript
function aStar(
graph: AdjacencyList,
start: number,
end: number,
heuristic: (node: number) => number
): number[] | null {
const openSet: number[] = [start];
const cameFrom: Map<number, number> = new Map();
const gScore: Map<number, number> = new Map([[start, 0]]);
const fScore: Map<number, number> = new Map([[start, heuristic(start)]]);
while (openSet.length > 0) {
// Get node with lowest fScore
openSet.sort((a, b) => (fScore.get(a) || Infinity) - (fScore.get(b) || Infinity));
const current = openSet.shift()!;
if (current === end) {
return reconstructPath(cameFrom, current);
}
for (const neighbor of graph[current] || []) {
const tentativeGScore = (gScore.get(current) || 0) + 1;
if (tentativeGScore < (gScore.get(neighbor) || Infinity)) {
cameFrom.set(neighbor, current);
gScore.set(neighbor, tentativeGScore);
fScore.set(neighbor, tentativeGScore + heuristic(neighbor));
if (!openSet.includes(neighbor)) {
openSet.push(neighbor);
}
}
}
}
return null;
}
function reconstructPath(cameFrom: Map<number, number>, current: number): number[] {
const path = [current];
while (cameFrom.has(current)) {
current = cameFrom.get(current)!;
path.unshift(current);
}
return path;
}Cycle Detection
Detect Cycle in Undirected Graph
typescript
function hasCycle(graph: AdjacencyList): boolean {
const visited = new Set<number>();
function dfs(vertex: number, parent: number | null): boolean {
visited.add(vertex);
for (const neighbor of graph[vertex] || []) {
if (!visited.has(neighbor)) {
if (dfs(neighbor, vertex)) return true;
} else if (neighbor !== parent) {
return true;
}
}
return false;
}
for (const vertex in graph) {
if (!visited.has(Number(vertex))) {
if (dfs(Number(vertex), null)) return true;
}
}
return false;
}Topological Sort
typescript
function topologicalSort(graph: AdjacencyList): number[] {
const inDegree: Map<number, number> = new Map();
const result: number[] = [];
const queue: number[] = [];
// Calculate in-degrees
for (const vertex in graph) {
inDegree.set(Number(vertex), 0);
}
for (const vertex in graph) {
for (const neighbor of graph[vertex] || []) {
inDegree.set(neighbor, (inDegree.get(neighbor) || 0) + 1);
}
}
// Add nodes with zero in-degree to queue
for (const [vertex, degree] of inDegree) {
if (degree === 0) queue.push(vertex);
}
// Process queue
while (queue.length > 0) {
const vertex = queue.shift()!;
result.push(vertex);
for (const neighbor of graph[vertex] || []) {
inDegree.set(neighbor, inDegree.get(neighbor)! - 1);
if (inDegree.get(neighbor) === 0) {
queue.push(neighbor);
}
}
}
return result.length === Object.keys(graph).length ? result : [];
}Common Applications
Social Network Analysis
typescript
function findFriendsOfFriends(
graph: AdjacencyList,
user: number,
depth: number = 2
): Set<number> {
const visited = new Set<number>();
const queue: [number, number][] = [[user, 0]];
while (queue.length > 0) {
const [current, level] = queue.shift()!;
if (level >= depth) continue;
for (const friend of graph[current] || []) {
if (!visited.has(friend)) {
visited.add(friend);
queue.push([friend, level + 1]);
}
}
}
visited.delete(user);
return visited;
}Time Complexity
- BFS/DFS: O(V + E)
- Dijkstra: O((V + E) log V)
- A*: O(b^d) where b is branching factor, d is depth
- Topological Sort: O(V + E)
Conclusion
Graph algorithms solve network problems. Master BFS, DFS, shortest paths, and cycle detection for interviews and real-world applications.
Graph your way to success!