Graphs

Definition

• A Graph G = (V, E) is a non-linear data structure of vertices (nodes) connected by edges — more general than a tree (graphs can have cycles, multiple paths, disconnected components; trees cannot)

Types of Graphs

• Directed (Digraph) vs Undirected — edges have direction or not
• Weighted vs Unweighted — edges carry a cost/value or not
• Cyclic vs Acyclic (DAG — Directed Acyclic Graph, used in scheduling/dependency resolution)
• Connected vs Disconnected

Representations

Traversal Algorithms (core exam topic)

• BFS (Breadth-First Search) — uses a Queue; explores level by level; finds shortest path in unweighted graphs; O(V+E)
• DFS (Depth-First Search) — uses a Stack (explicit or via recursion); explores as deep as possible before backtracking; O(V+E)

Key Graph Algorithms (frequently tested)

• Dijkstra's Algorithm — shortest path from a single source, non-negative weights only, Greedy approach, O((V+E) log V) with a priority queue
• Kruskal's / Prim's Algorithm — Minimum Spanning Tree (MST), Greedy approach
• Topological Sort — linear ordering of vertices in a DAG, used for task scheduling/dependency resolution

Exam Angle

Always pair BFS→Queue and DFS→Stack in your answer — a very common quick-fact MCQ. Dijkstra's algorithm requiring non-negative weights (fails with negative edges, unlike Bellman-Ford) is a frequently tested distinction.

📌 Sample & Repeated FPSC Questions (2016–2026)

📝 Kruskal's Algorithm — Full MST Trace

2019, Paper I, Q6(c) (5 marks) — Consider the following graph. Find the sequence of edges added to the minimum spanning tree using Kruskal's algorithm.

Edge list (weighted graph on vertices {a,b,c,d,e,f,g}): a-b=5, a-c=3, b-d=6, b-e=2, c-d=5, c-f=6, d-e=6, d-f=6, d-g=6, e-g=5, f-g=4.

Kruskal's sorts all edges ascending and greedily adds an edge only if it does not create a cycle (checked via union-find/disjoint-set), stopping once n−1 = 6 edges are chosen for 7 vertices.

Sorted: b-e(2), a-c(3), f-g(4), a-b(5), c-d(5), e-g(5), b-d(6), c-f(6), d-e(6), d-f(6), d-g(6)

1. b-e (2) -> no cycle, ADD    components: {b,e}
2. a-c (3) -> no cycle, ADD    components: {a,c} {b,e}
3. f-g (4) -> no cycle, ADD    components: {f,g} {a,c} {b,e}
4. a-b (5) -> a∈{a,c}, b∈{b,e}, different -> ADD   {a,b,c,e}
5. c-d (5) -> c∈{a,b,c,e}, d isolated -> ADD        {a,b,c,d,e}
6. e-g (5) -> e∈{a,b,c,d,e}, g∈{f,g} -> ADD         {a,b,c,d,e,f,g}  ← all 7 vertices, MST complete

MST edge order: b-e, a-c, f-g, a-b, c-d, e-g — total weight = 2+3+4+5+5+5 = 24. All weight-6 edges are rejected as unneeded once the tree already spans every vertex.

Key reasoning points:

• Kruskal's is edge-based and global — always picks the cheapest safe edge anywhere in the graph — unlike Prim's, which grows one connected tree outward from a start vertex.
• The cycle check via union-find is the step examiners most often see omitted — without it, Kruskal's would just be "sort and add edges," which produces an invalid result.

📝 Shortest Path vs Longest Path — Why One Is Easy and the Other Is NP-Hard

2020, Paper I, Q6(a)–(d) (7+3+7+3 marks) — John rides a van from New Square (S) to City Harbor (T), charged Rs. 10/km, with numerous possible routes. (a) He (dishonestly) always wants the longest path — write an algorithm to select it. (b) Compute its complexity and classify as P/NP/NP-complete. (c) Write an algorithm to find the minimum distance between S and T. (d) Derive that algorithm's complexity.

(a) Longest path — brute-force backtracking DFS over all simple paths:

LongestPath(G, S, T):
    best <- -infinity; bestPath <- []
    DFS(node, path, distSoFar):
        if node == T:
            if distSoFar > best: best <- distSoFar; bestPath <- path
            return
        mark node visited
        for each neighbor v with edge weight w:
            if v not visited: DFS(v, path+[v], distSoFar+w)
        unmark node visited        // backtrack
    DFS(S, [S], 0); return bestPath, best

