Graph Basics and Theory

1. Basics of Graphs

1.1 What is a Graph?

A graph is a non-linear data structure consisting of:

• A set of nodes (vertices).

• A set of edges connecting pairs of vertices.

Formally, a graph G is defined as:

G = (V, E)
Where:

• V is the set of vertices.

• E is the set of edges.

Graphs are used to model relationships or connections between objects (like social networks, maps, and recommendation systems).

1.2 Types of Graphs

1.2.1 Directed vs Undirected Graph

• Directed Graph (Digraph): Edges have a direction (u → v).

• Undirected Graph: Edges are bidirectional (u ↔ v).

1.2.2 Weighted vs Unweighted Graph

• Weighted: Edges have weights/costs (e.g., distance, time).

• Unweighted: All edges have equal cost or no weights.

1.2.3 Cyclic vs Acyclic Graph

• Cyclic: Contains at least one cycle.

• Acyclic: No cycles.

1.2.4 Connected vs Disconnected Graph

• Connected (Undirected): Every pair of nodes has a path.

• Disconnected: Some nodes are isolated.

1.2.5 Special Graphs

• Tree: Connected, acyclic, undirected graph with n vertices and n-1 edges.

• DAG (Directed Acyclic Graph): Directed graph with no cycles.

• Complete Graph: Every vertex is connected to every other vertex.

• Bipartite Graph: Vertices can be divided into 2 disjoint sets with edges only between sets.

1.3 Degree of a Vertex

• In-degree: Number of incoming edges.

• Out-degree: Number of outgoing edges.

• Degree (undirected): Number of edges incident to the vertex.

Example:

0 → 1 → 2
↑       |
└-------┘

• In-degree of 0 = 1

• Out-degree of 0 = 1

1.4 Connected Components

• A connected component in an undirected graph is a group of nodes such that any node is reachable from any other node in that group.

• In directed graphs, a strongly connected component (SCC) is a group where every node is reachable from every other node.

1.5 Graph Representation

1.5.1 Adjacency Matrix

int[][] adj = new int[V][V];
adj[u][v] = 1; // Edge from u to v
adj[v][u] = 1; // If undirected

• Space: O(V²)

• Edge check: O(1)

• Best for dense graphs

1.5.2 Adjacency List (ArrayList of Lists)

List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
adj.get(u).add(v); // Directed
adj.get(v).add(u); // If undirected

• Space: O(V + E)

• Efficient for sparse graphs

1.5.3 Adjacency List (Map-Based)

Map<Integer, List<Integer>> graph = new HashMap<>();
graph.putIfAbsent(u, new ArrayList<>());
graph.get(u).add(v);

• Useful when vertex names are strings or dynamic

• Supports large graphs

1.5.4 Weighted Graph (List of Pairs)

class Pair {
    int node, weight;
    Pair(int n, int w) { node = n; weight = w; }
}
List<List<Pair>> adj = new ArrayList<>();

1.5.5 Edge List

List<int[]> edges = new ArrayList<>();
edges.add(new int[]{u, v});
edges.add(new int[]{u, v, weight}); // weighted

• Useful for Kruskal’s algorithm

Representation Comparison

2. Graph Traversals

2.1 Breadth-First Search (BFS)

Intuition:

• Explore level by level.

• Use a queue.

• Good for shortest paths in unweighted graphs.

Java Code:

public void bfs(int start, List<List<Integer>> adj, boolean[] visited) {
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.print(node + " ");

        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.offer(neighbor);
            }
        }
    }
}

Dry Run:

Graph:

0: [1, 3]
1: [2]
3: [4]
4: [5]
5: [2]

Start = 0
Queue: [0]
Visited: [T, F, F, F, F, F]

Traversal:

0 → queue: [1,3]
1 → queue: [3,2]
3 → queue: [2,4]
2 → queue: [4]
4 → queue: [5]
5 → queue: []

Output: 0 1 3 2 4 5

Time & Space:

• Time: O(V + E)

• Space: O(V)

2.2 Depth-First Search (DFS)

Intuition:

• Explore a path as deep as possible, then backtrack.

• Use recursion or a stack.

Java Code (Recursive):

public void dfs(int node, List<List<Integer>> adj, boolean[] visited) {
    visited[node] = true;
    System.out.print(node + " ");

    for (int neighbor : adj.get(node)) {
        if (!visited[neighbor]) {
            dfs(neighbor, adj, visited);
        }
    }
}

Java Code (Iterative using Stack):

public void dfsIterative(int start, List<List<Integer>> adj, boolean[] visited) {
    Stack<Integer> stack = new Stack<>();
    stack.push(start);

    while (!stack.isEmpty()) {
        int node = stack.pop();

        if (!visited[node]) {
            visited[node] = true;
            System.out.print(node + " ");
        }

        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                stack.push(neighbor);
            }
        }
    }
}

Dry Run (Same graph):

Call: dfs(0)

dfs(0) → 0
dfs(1) → 1
dfs(2) → 2
dfs(3) → 3
dfs(4) → 4
dfs(5) → 5

Output: 0 1 2 3 4 5

Time & Space:

• Time: O(V + E)

• Space: O(V) for visited + call stack

Summary