Graphs · learnDataStructures

Graphs — the essential toolbox

What is a graph?

A graph is a set of vertices (a.k.a. nodes) connected by edges. You can model networks (maps, prerequisites, social links) with graphs.

Directed (digraph): edges have an arrow u → v. Undirected: edges are two-way u — v.
Weighted: each edge has a non-negative weight (we allow integers). Unweighted: all weights are 1.
Adjacent: u and v share an edge. Degree of v: number of incident edges (for directed: in-degree / out-degree).
Path: sequence of vertices where consecutive vertices share an edge. Cycle: path that starts and ends at the same vertex (length ≥ 1).
Connected (undirected): there is a path between every pair. For directed, we distinguish strongly vs weakly connected.

Representations

Adjacency list: for each vertex, store its neighbors (and weights). Space O(n + m). Great for sparse graphs.
Adjacency matrix: n × n table where entry [i][j] is 1 (or weight) if edge i→j exists; else 0/∞. Space O(n²). Great for dense graphs and instant hasEdge(i,j).

Traversals

BFS (breadth-first search): explores in layers using a queue. On unweighted graphs, BFS gives shortest path length (in edges) from a start.
DFS (depth-first search): explores along a branch using a stack/recursion. Useful for cycle detection, topological sort, and component discovery.

Other core tasks

Topological sort (DAG only): a linear order where every directed edge goes left→right. We show Kahn’s algorithm (BFS on in-degrees).
Cycle detection:
- Undirected: DFS avoiding the parent — if you see an already-visited neighbor ≠ parent ⇒ cycle.
- Directed: DFS with a 3-color/recursion stack — encountering a gray (in-stack) vertex ⇒ back edge ⇒ cycle.
Bipartite check (undirected): 2-coloring using BFS/DFS; if a conflict occurs, it’s not bipartite.
Connected components: group vertices reachable from each other (via BFS/DFS) or via Union-Find (Disjoint Set Union).

Complexities (adjacency list)

Operation	Time	Space	Notes
BFS / DFS (all vertices)	O(n + m)	O(n)	Visit each vertex & edge once
Topological sort (Kahn)	O(n + m)	O(n)	Maintains queue of zero in-degree
Cycle detection (undirected)	O(n + m)	O(n)	DFS with parent
Cycle detection (directed)	O(n + m)	O(n)	DFS colors/stack
Bipartite check	O(n + m)	O(n)	BFS/DFS 2-color
Connected components	O(n + m)	O(n)	Using BFS/DFS or DSU
Adjacency matrix build	O(n²) fill + O(m) set	O(n²)	We animate the fill

Need shortest paths (Dijkstra, A*, Bellman-Ford, BFS on unweighted)? See dijkstra.html (your lab).

Implementations & Notes

Implementations by Language (choose a variant)

Python

Adjacency list + BFS/DFS/topo/cycles/bipartite/components

from collections import deque, defaultdict

class Graph:
    def __init__(self, n, directed=False):
        self.n = n
        self.dir = directed
        self.adj = [[] for _ in range(n)]   # (v, w) pairs if weighted

    def add_edge(self, u, v, w=1):
        self.adj[u].append((v, w))
        if not self.dir:
            self.adj[v].append((u, w))

    def bfs(self, s):
        vis=[False]*self.n; q=deque([s]); vis[s]=True; order=[]
        while q:
            u=q.popleft(); order.append(u)
            for v,_ in self.adj[u]:
                if not vis[v]: vis[v]=True; q.append(v)
        return order

    def dfs(self, s):
        vis=[False]*self.n; order=[]
        def go(u):
            vis[u]=True; order.append(u)
            for v,_ in self.adj[u]:
                if not vis[v]: go(v)
        go(s); return order

    def topo_kahn(self):
        indeg=[0]*self.n
        for u in range(self.n):
            for v,_ in self.adj[u]: indeg[v]+=1
        from collections import deque
        q=deque([i for i in range(self.n) if indeg[i]==0])
        out=[]
        while q:
            u=q.popleft(); out.append(u)
            for v,_ in self.adj[u]:
                indeg[v]-=1
                if indeg[v]==0: q.append(v)
        return out if len(out)==self.n else None  # None if cycle

    def has_cycle_undirected(self):
        vis=[False]*self.n
        def go(u,p):
            vis[u]=True
            for v,_ in self.adj[u]:
                if not vis[v]:
                    if go(v,u): return True
                elif v!=p:
                    return True
            return False
        for i in range(self.n):
            if not vis[i] and go(i,-1): return True
        return False

    def has_cycle_directed(self):
        color=[0]*self.n # 0=white,1=gray,2=black
        def go(u):
            color[u]=1
            for v,_ in self.adj[u]:
                if color[v]==1: return True
                if color[v]==0 and go(v): return True
            color[u]=2; return False
        return any(color[i]==0 and go(i) for i in range(self.n))

    def bipartite(self):
        color=[-1]*self.n
        from collections import deque
        for s in range(self.n):
            if color[s]!=-1: continue
            color[s]=0; q=deque([s])
            while q:
                u=q.popleft()
                for v,_ in self.adj[u]:
                    if color[v]==-1:
                        color[v]=color[u]^1; q.append(v)
                    elif color[v]==color[u]:
                        return False, None
        return True, color

    def components(self):
        vis=[False]*self.n; comps=[]
        for s in range(self.n):
            if vis[s]: continue
            stack=[s]; vis[s]=True; cur=[]
            while stack:
                u=stack.pop(); cur.append(u)
                for v,_ in self.adj[u]:
                    if not vis[v]: vis[v]=True; stack.append(v)
            comps.append(cur)
        return comps