(b) Complexity: explores up to O(V!) simple paths — exponential, NOT polynomial. Deciding "is there a simple path of length ≥ k?" is NP-complete (Hamiltonian Path reduces to it), so the optimization version is NP-hard.

(c) Minimum distance — since distances (edge weights) are non-negative, Dijkstra's algorithm applies directly:

Dijkstra(G, S, T):
    dist[v] <- infinity for all v; dist[S] <- 0
    PQ <- min-priority-queue of vertices keyed by dist
    while PQ not empty:
        u <- extract-min(PQ); if u == T: break
        for each neighbor v of u with weight w(u,v):
            if dist[u]+w(u,v) < dist[v]:
                dist[v] <- dist[u]+w(u,v); prev[v] <- u
                decrease-key(v, dist[v])
    reconstruct path from T via prev[]

(d) Complexity: with a binary-heap priority queue, V extract-min ops + up to E decrease-key ops (O(log V) each) → O((V+E) log V) — polynomial, unlike the brute-force longest-path approach.

Exam angle: A favourite FPSC pairing — shortest path is solvable in polynomial time (Dijkstra), but the longest simple path is NP-hard, because the greedy/optimal-substructure property that makes Dijkstra correct does not hold when maximizing over non-repeating paths.

📝 Graph vs Tree

2018, Paper I, Q6(c) (5 marks) — Differentiate between graph and trees. Which is a special case of the other?

• Tree: hierarchical, connected, acyclic; exactly one path between any two nodes; n nodes ⇒ exactly n−1 edges; one root, every other node has exactly one parent.
• Graph: general — vertices + edges with no restriction on cycles/connectivity/paths; may be cyclic, disconnected, directed/undirected; no inherent hierarchy.
• Answer: A Tree is a special case of a Graph — specifically, a connected, acyclic (undirected) graph. Every tree is a graph; not every graph is a tree.

MCQ Trap: Never reverse the relationship. Also: the "n nodes ⇒ n−1 edges" rule is guaranteed only for trees, not general graphs.

📝 BFS for Distances (not just paths)

2024, Paper I, Q3(c) (8 marks) — Write a version of BFS that finds the distances from the start node to each of the others, rather than the actual paths.

vector<int> bfsDistances(int start, int n, vector<vector<int>>& adj) {
    vector<int> dist(n, -1);       // -1 = unvisited/unreachable
    queue<int> q;
    dist[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;   // one more edge than u
                q.push(v);
            }
        }
    }
    return dist;
}

Because BFS visits nodes in strictly increasing order of distance from start, dist[v] is simply one more than the distance of the node that discovered it. Runs in O(V+E) — identical to ordinary BFS, just tracking a distance counter instead of parent pointers.

📝 MCQ — Shortest Path Complexity

2024, Paper II, Q5 (1 mark) — The time complexity of finding a shortest path in a network is:

• A. Fairly low with Dijkstra's algorithm ✅ (correct)
• B. Very efficient with A* search given spatial heuristics
• C. Better than the above two using some randomization mechanism in large networks
• D. None of these

Explanation: Dijkstra's finds shortest paths (non-negative weights) in O((V+E) log V) with a priority queue — the standard, generally efficient answer. A* can beat it in practice, but only with a good admissible domain-specific heuristic, which isn't a general guarantee — so it isn't the safest textbook answer.

