Graph
What is a Graph?
A graph G = (V, E) consists of a set of vertices (nodes) V and a set of edges E connecting pairs of vertices. Graphs model real-world relationships: social networks, road maps, web links, dependencies, and more.
| Type | Description | Example |
|---|---|---|
| Undirected | Edges have no direction (A-B = B-A) | Facebook friendships |
| Directed (Digraph) | Edges have direction (A→B ≠B→A) | Twitter follows, web links |
| Weighted | Edges have costs/weights | Road distances, network latency |
| Cyclic / Acyclic | Contains / doesn't contain cycles | DAG for task scheduling |
Graph Representations
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
class Graph {
int V;
vector<vector<int>> adj;
public:
Graph(int v) : V(v), adj(v) {}
void addEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u); // undirected
}
// BFS — O(V + E)
vector<int> bfs(int src) {
vector<bool> visited(V, false);
vector<int> order;
queue<int> q;
visited[src] = true;
q.push(src);
while (!q.empty()) {
int node = q.front(); q.pop();
order.push_back(node);
for (int nb : adj[node]) {
if (!visited[nb]) { visited[nb] = true; q.push(nb); }
}
}
return order;
}
// DFS — O(V + E)
void dfsHelper(int node, vector<bool>& visited, vector<int>& order) {
visited[node] = true;
order.push_back(node);
for (int nb : adj[node])
if (!visited[nb]) dfsHelper(nb, visited, order);
}
vector<int> dfs(int src) {
vector<bool> visited(V, false);
vector<int> order;
dfsHelper(src, visited, order);
return order;
}
};
int main() {
Graph g(6);
g.addEdge(0,1); g.addEdge(0,2); g.addEdge(1,3);
g.addEdge(2,4); g.addEdge(3,5);
auto bfsOrder = g.bfs(0);
cout << "BFS: ";
for (int x : bfsOrder) cout << x << " ";
cout << endl; // 0 1 2 3 4 5
auto dfsOrder = g.dfs(0);
cout << "DFS: ";
for (int x : dfsOrder) cout << x << " ";
cout << endl; // 0 1 3 5 2 4
return 0;
}import java.util.*;
public class Graph {
int V;
List<List<Integer>> adj;
Graph(int v) {
V = v;
adj = new ArrayList<>();
for (int i = 0; i < v; i++) adj.add(new ArrayList<>());
}
void addEdge(int u, int v) {
adj.get(u).add(v);
adj.get(v).add(u);
}
List<Integer> bfs(int src) {
boolean[] visited = new boolean[V];
List<Integer> order = new ArrayList<>();
Queue<Integer> q = new LinkedList<>();
visited[src] = true; q.offer(src);
while (!q.isEmpty()) {
int node = q.poll(); order.add(node);
for (int nb : adj.get(node))
if (!visited[nb]) { visited[nb] = true; q.offer(nb); }
}
return order;
}
void dfsHelper(int node, boolean[] visited, List<Integer> order) {
visited[node] = true; order.add(node);
for (int nb : adj.get(node))
if (!visited[nb]) dfsHelper(nb, visited, order);
}
List<Integer> dfs(int src) {
boolean[] visited = new boolean[V];
List<Integer> order = new ArrayList<>();
dfsHelper(src, visited, order);
return order;
}
public static void main(String[] args) {
Graph g = new Graph(6);
g.addEdge(0,1); g.addEdge(0,2); g.addEdge(1,3);
g.addEdge(2,4); g.addEdge(3,5);
System.out.println("BFS: " + g.bfs(0)); // [0, 1, 2, 3, 4, 5]
System.out.println("DFS: " + g.dfs(0)); // [0, 1, 3, 5, 2, 4]
}
}from collections import defaultdict, deque
class Graph:
def __init__(self):
self.adj = defaultdict(list)
def add_edge(self, u, v):
self.adj[u].append(v)
self.adj[v].append(u) # undirected
def bfs(self, src):
visited = {src}
queue = deque([src])
order = []
while queue:
node = queue.popleft()
order.append(node)
for nb in self.adj[node]:
if nb not in visited:
visited.add(nb)
queue.append(nb)
return order
def dfs(self, src, visited=None, order=None):
if visited is None: visited = set()
if order is None: order = []
visited.add(src)
order.append(src)
for nb in self.adj[src]:
if nb not in visited:
self.dfs(nb, visited, order)
return order
def has_cycle(self):
"""Detect cycle in undirected graph using DFS"""
visited = set()
def dfs_cycle(node, parent):
visited.add(node)
for nb in self.adj[node]:
if nb not in visited:
if dfs_cycle(nb, node): return True
elif nb != parent:
return True # back edge = cycle
return False
for node in self.adj:
if node not in visited:
if dfs_cycle(node, -1): return True
return False
g = Graph()
for u, v in [(0,1),(0,2),(1,3),(2,4),(3,5)]:
g.add_edge(u, v)
print("BFS:", g.bfs(0)) # [0, 1, 2, 3, 4, 5]
print("DFS:", g.dfs(0)) # [0, 1, 3, 5, 2, 4]
print("Has cycle:", g.has_cycle()) # Falseclass Graph {
constructor() { this.adj = new Map(); }
addEdge(u, v) {
if (!this.adj.has(u)) this.adj.set(u, []);
if (!this.adj.has(v)) this.adj.set(v, []);
this.adj.get(u).push(v);
this.adj.get(v).push(u);
}
bfs(src) {
const visited = new Set([src]);
const queue = [src], order = [];
while (queue.length) {
const node = queue.shift();
order.push(node);
for (const nb of (this.adj.get(node) || [])) {
if (!visited.has(nb)) { visited.add(nb); queue.push(nb); }
}
}
return order;
}
dfs(src, visited = new Set(), order = []) {
visited.add(src);
order.push(src);
for (const nb of (this.adj.get(src) || [])) {
if (!visited.has(nb)) this.dfs(nb, visited, order);
}
return order;
}
// Shortest path (unweighted) using BFS
shortestPath(src, dest) {
const dist = new Map([[src, 0]]);
const queue = [src];
while (queue.length) {
const node = queue.shift();
if (node === dest) return dist.get(dest);
for (const nb of (this.adj.get(node) || [])) {
if (!dist.has(nb)) {
dist.set(nb, dist.get(node) + 1);
queue.push(nb);
}
}
}
return -1; // not reachable
}
}
const g = new Graph();
[[0,1],[0,2],[1,3],[2,4],[3,5]].forEach(([u,v]) => g.addEdge(u,v));
console.log("BFS:", g.bfs(0)); // [0, 1, 2, 3, 4, 5]
console.log("DFS:", g.dfs(0)); // [0, 1, 3, 5, 2, 4]
console.log("Shortest 0→5:", g.shortestPath(0, 5)); // 3