Union-Find (Disjoint Set Union) for components

class DSU:
    def __init__(self, n):
        self.p=list(range(n)); self.r=[0]*n
    def find(self,x):
        if self.p[x]!=x: self.p[x]=self.find(self.p[x])
        return self.p[x]
    def union(self,a,b):
        ra,rb=self.find(a),self.find(b)
        if ra==rb: return False
        if self.r[ra]<self.r[rb]: ra,rb=rb,ra
        self.p[rb]=ra
        if self.r[ra]==self.r[rb]: self.r[ra]+=1
        return True

Library note: networkx equivalents

# import networkx as nx
# G = nx.Graph() or nx.DiGraph()
# G.add_edge(u, v, weight=w)
# list(nx.bfs_tree(G, s))
# list(nx.dfs_preorder_nodes(G, s))
# list(nx.topological_sort(DAG))
# nx.is_directed_acyclic_graph(G)
# nx.is_bipartite(G)
# list(nx.connected_components(G))

Java

Adjacency list + BFS/DFS/topo/cycles/bipartite/components

import java.util.*;
class Graph {
  final int n; final boolean dir;
  final ArrayList<int[]>[] adj; // (v,w)
  @SuppressWarnings("unchecked")
  Graph(int n, boolean dir){
    this.n=n; this.dir=dir;
    adj=new ArrayList[n];
    for(int i=0;i<n;i++) adj[i]=new ArrayList<>();
  }
  void addEdge(int u,int v,int w){
    adj[u].add(new int[]{v,w});
    if(!dir) adj[v].add(new int[]{u,w});
  }
  List<Integer> bfs(int s){
    boolean[] vis=new boolean[n];
    ArrayDeque<Integer> q=new ArrayDeque<>();
    List<Integer> out=new ArrayList<>();
    vis[s]=true; q.add(s);
    while(!q.isEmpty()){
      int u=q.poll(); out.add(u);
      for(int[] e:adj[u]){ int v=e[0]; if(!vis[v]){ vis[v]=true; q.add(v); } }
    }
    return out;
  }
  List<Integer> dfs(int s){
    boolean[] vis=new boolean[n];
    List<Integer> out=new ArrayList<>();
    Deque<Integer> st=new ArrayDeque<>();
    st.push(s);
    while(!st.isEmpty()){
      int u=st.pop();
      if(vis[u]) continue; vis[u]=true; out.add(u);
      List<int[]> nbrs=adj[u];
      for(int i=nbrs.size()-1;i>=0;i--){ int v=nbrs.get(i)[0]; if(!vis[v]) st.push(v); }
    }
    return out;
  }
  List<Integer> topoKahn(){
    int[] indeg=new int[n];
    for(int u=0;u<n;u++) for(int[] e:adj[u]) indeg[e[0]]++;
    ArrayDeque<Integer> q=new ArrayDeque<>();
    for(int i=0;i<n;i++) if(indeg[i]==0) q.add(i);
    List<Integer> out=new ArrayList<>();
    while(!q.isEmpty()){
      int u=q.poll(); out.add(u);
      for(int[] e:adj[u]){ int v=e[0]; if(--indeg[v]==0) q.add(v); }
    }
    return out.size()==n?out:null;
  }
  boolean hasCycleUndirected(){
    boolean[] vis=new boolean[n];
    for(int s=0;s<n;s++){
      if(vis[s]) continue;
      ArrayDeque<int[]> st=new ArrayDeque<>(); // (u,parent)
      st.push(new int[]{s,-1});
      while(!st.isEmpty()){
        int[] t=st.pop(); int u=t[0],p=t[1];
        if(vis[u]) continue; vis[u]=true;
        for(int[] e:adj[u]){
          int v=e[0];
          if(!vis[v]) st.push(new int[]{v,u});
          else if(v!=p) return true;
        }
      }
    }
    return false;
  }
  boolean hasCycleDirected(){
    int[] color=new int[n]; // 0 W,1 G,2 B
    for(int s=0;s<n;s++){
      if(color[s]!=0) continue;
      ArrayDeque<int[]> st=new ArrayDeque<>(); // (u,itIndex)
      st.push(new int[]{s,0});
      ArrayList<Iterator<int[]>> its=new ArrayList<>(Collections.nCopies(n,null));
      while(!st.isEmpty()){
        int[] t=st.peek(); int u=t[0]; int itIdx=t[1];
        if(color[u]==0){ color[u]=1; its.set(u, adj[u].iterator()); }
        Iterator<int[]> it=its.get(u);
        if(it.hasNext()){
          int v=it.next()[0];
          if(color[v]==1) return true;
          if(color[v]==0) st.push(new int[]{v,0});
        }else{
          color[u]=2; st.pop();
        }
      }
    }
    return false;
  }
  boolean bipartite(){
    int[] col=new int[n];
    Arrays.fill(col,-1);
    for(int s=0;s<n;s++){
      if(col[s]!=-1) continue;
      ArrayDeque<Integer> q=new ArrayDeque<>();
      col[s]=0; q.add(s);
      while(!q.isEmpty()){
        int u=q.poll();
        for(int[] e:adj[u]){
          int v=e[0];
          if(col[v]==-1){ col[v]=col[u]^1; q.add(v); }
          else if(col[v]==col[u]) return false;
        }
      }
    }
    return true;
  }
  List<List<Integer>> components(){
    boolean[] vis=new boolean[n];
    List<List<Integer>> comps=new ArrayList<>();
    for(int s=0;s<n;s++){
      if(vis[s]) continue;
      ArrayDeque<Integer> st=new ArrayDeque<>();
      st.push(s); vis[s]=true; List<Integer> cur=new ArrayList<>();
      while(!st.isEmpty()){
        int u=st.pop(); cur.add(u);
        for(int[] e:adj[u]){ int v=e[0]; if(!vis[v]){ vis[v]=true; st.push(v); } }
      }
      comps.add(cur);
    }
    return comps;
  }
}