---n## Application: Bounded-Depth BFS — "Friends of Friends"nA common applied graph question models a social network as an undirected graph (vertices = users, edges = friendship connections, usually via an adjacency list). "Friends of friends" of a user X means every user at graph-distance exactly 2 from X — i.e., a friend of one of X's direct friends, excluding X itself and anyone already a direct friend. This is simply a depth-limited BFS, capped at 2 levels instead of exploring the whole graph.ncpp\nvector<int> friendsOfFriends(int X, vector<vector<int>>& adj) {\n unordered_set<int> directFriends(adj[X].begin(), adj[X].end());\n unordered_set<int> result;\n for (int f : adj[X]) { // level 1: X's direct friends\n for (int fof : adj[f]) { // level 2: friends of those friends\n if (fof != X && !directFriends.count(fof))\n result.insert(fof); // exclude X itself and existing direct friends\n }\n }\n return vector<int>(result.begin(), result.end());\n}\nnComplexity: O(V+E) in the worst case — the same asymptotic class as full BFS, since a depth-2 traversal from a high-degree vertex can still touch a large fraction of the graph; using a set avoids double-counting mutual friends-of-friends reached through multiple paths.n### Exam AnglenThis is the same core mechanism as the "BFS for distances" technique already on this page — just stopped after 2 levels instead of running to completion, and filtered against the direct-friend set. Framing an algorithm question as a depth-limited BFS (rather than reaching for a brand-new technique) is exactly the recognition FPSC is testing.n## 📌 More Sample & Repeated FPSC Questionsn### 📝 Exam Practice: Social Network Friends-of-Friendsn2020, Paper I, Q8(b) (7 marks) — Suppose you are representing a social network (such as Facebook) as a graph. Devise an algorithm through which you can determine friends of friends.nModel answer: see the "Application: Bounded-Depth BFS" section above — model the network as an undirected graph, run BFS from the target user capped at depth 2, and exclude the user themselves and their direct friends from the result set. State the O(V+E) complexity and note that it's structurally identical to the BFS-distance technique elsewhere on this page, just depth-limited.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2018 · Paper-I · Q6(c) · 5 marks

Q. Differentiate between graphs and trees. Which is a special case of the other?

Ans.

• A tree is a special case of a graph: a connected, acyclic graph.

2019 · Paper-I · Q6(c) · 5 marks

Q. For the given graph, find the sequence of edges added to the minimum spanning tree using Kruskal's algorithm.

Ans. (Edge weights as read from the figure: b–e 2, a–c 3, e–f 3, a–b 5, b–c 4, f–g 4, c–d 5, e–g 5, and 6 on b–d, d–e, d–f, c–f. If your figure differs, apply the same steps.)

• Kruskal's algorithm: sort all edges by weight, then add each edge unless it forms a cycle.

• MST edges: b–e, a–c, e–f, b–c, f–g, c–d, total weight 2 + 3 + 3 + 4 + 4 + 5 = 21. Time O(E log E).

2020 · Paper-I · Q6 · 20 marks (longest and shortest path)

Q. (a) Write an algorithm that picks the longest path between S and T by evaluating all possible paths. (b) Find its complexity and say whether it is in P, NP or NP-complete. (c) Write an algorithm for the minimum distance between S and T. (d) Derive its complexity.

Ans.

• (a) Longest path by brute force:

longest = 0
DFS(u, length, visited):
    if u == T: longest = max(longest, length); return
    mark u visited
    for each edge (u, v, w) with v not visited:
        DFS(v, length + w, visited)
    unmark u                       // backtrack
DFS(S, 0, {})

• (b) Complexity: it explores every simple path, so it is exponential, up to O(n!) in the worst case. The longest simple path problem is NP-hard (its decision version is NP-complete), so no polynomial algorithm is known.
• (c) Shortest path (Dijkstra):

dist[S] = 0, all other dist = infinity; put S in a min-priority queue
while queue not empty:
    u = extract-min
    for each edge (u, v, w):
        if dist[u] + w < dist[v]: dist[v] = dist[u] + w; update queue
return dist[T]

• (d) Complexity: with a binary heap, O((V + E) log V). It is in P. (The weights must be non-negative.)

2020 · Paper-I · Q8(b)(c) · 12 marks

Q. Represent a social network as a graph and devise an algorithm to find friends of friends. Explain its complexity.

Ans.

• Model: each person is a vertex and each friendship an undirected edge. Use an adjacency list.
• Algorithm (BFS to depth 2):

friendsOfFriends(p):
    F = set of neighbours of p                    // direct friends
    result = empty set
    for each f in F:
        for each g in neighbours(f):
            if g != p and g not in F: add g to result
    return result

• Complexity: the work is the sum of the degrees of p's friends. It is at most O(V + E) overall (O(d²) for average degree d). Space O(V) for the sets.

2024 · Paper-I · Q3(c) · 8 marks

Q. Write a version of Breadth-First Search (BFS) that finds the distances from the start node to each of the others, rather than the actual paths.

Ans.

BFS-distances(G, s):
    for each vertex v: dist[v] = -1          // -1 means not yet reached
    dist[s] = 0
    enqueue(Q, s)
    while Q is not empty:
        u = dequeue(Q)
        for each neighbour v of u:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                enqueue(Q, v)
    return dist

• BFS visits vertices level by level, so the first time a vertex is reached gives its shortest distance (in number of edges). Time O(V + E).