Union-Find (DSU)

class DSU{
  int[] p, r;
  DSU(int n){ p=new int[n]; r=new int[n]; for(int i=0;i<n;i++) p[i]=i; }
  int find(int x){ return p[x]==x?x:(p[x]=find(p[x])); }
  boolean union(int a,int b){
    int ra=find(a), rb=find(b); if(ra==rb) return false;
    if(r[ra]<r[rb]){ int t=ra; ra=rb; rb=t; }
    p[rb]=ra; if(r[ra]==r[rb]) r[ra]++; return true;
  }
}

Library note: Java Collections

// Queue: ArrayDeque<Integer>
// Priority queue (not needed here, but for SSSP): new PriorityQueue<int[]>(Comparator.comparingInt(a->a[1]));

C++

Adjacency list + BFS/DFS/topo/cycles/bipartite/components

#include <bits/stdc++.h>
using namespace std;
struct Graph{
  int n; bool dir; vector<vector<pair<int,int>>> adj;
  Graph(int n,bool dir):n(n),dir(dir),adj(n){}
  void add_edge(int u,int v,int w=1){
    adj[u].push_back({v,w});
    if(!dir) adj[v].push_back({u,w});
  }
  vector<int> bfs(int s){
    vector<int> vis(n); queue<int> q; vector<int> out;
    vis[s]=1; q.push(s);
    while(!q.empty()){
      int u=q.front(); q.pop(); out.push_back(u);
      for(auto [v,w]:adj[u]) if(!vis[v]){ vis[v]=1; q.push(v); }
    }
    return out;
  }
  vector<int> dfs(int s){
    vector<int> vis(n); vector<int> out; stack<int> st; st.push(s);
    while(!st.empty()){
      int u=st.top(); st.pop();
      if(vis[u]) continue; vis[u]=1; out.push_back(u);
      for(int i=(int)adj[u].size()-1;i>=0;--i){ int v=adj[u][i].first; if(!vis[v]) st.push(v); }
    }
    return out;
  }
  vector<int> topo_kahn(){
    vector<int> indeg(n); for(int u=0;u<n;u++) for(auto [v,w]:adj[u]) indeg[v]++;
    queue<int> q; for(int i=0;i<n;i++) if(indeg[i]==0) q.push(i);
    vector<int> out;
    while(!q.empty()){
      int u=q.front(); q.pop(); out.push_back(u);
      for(auto [v,w]:adj[u]) if(--indeg[v]==0) q.push(v);
    }
    if((int)out.size()!=n) return {};
    return out;
  }
  bool has_cycle_undirected(){
    vector<int> vis(n);
    for(int s=0;s<n;s++){
      if(vis[s]) continue;
      stack<pair<int,int>> st; st.push({s,-1});
      while(!st.empty()){
        auto [u,p]=st.top(); st.pop();
        if(vis[u]) continue; vis[u]=1;
        for(auto [v,w]:adj[u]){
          if(!vis[v]) st.push({v,u});
          else if(v!=p) return true;
        }
      }
    }
    return false;
  }
  bool has_cycle_directed(){
    vector<int> color(n); // 0W,1G,2B
    function<bool(int)> go = [&](int u){
      color[u]=1;
      for(auto [v,w]:adj[u]){
        if(color[v]==1) return true;
        if(color[v]==0 && go(v)) return true;
      }
      color[u]=2; return false;
    };
    for(int i=0;i<n;i++) if(color[i]==0 && go(i)) return true;
    return false;
  }
  bool bipartite(){
    vector<int> col(n,-1);
    for(int s=0;s<n;s++){
      if(col[s]!=-1) continue;
      queue<int> q; col[s]=0; q.push(s);
      while(!q.empty()){
        int u=q.front(); q.pop();
        for(auto [v,w]:adj[u]){
          if(col[v]==-1){ col[v]=col[u]^1; q.push(v); }
          else if(col[v]==col[u]) return false;
        }
      }
    }
    return true;
  }
  vector<vector<int>> components(){
    vector<int> vis(n); vector<vector<int>> comps;
    for(int s=0;s<n;s++){
      if(vis[s]) continue;
      vector<int> cur; stack<int> st; st.push(s); vis[s]=1;
      while(!st.empty()){
        int u=st.top(); st.pop(); cur.push_back(u);
        for(auto [v,w]:adj[u]) if(!vis[v]){ vis[v]=1; st.push(v); }
      }
      comps.push_back(cur);
    }
    return comps;
  }
};

Union-Find (DSU)

struct DSU{
  vector<int> p,r;
  DSU(int n):p(n),r(n,0){ iota(p.begin(),p.end(),0); }
  int find(int x){ return p[x]==x?x:p[x]=find(p[x]); }
  bool unite(int a,int b){
    a=find(a); b=find(b); if(a==b) return false;
    if(r[a]<r[b]) swap(a,b);
    p[b]=a; if(r[a]==r[b]) r[a]++; return true;
  }
};

Library note: STL

// queue<int>, stack<int>, vector<vector<pair<int,int>>>, etc.
// For shortest paths use priority_queue (see your dijkstra.html lab).

Concept Checks

Define vertex, edge, degree, path, cycle, directed vs. undirected, weighted vs. unweighted.
Explain when to prefer adjacency list vs adjacency matrix.
Run BFS and DFS from a start vertex; explain why BFS visits by layers and DFS goes deep.
Perform Kahn’s topological sort and show why it detects cycles when the result is shorter than n.
Detect cycles in undirected (parent check) and directed (gray/back edge) graphs.
Show a 2-coloring or give a counterexample for bipartite check.
Compute connected components by DFS and by Union-Find; discuss complexity.

learnDataStructures

Graphs — the essential toolbox

What is a graph?

Representations

Traversals

Other core tasks

Complexities (adjacency list)

Graphs — reference & pseudocode

Pseudocode (BFS, DFS, topo, cycles, bipartite, components, DSU)

Interactive Graph Simulator

Implementations & Notes

Implementations by Language (choose a variant)

Python

Java

C++

Concept Checks