Unit V · Graphs — Interactive Notes

Unit V · Part 1

Graph Basics

What a graph is, why almost every network in the real world is a graph, and the one counting rule you will use in every answer.

Syllabus: Definition of graph, directed and undirected graphs, basic properties.

1.1What is a graph?

Definition (write this in the exam)

A graph G is a pair of two finite sets, G = (V, E), where V is a non-empty set of vertices (also called nodes) and E is a set of edges. Each edge is a pair of vertices (u, v) and shows that u and v are connected.

In simple words

A graph is dots joined by lines. The dots are vertices, the lines are edges. That is all. A city map (cities and roads), Instagram (people and follows) and the internet (computers and cables) are all graphs.

V = { A, B, C, D, E, F }

E = { (A,B), (A,C), (B,C), (B,D),
(C,E), (D,E), (D,F), (E,F) }

|V| = 6 is the order of the graph. |E| = 8 is the size of the graph.

A graph is a non-linear data structure: one vertex can be connected to many others, in any pattern. There is no first or last element and no root.

Graph = vertices + edges. Nothing else matters — not the position of the dots, not the length or shape of the lines.

The same graph can be drawn in many ways. If you move vertex F to the top of the page, it is still the same graph, because the same pairs are connected. Only the connections matter.

1.2Graphs around you

Whenever things are connected to other things, you have a graph. Learning graphs means learning how Google Maps, social media and the internet work underneath.

Road map

Cities are vertices, roads are edges. The road length is the weight. Google Maps runs a shortest-path algorithm (Part 6).

Friends network

People are vertices; a friendship is an edge. Friendship goes both ways, so the graph is undirected.

Instagram follows

If you follow someone, they may not follow you back. Each follow is an arrow, so this graph is directed.

Course prerequisites

“C before Data Structures before Algorithms.” Arrows with no loop: a DAG. Topological sort gives a valid study order.

Computer network

Routers are vertices and cables are edges. Routing protocols such as OSPF use Dijkstra to send packets on the fastest path.

Web pages

Each page is a vertex and each hyperlink is a directed edge. Search engines walk this graph with BFS to discover pages.

1.3Undirected and directed graphs

	Undirected graph	Directed graph (digraph)
Edge	Unordered pair (u, v). (u, v) and (v, u) are the same edge.	Ordered pair <u, v>. u is the tail (start), v is the head (end).
Drawn as	A plain line	An arrow
Degree	One number: degree	Two numbers: in-degree and out-degree
Max edges (simple)	n(n − 1) / 2	n(n − 1)
Adjacency matrix	Always symmetric	Usually not symmetric
Example	Facebook friends, roads with two-way traffic	Instagram follows, one-way streets, web links

Common mistake: Writing directed edges with round brackets. Use (u, v) for undirected edges and <u, v> for directed edges. The order inside < > matters.

1.4Degree and the handshake rule

The degree of a vertex is the number of edges touching it. In Figure 1, deg(A) = 2 and deg(B) = 3.

Handshake lemma: in every undirected graph, the sum of all degrees = 2 × (number of edges).

Σ deg(v) = 2|E|

Why it is true: every edge has two ends. When you add up the degrees, each edge is counted once at each end, so it is counted exactly twice. In Figure 1: 2 + 3 + 3 + 3 + 3 + 2 = 16 = 2 × 8.

Result you get for free: the number of vertices with an odd degree is always even. The total 2|E| is even; the even degrees add up to an even number, so the odd degrees must also add up to an even number, and that needs an even count of them.

Exam use: “Can a graph have 5 vertices with degrees 3, 3, 3, 3, 3?” No. The sum is 15, which is odd, but the sum of degrees must be 2|E| (even). Equally: it would have 5 odd-degree vertices, which is an odd count.

For a directed graph the rule becomes: Σ in-degree = Σ out-degree = |E|. Each arrow leaves one vertex and enters one vertex.

1.5How many edges can a graph have?

In a simple graph (no loops, no repeated edges) every pair of vertices can have at most one edge. With n vertices there are n(n − 1)/2 pairs.

Graph	Minimum edges	Maximum edges	n = 5
Simple undirected	0	n(n − 1)/2	10
Simple directed	0	n(n − 1)	20
Connected undirected	n − 1 (a tree)	n(n − 1)/2	4 to 10

A graph with close to the maximum number of edges is dense. A graph with few edges (about n) is sparse. Most real graphs, like road maps, are sparse. This decides which representation to use in Part 4.

1.6Graph vs tree

In Unit IV you studied trees. A tree is just a special graph: connected and with no cycle.

	Tree	Graph
Root	One special root	No root
Cycles	Never	Allowed
Edges for n vertices	Exactly n − 1	0 to n(n − 1)/2
Path between two vertices	Exactly one	Zero, one or many
Connected?	Always	Maybe not
Model	Hierarchy (parent–child)	Network (any relation)
Traversal needs visited[]?	No	Yes, to avoid looping on cycles

Every tree is a graph, but not every graph is a tree.

1.7Map of this unit

Each part builds on the one before. Parts 1–5 are the syllabus; Part 6 takes you beyond it into the algorithms used in real software.

PART 2TerminologyDegree, path, cycle, connected, component. PART 3Types of graphSimple, multi, complete, bipartite, DAG, isomorphic… PART 4RepresentationMatrix, list, incidence matrix, edge list. PART 5BFS & DFSVisit every vertex once using a queue or a stack. PART 6 · ADVANCEDMST & shortest pathPrim, Kruskal, Dijkstra, topological sort. ✓Revision & examCheat sheet, model answers, mixed quiz.

Remember from Part 1

G = (V, E): a set of vertices and a set of edges.
Undirected edge (u, v) goes both ways; directed edge <u, v> goes from u to v only.
Σ deg = 2|E|, so the number of odd-degree vertices is even.
Max edges: n(n − 1)/2 undirected, n(n − 1) directed.
A tree is a connected graph with no cycle and n − 1 edges.

Unit V · Part 2

Graph Terminology

Each term is its own section, with one definition and one example. Do not mix them. The picture is the example you can redraw in the exam.

Syllabus: vertex, edge, adjacent vertices and edges, incident, neighbour, degree, in-degree, out-degree, isolated, pendant, source, sink, loop, multiple edges, walk, trail, path, closed walk, circuit, cycle, length, distance, connected, component, subgraph, spanning subgraph, reachable, predecessor, successor, weight, bridge, cut vertex.

2.1Vertex and edge

Definition

A vertex (node) is a point of the graph. An edge (link) joins two vertices. A directed edge is called an arc.

Example. In G, the vertices are A, B, C, D, E, F. One edge is (B, D). Order = |V| = 6. Size = |E| = 8.

2.2Adjacent vertices

Definition

Two vertices are adjacent if one edge joins them directly.

Example. A is adjacent to B and to C. A is not adjacent to D, E or F — you cannot go there in one edge.

2.3Adjacent edges

Definition

Two edges are adjacent if they share a common vertex.

Example. (A, B) and (B, D) are adjacent edges. (A, B) and (E, F) are not — they share no vertex.

2.4Incident

Definition

An edge is incident on the vertices at its two ends. A vertex is incident on every edge that touches it.

Example. Edge (D, F) is incident on D and on F. It is not incident on A.

2.5Neighbour

Definition

The neighbours of v are the vertices adjacent to v.

Example. Neighbours of B = {A, C, D}. Neighbours of F = {D, E}.

2.6Degree

Definition

Degree of v, written deg(v), is the number of edges touching v. A self-loop counts 2. The degree of the graph, Δ(G), is the largest degree.

Example. deg(B) = 3, deg(F) = 1, deg(G) = 0. Sum of degrees = 2+3+3+2+3+1+0 = 14 = 2 × 7 edges.

2.7In-degree

Definition

In a directed graph, in-degree in(v) is the number of arrows that enter v.

Example. in(E) = 2 (from D and F). in(A) = 0. Sum of all in-degrees = number of arrows = 7.

2.8Out-degree

Definition

Out-degree out(v) is the number of arrows that leave v. In a digraph, deg(v) = in(v) + out(v).

Example. out(A) = 2, out(E) = 0. Sum of all out-degrees = 7, the same as the sum of in-degrees.

2.9Isolated vertex

Definition

An isolated vertex has degree 0. No edge touches it.

Example. D is isolated. A, B and C are not.

2.10Pendant vertex

Definition

A pendant vertex (leaf) has degree exactly 1.

Example. A and D are pendant. B and C are not.

2.11Source

Definition

A source is a vertex with in-degree 0. Arrows only leave it.

Example. A is a source. B is not, because the arrow A → B enters B.

2.12Sink

Definition

A sink is a vertex with out-degree 0. Arrows only enter it.

Example. D is a sink. in(D) = 2, out(D) = 0.

2.13Loop (self-loop)

Definition

A loop is an edge from a vertex to itself. In an undirected graph it adds 2 to the degree.

Example. C has a loop and the edge B–C, so deg(C) = 2 + 1 = 3.

2.14Multiple (parallel) edges

Definition

Multiple edges are two or more edges with the same two end vertices. Each one is a separate edge.

Example. There are 3 edges between A and B, so they add 3 to deg(A) and 3 to deg(B).

2.15Walk

Definition

A walk is a sequence of vertices where each next vertex is adjacent to the one before. Vertices and edges may repeat.

Example. A–B–C–A–B–D is a walk from A to D. It repeats A, B and the edge A–B, so it is not a path.

2.16Trail

Definition

A trail is a walk that repeats no edge. A vertex may still repeat.

Example. A–B–D–E–C–B is a trail: no edge is used twice, but B appears twice, so it is not a path.

2.17Path

Definition

A path (simple path) is a walk with no repeated vertex.

Example. A–B–D–F is a path. A–B–C–A–B–D is not, because A and B repeat.

2.18Closed walk

Definition

A closed walk starts and ends at the same vertex. It may repeat vertices and edges.

Example. A–B–C–A is a closed walk of length 3. A–B–D is not closed: it starts at A and ends at D.

2.19Circuit

Definition

A circuit is a closed trail: it returns to the start and repeats no edge.

Example. B–C–E–D–B is a circuit of length 4. A–B–C–A–B–A is a closed walk, not a circuit, because A–B is used twice.

2.20Cycle

Definition

A cycle is a closed path of length at least 3: no vertex repeats except that the first vertex is also the last.

Example. D–E–F–D is a cycle. A loop is not called a cycle here. A cycle of length 3 is a triangle.

2.21Length

Definition

The length of a walk, path or cycle is the number of edges in it, not the number of vertices.

Example. A–B–D–F has 4 vertices and length 3. The cycle D–E–F–D has length 3.

2.22Distance

Definition

The distance from u to v is the length of the shortest path from u to v. If no path exists, the distance is infinite.

Example. Distance from A to F is 3. A–C–E–F is also length 3. No shorter path exists. BFS finds this.

2.23Connected graph

Definition

An undirected graph is connected if there is a path between every pair of vertices.

Example. G is connected. From F you can reach A by F–D–B–A.

2.24Disconnected graph and component

Definition

A graph is disconnected if some pair of vertices has no path between them. A component is one largest connected piece.

Example. This graph has 3 components. F is a component by itself. A connected graph has exactly 1 component.

2.25Subgraph

Definition

A subgraph uses some of the vertices and some of the edges of G. Every chosen edge must join two chosen vertices.

Example. Vertices {D, E, F} with edges D–E, E–F, D–F form a subgraph. It is a triangle.

2.26Spanning subgraph

Definition

A spanning subgraph keeps every vertex of G. A spanning tree is a spanning subgraph that is a tree (n − 1 edges, no cycle).

Example. The thick edges form a spanning tree of G: 6 vertices, 5 edges, no cycle.

2.27Reachable

Definition

In a directed graph, v is reachable from u if a directed path goes from u to v.

Example. C is reachable from A (A → B → C). A is not reachable from C: no arrow leads back. E can reach D, but D cannot reach E.

2.28Predecessor and successor

Definition

If the arrow u → v exists, u is a predecessor of v and v is a successor of u.

Example. Predecessors of C are A and B. Successors of A are B and C. E has no successor in the earlier digraph, so E is a sink.

2.29Weight

Definition

A weight is a number on an edge: distance, cost or time. A graph with weights is a weighted graph.

Example. Weight of A–B is 4. The path A–B–D has total weight 4 + 5 = 9. Length of that path is still 2 (two edges).

2.30Bridge and cut vertex

Definition

A bridge is an edge whose removal increases the number of components. A cut vertex is a vertex whose removal does the same.

Example. Delete C–D and the graph splits. So C–D is a bridge. Delete C and {A, B} is cut off from {D, E}. C is a cut vertex. A–B is not a bridge: A–C–B remains.

2.31Walk, trail, path, cycle — side by side

Term	Vertex may repeat?	Edge may repeat?	Back to start?	Example in G
Walk	Yes	Yes	No	A–B–C–A–B–D
Trail	Yes	No	No	A–B–D–E–C–B
Path	No	No	No	A–B–D–F
Closed walk	Yes	Yes	Yes	A–B–C–A–B–A
Circuit	Only start = end	No	Yes	B–C–E–D–B
Cycle	Only start = end	No	Yes, length ≥ 3	D–E–F–D

Common mistake: calling the length the number of vertices. A–B–D–F has 4 vertices and length 3.

2.32Term explorer

Tap a vertex to see its degree, neighbours and incident edges. Tap a second vertex to see every simple path between them. Switch to Directed for in-degree, out-degree, source and sink.

Remember from Part 2

Adjacent = joined by an edge. Incident = the edge touches that vertex.
Degree counts edges. A loop adds 2. Isolated = 0, pendant = 1.
Source = in-degree 0. Sink = out-degree 0.
Walk may repeat. Trail repeats no edge. Path repeats no vertex. Length = number of edges.
Cycle = closed path, length at least 3. Connected = one component.

Unit V · Part 3

Types of Graph

Each type is a separate section. Learn the rule, then the example drawn next to it. One graph can have more than one name — say which rule you used.

Syllabus: null, trivial, simple, multigraph, pseudograph, undirected, directed, weighted, regular, complete, path, cycle, star, wheel, bipartite, complete bipartite, connected, disconnected, strongly connected, weakly connected, cyclic, acyclic, DAG, tree, forest, isomorphic, planar.

3.1Null graph

Vertices, but no edges. Every vertex is isolated.

Example. Four cities and no roads yet.

|E| = 0

3.2Trivial graph

Exactly one vertex and no edge. It is a null graph with n = 1.

Example. A single computer, not yet joined to a network.

n = 1, |E| = 0

3.3Simple graph

At most one edge between any pair, and no loop. This is what “graph” means in most questions.

Example. The drawing has 5 edges, no pair repeated, no loop.

no loops · no parallel edges

3.4Multigraph

Parallel edges are allowed. Loops are not.

Example. Two train lines between the same two cities, drawn as two A–B edges.

parallel edges allowed

3.5Pseudograph

Both parallel edges and loops are allowed. This is the most general undirected graph.

Example. Two roads A–B, plus a loop at C (a road that leaves C and returns to C).

loops + parallel edges

3.6Undirected graph

Edges have no direction. (u, v) is the same edge as (v, u). You may travel both ways.

Example. A two-way road between A and B.

3.7Directed graph

Every edge is an arrow. <u, v> is not the same as <v, u>. Also called a digraph.

Example. One-way streets. You can go A → B, but not B → A, unless a second arrow is drawn.

3.8Weighted graph

Every edge has a number: distance, time or cost. A weighted graph may be directed or undirected.

Example. A–B costs 4, B–C costs 2. Path A–B–C has total weight 6 and length 2.

weight on every edge

3.9Regular graph

Every vertex has the same degree k. This cycle is 2-regular. A k-regular graph on n vertices has nk/2 edges, so nk must be even.

Example. A hexagon: every corner has degree 2. It is regular, but not complete.

deg(v) = k for every v

3.10Complete graph

K_n: every vertex is joined to every other vertex by exactly one edge. K_n has n(n − 1)/2 edges and is (n − 1)-regular. Every complete graph is regular. Not every regular graph is complete.

Example. K₄ has 6 edges. Each vertex has degree 3.

|E| = n(n − 1)/2

3.11Path graph

P_n is n vertices in one line. The two ends have degree 1. The others have degree 2. It is a tree, so it has n − 1 edges.

Example. P₅ is drawn. It is not a cycle, because the ends are not joined.

Pₙ has n − 1 edges

3.12Cycle graph

C_n is one cycle through all n vertices. It has n edges and is 2-regular. C₃ = K₃. An even cycle is bipartite. An odd cycle is not.

Example. C₅ is drawn. It is regular, not complete, and not bipartite.

Cₙ has n edges

3.13Star

K_1,n: one centre joined to n leaves, and no other edges. It is a tree and a complete bipartite graph.

Example. K_1,4. The centre has degree 4. Each leaf has degree 1.

centre degree n

3.14Wheel

A cycle plus one hub joined to every vertex of the cycle. The hub has the highest degree.

Example. A 4-cycle with hub E. E has degree 4. This is not a tree: it has cycles.

cycle + one hub

3.15Bipartite graph

Vertices split into two groups so that every edge goes from one group to the other. No edge stays inside a group.

Test: bipartite if and only if there is no odd cycle.

Example. Students {A, B, C} and courses {X, Y, Z}. An edge means “enrolled in”.

no odd cycle

3.16Complete bipartite graph

K_m,n: every vertex of the first group is joined to every vertex of the second group, and there are no edges inside a group. It has m × n edges.

Example. K_2,3 has 2 × 3 = 6 edges. A star is K_1,n.

|E| = m · n

3.17Connected graph

An undirected graph with a path between every pair of vertices. It has exactly one component.

Example. The square is connected. From any corner you can walk to any other.

1 component

3.18Disconnected graph

At least one pair of vertices has no path between them. The pieces are the components.

Example. {A, B, C} and {D, E} are two components. There is no path from A to D.

2 or more components

3.19Strongly connected graph

A directed graph in which every vertex can reach every other vertex by following the arrows.

Example. A → B → C → D → A. From any start you can go all the way round.

path both ways, following arrows

3.20Weakly connected graph

Not strongly connected, but it becomes connected if you ignore the arrows.

Example. Nothing leaves B, so B cannot reach A. Ignore the arrows and it is one piece. Strongly connected implies weakly connected. The reverse is false.

ignore arrows → connected

3.21Cyclic graph

Contains at least one cycle.

Example. A–B–C–A is a cycle, so the graph is cyclic. D is outside the cycle, but one cycle is enough.

has a cycle

3.22Acyclic graph

Contains no cycle. Every tree and every forest is acyclic. A single edge is acyclic.

Example. This path has no way back to an earlier vertex without repeating an edge.

no cycle

3.23DAG

A directed acyclic graph: arrows, and no directed cycle. Used for task order, course plans and build tools. Every DAG has a topological order.

Example. A and B have no arrow into them. Nothing leads back, so there is no directed cycle.

directed · no directed cycle

3.24Tree

Connected and acyclic. Exactly one path between any two vertices. A tree with n vertices has n − 1 edges.

Example. 6 vertices, 5 edges, no cycle. D, E and F are leaves.

n − 1 edges

3.25Forest

An acyclic graph that may be disconnected: a set of trees. A forest with n vertices and c trees has n − c edges.

Example. Three trees: {A, B, C}, {D, E}, and {F}. 6 vertices, 3 trees, 3 edges.

n − c edges

3.26Isomorphic graphs

Two graphs are isomorphic if renaming the vertices of one gives the other. Same structure, different drawing.

Example. Map 1→Q, 2→P, 3→S, 4→R onto a diamond with one diagonal. Same vertices, same edges, same degree sequence 3, 3, 2, 2. Equal counts are necessary, not enough — give the mapping.

same structure

3.27Planar graph

A graph that can be drawn with no two edges crossing. K₄ looks crossed in a square, but it can be redrawn with one vertex inside and no crossing, so K₄ is planar. K₅ and K_3,3 are not planar.

Example. This drawing of K₄ has no crossing.

drawable with no crossing

3.28Type checker

Pick an example or type your own edges (A-B undirected, A>B directed). The checker tests every property from this part and draws a bipartite colouring when one exists.

3.29Summary table

Type	Rule	Edges
Path P_n	A line of n vertices	n − 1
Cycle C_n	One cycle, every degree 2	n
Star K_1,n	One centre, n leaves	n
Trivial	One vertex, no edge	0
Null	No edges	0
Simple	No loops, no parallel edges	≤ n(n−1)/2
Multigraph	Parallel edges allowed	any
Pseudograph	Loops and parallel edges allowed	any
Weighted	Every edge has a number	—
k-regular	All degrees = k	nk/2
Complete K_n	Every pair joined	n(n−1)/2
Complete bipartite K_m,n	Two groups, every cross pair joined	m·n
Tree	Connected + acyclic	n − 1
Forest of c trees	Acyclic	n − c
Strongly connected	Directed path both ways between every pair	≥ n
DAG	Directed, no directed cycle	≤ n(n−1)/2

3.30Name the graph — ten examples

Cover the right column and try each one. A graph can have more than one name: K₃ is also C₃, a complete graph, and 2-regular.

1. Three vertices, no edges

Null graph on 3 vertices. Every vertex is isolated. It is also 0-regular.

2. Triangle

K₃ and C₃. Complete, 2-regular, a cycle, and not bipartite (odd cycle).

3. Square

C₄. 2-regular, bipartite (groups {A, C} and {B, D}), not complete.

4. One centre, three leaves

Star K_1,3. A tree (3 edges, 4 vertices). Bipartite. Not regular.

5. Two edges between A and B

Multigraph, not simple. deg(A) = 2, deg(B) = 3, deg(C) = 1.

6. A loop and a separate edge

Pseudograph (the loop). Two components: {A} and {B, C}. deg(A) = 2.

7. A directed triangle

Strongly connected: follow the arrows all the way round. Also a directed cycle.

8. Arrows, no way back

A DAG (no directed cycle). Weakly connected. A is a source, C is a sink. Topological order A, B, C.

9. Numbers on the edges

Weighted path. Total weight A to D = 5 + 1 + 8 = 14. Still a tree.

10. Connected, one extra edge

Not a tree: 5 vertices and 5 edges, so exactly one cycle (A–B–D–C–A). E is pendant. D is a cut vertex; D–E is a bridge.

Do not mix the names. Regular does not mean complete. Connected does not mean strongly connected. A cycle graph is 2-regular, but a 3-regular graph need not be a cycle. Always state the rule you used.

Remember from Part 3

Simple = no loops and no parallel edges. Multigraph allows parallel edges; pseudograph allows loops too.
Complete K_n: n(n − 1)/2 edges, (n − 1)-regular.
Bipartite ⇔ no odd cycle.
Strongly connected: follow arrows from anyone to anyone. Weakly: only if you ignore arrows.
Isomorphic = same structure; prove with a vertex mapping.
Pₙ is a path (n − 1 edges). Cₙ is a cycle (n edges, 2-regular). A star is K_1,n.

Unit V · Part 4

Representation of Graphs

A computer cannot see a drawing. We must store “who is connected to whom” as numbers. There are four standard ways; two of them are used almost everywhere.

Syllabus: Representation of graphs — adjacency matrix (including the program that checks whether an edge is present between two vertices), adjacency list, incidence matrix; programs and comparison.

4.1Adjacency matrix

Definition

For a graph with n vertices, the adjacency matrix A is an n × n array where A[i][j] = 1 if there is an edge from vertex i to vertex j, and A[i][j] = 0 otherwise.

In simple words

Make a table with one row and one column for every vertex. Put a 1 in the box where row u meets column v if u and v are connected.

Example 1 — undirected graph

Example 2 — directed graph (a different drawing)

Example 3 — weighted graph (weights, not 1s)

Properties

Space: always n² cells, even if the graph has very few edges.
Check “is there an edge u–v?” in O(1) — just read A[u][v].
Find all neighbours of u: scan the whole row, O(n).
Undirected ⇒ symmetric (A[u][v] = A[v][u]). Only the upper half needs to be stored.
Diagonal is all 0 in a simple graph (no self-loops).
Number of 1s = 2|E| (undirected) or |E| (directed).

4.1bProgram: matrix, and is an edge present?

Exam question

Write a C Program to represent an undirected graph using an adjacency matrix and display the matrix. Also check whether an edge is present between two vertices.

This is a fourth example, with numbered vertices, and the practical program. Click Run under the sample output to watch the real output print.

Program — adjacency matrix, and find if an edge is present between two nodes

This is the practical program: numbered vertices, an n × n matrix, then one question — does the edge (u, v) exist? The answer is a single read of adj[u][v].

/* Adjacency matrix: create, display, and check if an edge is present
   between two vertices. Vertices are numbered 0, 1, 2, ...
   (conio.h from the old listing is not used, so it is omitted.) */
#include <stdio.h>
#define MAX 20

int adj[MAX][MAX], n, edges;

void createGraph() {
    int i, j, u, v;

    printf("Enter number of vertices: ");
    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            adj[i][j] = 0;
        }
    }

    printf("Enter number of edges: ");
    scanf("%d", &edges);

    printf("Enter edges (u v):\n");
    for (i = 0; i < edges; i++) {
        scanf("%d %d", &u, &v);
        adj[u][v] = 1;
        adj[v][u] = 1; /* undirected graph: both ways */
    }
}

void displayMatrix() {
    int i, j;
    printf("\nAdjacency Matrix:\n   ");

    for (i = 0; i < n; i++) {
        printf("%d ", i);
    }
    printf("\n");

    for (i = 0; i < n; i++) {
        printf("%d: ", i);
        for (j = 0; j < n; j++) {
            printf("%d ", adj[i][j]);
        }
        printf("\n");
    }
}

void checkEdge() {
    int u, v;
    printf("\nEnter vertices to check edge (u v): ");
    scanf("%d %d", &u, &v);

    if (adj[u][v] == 1) {
        printf("Edge exists between %d and %d\n", u, v);
    } else {
        printf("No edge between %d and %d\n", u, v);
    }
}

int main() {
    createGraph();
    displayMatrix();
    checkEdge();
    return 0;
}

Input

Output — edge is present

Adjacency Matrix:
   0 1 2 3
0: 0 1 1 0
1: 1 0 0 1
2: 1 0 0 1
3: 0 1 1 0

Edge exists between 0 and 1

Same graph, check 0 and 3

No edge between 0 and 3

How to read the answer: Row 0, column 1 is 1, so the edge exists. Row 0, column 3 is 0, so it does not. For an undirected graph the matrix is symmetric, so checking (1, 0) gives the same answer as (0, 1).

Program 1 — adjacency matrix: create, display, degrees

/* Adjacency matrix: create, display, degree of every vertex */
#include <stdio.h>
#define MAX 20

int adj[MAX][MAX];
int n, directed;

void createGraph() {
    int e, i;
    char u, v;
    printf("Number of vertices: ");
    scanf("%d", &n);
    printf("Directed? (1 = yes, 0 = no): ");
    scanf("%d", &directed);
    printf("Number of edges: ");
    scanf("%d", &e);
    for (i = 0; i < e; i++) {
        printf("Edge %d (e.g. A B): ", i + 1);
        scanf(" %c %c", &u, &v);
        adj[u - 'A'][v - 'A'] = 1;
        if (!directed)
            adj[v - 'A'][u - 'A'] = 1;   /* undirected: both ways */
    }
}

void displayMatrix() {
    int i, j;
    printf("\nAdjacency matrix:\n   ");
    for (j = 0; j < n; j++) printf(" %c", 'A' + j);
    printf("\n");
    for (i = 0; i < n; i++) {
        printf(" %c ", 'A' + i);
        for (j = 0; j < n; j++) printf(" %d", adj[i][j]);
        printf("\n");
    }
}

void degrees() {
    int i, j, in, out;
    printf("\nVertex  ");
    printf(directed ? "In  Out\n" : "Degree\n");
    for (i = 0; i < n; i++) {
        in = out = 0;
        for (j = 0; j < n; j++) {
            out += adj[i][j];            /* row sum    */
            in  += adj[j][i];            /* column sum */
        }
        if (directed) printf("  %c     %d   %d\n", 'A' + i, in, out);
        else          printf("  %c     %d\n", 'A' + i, out);
    }
}

int main() {
    createGraph();
    displayMatrix();
    degrees();
    return 0;
}

Input (Figure 1 graph)

6
0
8
A B
A C
B C
B D
C E
D E
D F
E F

Output

Adjacency matrix:
    A B C D E F
 A  0 1 1 0 0 0
 B  1 0 1 1 0 0
 C  1 1 0 0 1 0
 D  0 1 0 0 1 1
 E  0 0 1 1 0 1
 F  0 0 0 1 1 0

Vertex  Degree
  A     2
  B     3
  C     3
  D     3
  E     3
  F     2

4.2Adjacency list

Definition

An adjacency list keeps an array of n head pointers, one per vertex. Head[u] points to a linked list of all vertices adjacent to u.

In simple words

For every vertex, write down the list of its neighbours. Like a phone's contact list: each person has their own list of friends.

Example 1 — undirected list (different reading of the same idea)

Example 2 — same numbered graph, stored as a list

Example 3 — weighted list

struct node {
    int vertex;          /* neighbour number          */
    int weight;          /* only for weighted graphs  */
    struct node *next;   /* next neighbour in list    */
};
struct node *head[MAX];  /* head[u] = first neighbour of u */

Properties

Space: O(n + e) — n heads plus 2e nodes (undirected) or e nodes (directed).
List all neighbours of u in O(deg(u)) — only real neighbours are visited. This makes BFS and DFS fast.
Check “is there an edge u–v?” needs a scan of u's list: O(deg(u)).
In-degree in a digraph is slow: you must scan every list (or keep an inverse list).

Program 2 — adjacency list with linked lists

/* Adjacency list using linked lists (new node added at the end) */
#include <stdio.h>
#include <stdlib.h>
#define MAX 20

struct node {
    int vertex;
    struct node *next;
};

struct node *head[MAX];
int n;

void addEdge(int u, int v) {
    struct node *p, *nn = (struct node *)malloc(sizeof(struct node));
    nn->vertex = v;
    nn->next = NULL;
    if (head[u] == NULL) {
        head[u] = nn;
        return;
    }
    p = head[u];
    while (p->next != NULL) p = p->next;
    p->next = nn;
}

void display() {
    int i;
    struct node *p;
    printf("\nAdjacency list:\n");
    for (i = 0; i < n; i++) {
        printf(" %c", 'A' + i);
        for (p = head[i]; p != NULL; p = p->next)
            printf(" -> %c", 'A' + p->vertex);
        printf(" -> NULL\n");
    }
}

int main() {
    int e, i, directed;
    char u, v;
    printf("Number of vertices: ");
    scanf("%d", &n);
    printf("Directed? (1 = yes, 0 = no): ");
    scanf("%d", &directed);
    printf("Number of edges: ");
    scanf("%d", &e);
    for (i = 0; i < e; i++) {
        printf("Edge %d (e.g. A B): ", i + 1);
        scanf(" %c %c", &u, &v);
        addEdge(u - 'A', v - 'A');
        if (!directed) addEdge(v - 'A', u - 'A');
    }
    display();
    return 0;
}

Input: same as Program 1

Output

Adjacency list:
 A -> B -> C -> NULL
 B -> A -> C -> D -> NULL
 C -> A -> B -> E -> NULL
 D -> B -> E -> F -> NULL
 E -> C -> D -> F -> NULL
 F -> D -> E -> NULL

4.3Incidence matrix

Definition

The incidence matrix is an n × e array (rows = vertices, columns = edges). M[v][k] = 1 if edge k touches vertex v, otherwise 0. For a digraph, use +1 at the start (tail) and −1 at the end (head) of the edge.

Example 1 — undirected incidence (a 4-edge graph, not the matrix example)

Example 2 — directed incidence

Space is n × e, which is large for most graphs, so the incidence matrix is used mainly in theory and in electrical circuit analysis (Kirchhoff's laws).

4.4Edge list

The simplest form: just store every edge as a pair (u, v), or a triple (u, v, w) for a weighted graph. Space is O(e).

Example — weighted edge list (one row per edge, a different store from the matrix)

Finding neighbours is slow (scan all edges), but sorting edges by weight is easy. That is exactly what Kruskal's algorithm needs, so Kruskal uses an edge list.

4.5Representation lab

Edit the graph on the left. All four representations update instantly. Hover a matrix cell to light up its two vertices.

4.6Which one to use?

Operation	Adjacency matrix	Adjacency list	Incidence matrix	Edge list
Space	O(n²)	O(n + e)	O(n · e)	O(e)
Is u–v an edge?	O(1)	O(deg u)	O(e)	O(e)
All neighbours of u	O(n)	O(deg u)	O(e)	O(e)
Add an edge	O(1)	O(1) at head	new column	O(1)
BFS / DFS time	O(n²)	O(n + e)	—	—
Best for	Dense graphs, quick edge checks, Floyd–Warshall	Sparse graphs (most real graphs), BFS, DFS, Dijkstra	Circuit theory	Kruskal, input files

Exam tip: Example — a road map of 1000 cities with about 3000 roads. Matrix: 1,000,000 cells. List: 1000 + 6000 = 7000 nodes. The list is over 100 times smaller, so use the list.

Remember from Part 4

Adjacency matrix: n × n, A[u][v] = 1 if edge. Symmetric for undirected graphs. Edge check O(1), space O(n²).
Adjacency list: array of linked lists. Space O(n + e). Best for sparse graphs and traversals.
Incidence matrix: n × e, vertex vs edge.
Edge list: list of (u, v, w). Used by Kruskal.

Unit V · Part 5

Graph Traversal: BFS and DFS

For BFS and then for DFS: the idea, the complete algorithm with every line explained, a dropdown of examples (each with a player, step cards, an exam table and the program’s output), and simple tested C programs. Then BFS vs DFS, practice with instant feedback, and exam answers.

Syllabus: Graph traversal — Breadth First Search and Depth First Search, algorithms, programs and comparison.

5.1What is graph traversal?

Definition (write this in the exam)

Graph traversal is visiting every vertex of a graph exactly once, in a definite order, starting from a given source.

In simple words

Touch every dot, do not loop forever. BFS = wide first (queue). DFS = deep first (recursion).

Four rules every traversal follows

Start at the given vertex s.
Keep a visited[] array, all 0. Mark a vertex the first time you reach it and never visit it again — graphs can have cycles.
Take neighbours in number / alphabetical order (the row of the adjacency matrix). A different order gives a different, also correct, answer — so write the order you used.
If the BFS queue becomes empty, or the first DFS call returns, while some vertex is still unvisited, the graph is not connected. Start again from the smallest unvisited vertex.

5.2BFS — idea and algorithm

Definition

Breadth First Search (BFS) visits vertices level by level: the start first (distance 0), then every vertex 1 edge away, then 2 edges away, and so on. It uses a queue and a visited[] array.

Picture it

You tell news to all your friends first. Then each of them tells their friends, and so on. Nearest people hear first. The queue is the list of people who still have to pass the news on — first told, first to pass it on.

Complete algorithm

BFS(G, s)
1. For every vertex v:  visited[v] = 0
2. visited[s] = 1
   ENQUEUE(s)                 // s goes to the rear; it is the only item
3. While the queue is not empty:
     u = DEQUEUE()            // take the front
     print u                  // u is now visited and processed
     For every neighbour v of u, in order:
         If visited[v] == 0:
             visited[v] = 1   // mark NOW, not later
             ENQUEUE(v)       // v joins at the rear
4. If some vertex is still unvisited, pick the next one
   as a new start and repeat from step 2
   (the graph has more than one component)
5. Stop. The printed list is the BFS order.

Line by line — why each line is there

Line	What it does	Why it is needed
`visited[v] = 0`	Nothing is seen yet.	Clears old marks. Forget it after another traversal and BFS prints almost nothing.
`visited[s] = 1; ENQUEUE(s)`	The start is seen and waits in the queue.	The queue is the “to-do list”. BFS needs one item to begin.
`while queue not empty`	Repeat until the to-do list is empty.	Empty queue = everything reachable from s has been printed.
`u = DEQUEUE(); print u`	Take the oldest waiting vertex.	First in, first out — so all level-1 vertices come out before any level-2 vertex.
`for every neighbour v of u`	Look at vertices one edge from u, in order.	This order decides the answer. The C program scans row u from 0 to n−1.
`if visited[v] == 0`	Only new vertices.	Stops cycles and stops a vertex entering the queue twice.
`visited[v] = 1; ENQUEUE(v)`	Mark at once, put at the rear.	v is one level deeper than u. Marking now is the rule that keeps the queue clean (see the bug below).
Step 4 (restart)	Start again from an unvisited vertex.	Needed only when the graph is disconnected.

Every term in the algorithm

Term	Meaning
G = (V, E)	The graph. V = vertices, E = edges.
s (source / start)	The vertex where BFS begins.
Neighbour	A vertex joined to u by an edge. Read them from row u of the matrix, left to right.
visited[v]	1 if v has already entered the queue. Stops cycles and duplicate enqueue.
Queue	A line of vertices. FIFO — first in, first out.
Front	Left end of the queue. This vertex leaves next.
Rear	Right end of the queue. A new vertex joins here.
ENQUEUE(v)	Put v at the rear. Then mark visited[v] = 1.
DEQUEUE()	Remove and return the front. Then print that vertex.
Level / distance	How many edges from s. The start is level 0. BFS visits increasing levels.
Parent	The vertex that enqueued v. Following parents back to s gives the shortest path.
BFS tree	The edges used the first time a vertex is reached. \|V\| − 1 edges, no cycle, in one component.
Time	O(V + E) with an adjacency list. O(V²) with a matrix (each row is scanned).
Space	Queue + visited[] = O(V). The queue can hold a whole level.

How to draw the queue on paper

dequeue

BfrontCDrear

enqueue

Boxes in a row. Front (left) leaves first. Rear (right) is where a new vertex joins. Here B will leave next; a new vertex sits after D.

Why mark on enqueue? Watch the bug

Practical graph 0–1, 0–2, 1–3, 2–3, start 0. Vertex 3 is a neighbour of both 1 and 2.

Step	Right: mark on enqueue queue after	Wrong: mark on dequeue queue after
Dequeue 0	1 2	1 2
Dequeue 1	2 3	2 3
Dequeue 2	3 (3 is marked → skip)	3 3 (3 not marked yet → added again!)
Dequeue 3	empty	3
Dequeue 3	—	empty
Output	0 1 2 3 ✓	0 1 2 3 3 ✗

Mark visited on enqueue, not when you print. If you wait, the same vertex can sit in the queue twice and be printed twice.

Time and space — where O(V + E) comes from

Every vertex is enqueued once and dequeued once → O(V).
When u is dequeued, its neighbours are scanned once. With an adjacency list that is deg(u) cells. Over all vertices: deg(v₁) + deg(v₂) + … = 2E (handshake lemma) → O(E).
With a matrix, scanning row u costs n cells every time: n × n → O(V²).
Space: visited[] and the queue, each at most V → O(V).

T(BFS) = O(V) + O(deg(v₁) + … + deg(vₙ)) = O(V + E)

What BFS gives you

Shortest hop path

The level of v = the fewest edges from s to v. Follow parent[] back to s to print that path.

BFS spanning tree

Edges used to discover new vertices. Short and wide.

Connected or not

One BFS from s visits everyone ⇔ the graph is connected. Count restarts = number of components.

Level rule

In an undirected graph every non-tree edge joins two vertices whose levels differ by at most 1.

Where BFS is used

Fewest moves

Shortest route in an unweighted map, fewest flight changes, fewest moves in a puzzle.

Social networks

Friends (level 1), friends of friends (level 2) — “people you may know”.

Web crawlers

Visit a page, then every page it links to, level by level.

Networks

Broadcasting a message to all computers; peer-to-peer search.

Bipartite check

Colour levels alternately; an edge inside one level means an odd cycle.

Components

Find and count the separate pieces of a graph.

5.3BFS — examples

Choose an example from the dropdown, or type your own graph. Then use the tabs: Watch the animation, read every step with the queue drawn, copy the exam table, check the matrix, see the levels and BFS tree, and see what the C program prints for this exact graph.

5.4BFS — programs in C

All programs read the same input: number of vertices, number of edges, the edges (u v), the start vertex. Vertices are numbered 0 to n−1. Pick a program from the dropdown. Every program here was compiled with gcc -Wall and run on the input shown; the screen below each one is its real output.

Exam answerThe program to write in the exam and in the lab. One matrix, one array used as a queue, one visited[] array.

Key lines

q[++r] = start; — enqueue: move r (rear) forward and store the vertex.
u = q[f++]; — dequeue: read the front, then move f (front) forward.
while (f <= r) — the queue is not empty while front has not passed rear.
visited[i] = 1; comes just before q[++r] = i; — mark on enqueue.
for (i = 0; i < n; i++) scans row u, so neighbours come in number order.

/* BFS of an undirected graph using a queue */
#include <stdio.h>
#define MAX 20

int adj[MAX][MAX];
int visited[MAX];
int n;

void bfs(int start) {
    int q[MAX], f = 0, r = -1;
    int i, u;

    for (i = 0; i < n; i++)
        visited[i] = 0;

    visited[start] = 1;
    q[++r] = start;

    while (f <= r) {
        u = q[f++];
        printf("%d ", u);
        for (i = 0; i < n; i++) {
            if (adj[u][i] == 1 && visited[i] == 0) {
                visited[i] = 1;
                q[++r] = i;
            }
        }
    }
}

int main() {
    int e, i, j, u, v, start;

    printf("Enter number of vertices: ");
    scanf("%d", &n);

    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            adj[i][j] = 0;

    printf("Enter number of edges: ");
    scanf("%d", &e);

    printf("Enter %d edges (u v):\n", e);
    for (i = 0; i < e; i++) {
        scanf("%d %d", &u, &v);
        adj[u][v] = 1;
        adj[v][u] = 1;
    }

    printf("Enter start vertex: ");
    scanf("%d", &start);

    printf("\nBFS Traversal: ");
    bfs(start);
    printf("\n");
    return 0;
}

Sample run · what you type is highlighted

Enter number of vertices: 4
Enter number of edges: 4
Enter 4 edges (u v):
0 1
0 2
1 3
2 3
Enter start vertex: 0

BFS Traversal: 0 1 2 3

Same BFS, but each vertex keeps a linked list of only its real neighbours. The loop visits deg(u) nodes instead of n cells, so the time is O(V + E).

Key lines

struct node — one neighbour plus a pointer to the next one.
insert() keeps each list in increasing order, so the answer matches the matrix program.
for (p = head[u]; p != NULL; p = p->next) — walk only the real neighbours of u.
The program prints the adjacency list first, then BFS, and frees every node at the end.

/* BFS using an adjacency list (array of linked lists). Time O(V + E). */
#include <stdio.h>
#include <stdlib.h>
#define MAX 20

struct node {
    int vertex;
    struct node *next;
};

struct node *head[MAX];     /* head[u] points to the first neighbour of u */
int visited[MAX];
int n;

/* put v in the list of u, keeping the list in increasing order */
void insert(int u, int v) {
    struct node *t, *p;
    t = (struct node *)malloc(sizeof(struct node));
    t->vertex = v;
    t->next = NULL;
    if (head[u] == NULL || v < head[u]->vertex) {   /* v becomes the first node */
        t->next = head[u];
        head[u] = t;
        return;
    }
    p = head[u];
    while (p->next != NULL && p->next->vertex < v)
        p = p->next;
    t->next = p->next;
    p->next = t;
}

void display() {
    int i;
    struct node *p;
    printf("\nAdjacency list:\n");
    for (i = 0; i < n; i++) {
        printf("%d", i);
        for (p = head[i]; p != NULL; p = p->next)
            printf(" -> %d", p->vertex);
        printf(" -> NULL\n");
    }
}

void bfs(int start) {
    int q[MAX], f = 0, r = -1, u;
    struct node *p;

    visited[start] = 1;
    q[++r] = start;

    while (f <= r) {
        u = q[f++];
        printf("%d ", u);
        for (p = head[u]; p != NULL; p = p->next) {   /* only real neighbours */
            if (visited[p->vertex] == 0) {
                visited[p->vertex] = 1;
                q[++r] = p->vertex;
            }
        }
    }
}

int main() {
    int e, i, u, v, start;
    struct node *p, *t;

    printf("Enter number of vertices: ");
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        head[i] = NULL;
        visited[i] = 0;
    }

    printf("Enter number of edges: ");
    scanf("%d", &e);

    printf("Enter %d edges (u v):\n", e);
    for (i = 0; i < e; i++) {
        scanf("%d %d", &u, &v);
        insert(u, v);
        insert(v, u);
    }

    printf("Enter start vertex: ");
    scanf("%d", &start);

    display();
    printf("\nBFS Traversal: ");
    bfs(start);
    printf("\n");

    for (i = 0; i < n; i++) {           /* free every node */
        p = head[i];
        while (p != NULL) {
            t = p;
            p = p->next;
            free(t);
        }
    }
    return 0;
}

Sample run · what you type is highlighted

Enter number of vertices: 8
Enter number of edges: 10
Enter 10 edges (u v):
0 1
0 2
1 3
1 4
2 5
2 6
3 7
4 7
5 7
6 7
Enter start vertex: 0

Adjacency list:
0 -> 1 -> 2 -> NULL
1 -> 0 -> 3 -> 4 -> NULL
2 -> 0 -> 5 -> 6 -> NULL
3 -> 1 -> 7 -> NULL
4 -> 1 -> 7 -> NULL
5 -> 2 -> 7 -> NULL
6 -> 2 -> 7 -> NULL
7 -> 3 -> 4 -> 5 -> 6 -> NULL

BFS Traversal: 0 1 2 3 4 5 6 7

BFS reaches vertices in order of distance. Store the level and the parent of each vertex, and you get the fewest-edges path from the start to every vertex.

Key lines

level[i] = level[u] + 1; — i is one edge further than u.
parent[i] = u; — remember who found i.
printPath(v) follows parent[] back to the start (recursion), then prints on the way back, so the path comes out start → v.
-1 means “not reached”, so unreachable vertices are reported.

/* BFS gives the fewest-edges path from the start to every vertex */
#include <stdio.h>
#define MAX 20

int adj[MAX][MAX];
int visited[MAX], level[MAX], parent[MAX];
int n;

void bfs(int start) {
    int q[MAX], f = 0, r = -1;
    int i, u;

    for (i = 0; i < n; i++) {
        visited[i] = 0;
        level[i] = -1;          /* -1 means not reached */
        parent[i] = -1;
    }

    visited[start] = 1;
    level[start] = 0;
    q[++r] = start;

    while (f <= r) {
        u = q[f++];
        printf("%d ", u);
        for (i = 0; i < n; i++) {
            if (adj[u][i] == 1 && visited[i] == 0) {
                visited[i] = 1;
                level[i] = level[u] + 1;   /* one edge further than u */
                parent[i] = u;             /* i was reached from u */
                q[++r] = i;
            }
        }
    }
}

/* print start -> ... -> v by walking parent[] back to the start */
void printPath(int v) {
    if (parent[v] == -1) {
        printf("%d", v);
        return;
    }
    printPath(parent[v]);
    printf(" -> %d", v);
}

int main() {
    int e, i, j, u, v, start;

    printf("Enter number of vertices: ");
    scanf("%d", &n);

    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            adj[i][j] = 0;

    printf("Enter number of edges: ");
    scanf("%d", &e);

    printf("Enter %d edges (u v):\n", e);
    for (i = 0; i < e; i++) {
        scanf("%d %d", &u, &v);
        adj[u][v] = 1;
        adj[v][u] = 1;
    }

    printf("Enter start vertex: ");
    scanf("%d", &start);

    printf("\nBFS Traversal: ");
    bfs(start);

    printf("\n\nVertex  Level  Parent  Shortest path\n");
    for (i = 0; i < n; i++) {
        printf("%-7d ", i);
        if (level[i] == -1) {
            printf("not reachable from %d\n", start);
            continue;
        }
        printf("%-6d ", level[i]);
        if (parent[i] == -1)
            printf("%-7s ", "-");
        else
            printf("%-7d ", parent[i]);
        printPath(i);
        printf("\n");
    }
    return 0;
}

Sample run · what you type is highlighted

Enter number of vertices: 8
Enter number of edges: 10
Enter 10 edges (u v):
0 1
0 2
1 3
1 4
2 5
2 6
3 7
4 7
5 7
6 7
Enter start vertex: 0

BFS Traversal: 0 1 2 3 4 5 6 7

Vertex  Level  Parent  Shortest path
0       0      -       0
1       1      0       0 -> 1
2       1      0       0 -> 2
3       2      1       0 -> 1 -> 3
4       2      1       0 -> 1 -> 4
5       2      2       0 -> 2 -> 5
6       2      2       0 -> 2 -> 6
7       3      3       0 -> 1 -> 3 -> 7

The simple program stops when the queue is empty. This one keeps going: every vertex that is still unvisited starts a new BFS, and the starts are counted.

Key lines

visited[] is cleared once in main, not inside bfs() — marks from earlier components must stay.
for (i = 0; i < n; i++) if (visited[i] == 0) — find the next unvisited vertex.
Number of BFS calls = number of components. 1 means the graph is connected.

/* BFS of a graph that may be disconnected: restart from every unvisited vertex */
#include <stdio.h>
#define MAX 20

int adj[MAX][MAX];
int visited[MAX];
int n;

void bfs(int start) {               /* visited[] is NOT reset here */
    int q[MAX], f = 0, r = -1;
    int i, u;

    visited[start] = 1;
    q[++r] = start;

    while (f <= r) {
        u = q[f++];
        printf("%d ", u);
        for (i = 0; i < n; i++) {
            if (adj[u][i] == 1 && visited[i] == 0) {
                visited[i] = 1;
                q[++r] = i;
            }
        }
    }
}

int main() {
    int e, i, j, u, v, start, count;

    printf("Enter number of vertices: ");
    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        visited[i] = 0;
        for (j = 0; j < n; j++)
            adj[i][j] = 0;
    }

    printf("Enter number of edges: ");
    scanf("%d", &e);

    printf("Enter %d edges (u v):\n", e);
    for (i = 0; i < e; i++) {
        scanf("%d %d", &u, &v);
        adj[u][v] = 1;
        adj[v][u] = 1;
    }

    printf("Enter start vertex: ");
    scanf("%d", &start);

    printf("\nBFS Traversal:\n");
    count = 1;
    printf("Component %d: ", count);
    bfs(start);

    for (i = 0; i < n; i++) {
        if (visited[i] == 0) {       /* not reached yet: a new component */
            count++;
            printf("\nComponent %d: ", count);
            bfs(i);
        }
    }

    printf("\n\nNumber of components = %d\n", count);
    return 0;
}

Sample run · what you type is highlighted

Enter number of vertices: 6
Enter number of edges: 4
Enter 4 edges (u v):
0 1
1 2
0 2
3 4
Enter start vertex: 0

BFS Traversal:
Component 1: 0 1 2
Component 2: 3 4
Component 3: 5

Number of components = 3

Compile and run

gcc bfs_matrix.c -o bfs
./bfs          (Windows: bfs.exe)

5.5DFS — idea and algorithm (recursion)

Definition

Depth First Search (DFS) goes as deep as possible along one path, then backtracks to the last vertex that still has an unvisited neighbour. It is written as a recursive function dfs(u) that calls itself, with a visited[] array.

Picture it

You walk through a maze. At every junction take the first unused road and keep going. At a dead end, walk back to the last junction that still has an unused road. In the program, “keep going” is a new call dfs(v), and “walk back” is that call returning.

Complete algorithm (recursive)

DFS(u)
1. visited[u] = 1
   print u
2. For every neighbour v of u, in order:
       If visited[v] == 0:
           DFS(v)             // go deeper; u waits here
3. Return                     // u is finished → backtrack

MAIN
1. For every vertex v:  visited[v] = 0
2. DFS(s)                     // first call
3. If some vertex is still unvisited (disconnected graph),
   call DFS on it too.

Recursion in three ideas

1 · Call = go deeper

dfs(u) finds an unvisited neighbour v and calls dfs(v). dfs(u) stops at that line and waits.

2 · Return = backtrack

When dfs(v) has no unvisited neighbour left, its loop ends and it returns. Control comes back to dfs(u), to the same line.

3 · Continue the loop

dfs(u) goes on with its next neighbour. When its own loop ends, dfs(u) returns too.

Line by line — why each line is there

Line of the C program	What it does	Why it is needed
`visited[u] = 1;` `printf("%d ", u);`	We reached u for the first time.	Mark first, so a cycle can never bring us back to u.
`for (i = 0; i < n; i++)`	Look at every vertex i, in order 0 … n−1.	The order decides the answer (row u of the matrix).
`if (adj[u][i] == 1 && visited[i] == 0)`	Only a real, new neighbour.	Without the visited check the function calls itself round a cycle for ever (stack overflow).
`dfs(i);`	The function calls itself on i.	This is “depth first”: i is explored completely before u looks at its next neighbour. u’s loop waits here.
closing `}` of `dfs`	The function ends = return.	Backtrack: the caller continues its loop with the next i.
`main`: `visited[i] = 0;` then `dfs(start);`	The first call.	After BFS, reset `visited[]` or DFS prints nothing.

How the recursion runs — call by call

Practical graph 0–1, 0–2, 1–3, 2–3, start 0. Each call of dfs() gets its own u and i. The calls that have started but not finished wait in the call stack: a new call goes on top, a returning call leaves the top.

#	What happens	Call stack after bottom … top	Output
1	main calls dfs(0). Mark 0, print 0.	dfs(0)	0
2	In dfs(0): i = 1 is unvisited → call dfs(1). dfs(0) waits.	dfs(0) dfs(1)	0 1
3	In dfs(1): 0 is visited → skip. 3 is unvisited → call dfs(3).	dfs(0) dfs(1) dfs(3)	0 1 3
4	In dfs(3): 1 is visited → skip. 2 is unvisited → call dfs(2).	dfs(0) dfs(1) dfs(3) dfs(2)	0 1 3 2
5	In dfs(2): 0 and 3 are visited. Loop ends → dfs(2) returns.	dfs(0) dfs(1) dfs(3)	0 1 3 2
6	Back in dfs(3): no more neighbours → dfs(3) returns.	dfs(0) dfs(1)	0 1 3 2
7	Back in dfs(1): no more neighbours → dfs(1) returns.	dfs(0)	0 1 3 2
8	Back in dfs(0): i = 2 is already visited → skip. Loop ends → dfs(0) returns to main.	empty	0 1 3 2

How to draw the call stack on paper — at step 4, the deepest point

dfs(0)

dfs(1)

dfs(3)

dfs(2)← running now

One box per call that has not finished. The top box is the call running now; every box below it is waiting at its dfs(i); line. A return removes the top box. You never write this stack in the program — the computer keeps it.

Every term in the algorithm

Term	Meaning
Recursion	A function that calls itself: `dfs(u)` calls `dfs(v)`.
Call	`dfs(v)` starts — go one step deeper.
Return	`dfs(v)` ends — control goes back to the call that made it.
Backtrack	After a return, the caller continues with its next neighbour.
Call stack	The calls that have started but not finished. The top one is running; the others wait.
Stopping point	There is no separate base case: a call stops when its loop finds no unvisited neighbour.
Parent	The vertex whose call started `dfs(v)`. Parent → v is a tree edge.
Depth	How many calls are on the call stack. At most V.
Discovery time d[u]	The clock value when `dfs(u)` starts.
Finish time f[u]	The clock value when `dfs(u)` returns — all its neighbours are done.
White / grey / black	Not visited / its call is still on the call stack / its call has returned.
Time / space	O(V + E) list, O(V²) matrix. Call-stack depth = length of the deepest path (up to V).

Reset visited[] to 0 before DFS if you just ran BFS. Otherwise DFS prints only the start vertex. And never call dfs(i) without the visited[i] == 0 check — the recursion would never stop on a cycle.

Edge types in DFS

Edge u → v	When	Meaning
Tree edge	v is white (new)	`dfs(u)` calls `dfs(v)` through this edge. These edges form the DFS tree.
Back edge	v is grey (its call is still on the call stack — an ancestor)	Closes a cycle. No back edge ⇔ no cycle.
Forward edge (directed only)	v is black and d[v] > d[u]	A shortcut down to a finished descendant.
Cross edge (directed only)	v is black and d[v] < d[u]	Goes to another, already finished branch.

In an undirected graph only tree edges and back edges appear. The times also nest like brackets: for any two vertices, either one interval [d, f] sits completely inside the other (ancestor and descendant), or they do not overlap at all.

Time and space

Each vertex gets exactly one dfs() call → O(V). Each call scans the neighbours of its vertex once → total O(E) with a list. So O(V + E).
With a matrix each call scans a full row of n cells → O(V²).
Space: visited[] plus the call stack. On a long path every call waits on the stack → O(V).

Where DFS is used

Cycle detection

A back edge means a cycle (deadlock checks, dependency loops).

Topological sort

List vertices by decreasing finish time — task and course order.

Path finding / mazes

Is there a path from s to t? Follow one road to the end.

Components

Count the pieces; strongly connected components (Kosaraju).

Bridges & cut vertices

Weak links in a network, found with d[] and low[].

Backtracking

Sudoku, N-queens, puzzles: try, go deeper, undo.

Extra — DFS without recursion (explicit stack)

Only if the question asks for a non-recursive DFS. Everything above is the recursive DFS; this box is a separate method. Here your own array replaces the call stack.

DFS_STACK(s)
1. PUSH(s)
2. While the stack is not empty:
     u = POP()                // take the top
     If visited[u] == 1: skip // an old copy
     visited[u] = 1
     print u
     PUSH the unvisited neighbours of u
       in REVERSE order (smallest ends on top)
3. Stop. Printed list = DFS order.

Reverse push: neighbours of 0 are 1 then 2. Push 2 first, then 1, so 1 is on top and comes out first — the same order as the recursive program.
Skip: a vertex can be pushed twice (by two neighbours). Only the first pop counts.
The order printed is the same as the recursive DFS. Program: “Extra: DFS without recursion” in the dropdown of 5.7.

5.6DFS — examples

Everything here follows the recursive program: the player, the step cards and the exam table show every dfs() call and every return, with the call stack drawn. Extra tabs: Recursion trace (every line the program runs) and Times & edge types (discovery/finish times, back edges, cycle check).

5.7DFS — programs in C

Exam question

Define Graph? Write a C Program to display BFS Traversal and DFS Traversal of a graph.

Definition (write this first)

A graph G is a pair of two finite sets, G = (V, E), where V is a non-empty set of vertices and E is a set of edges. Each edge is a pair of vertices.

The first program in the dropdown is the answer to this question: the BFS program plus a recursive dfs. After BFS, reset visited[], then call dfs. The other programs show DFS in other ways. Same input format as 5.4.

Exam answerThe answer to “Write a C program to display BFS and DFS traversal”. The BFS function from 5.4 plus a recursive dfs.

Key lines

dfs(u) marks u, prints it, then calls itself on the first unvisited neighbour — recursion is the stack.
Between the two traversals, visited[] is reset to 0. Without this DFS prints nothing.
Both functions scan the matrix row in order 0 … n−1, so the answer matches the hand trace.

/* Define Graph. Display BFS and DFS of an undirected graph. */
#include <stdio.h>
#define MAX 20

int adj[MAX][MAX];
int visited[MAX];
int n;

void bfs(int start) {
    int q[MAX], f = 0, r = -1;
    int i, u;

    for (i = 0; i < n; i++)
        visited[i] = 0;

    visited[start] = 1;
    q[++r] = start;

    while (f <= r) {
        u = q[f++];
        printf("%d ", u);
        for (i = 0; i < n; i++) {
            if (adj[u][i] == 1 && visited[i] == 0) {
                visited[i] = 1;
                q[++r] = i;
            }
        }
    }
}

void dfs(int u) {
    int i;
    visited[u] = 1;
    printf("%d ", u);
    for (i = 0; i < n; i++) {
        if (adj[u][i] == 1 && visited[i] == 0)
            dfs(i);
    }
}

int main() {
    int e, i, j, u, v, start;

    printf("Enter number of vertices: ");
    scanf("%d", &n);

    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            adj[i][j] = 0;

    printf("Enter number of edges: ");
    scanf("%d", &e);

    printf("Enter %d edges (u v):\n", e);
    for (i = 0; i < e; i++) {
        scanf("%d %d", &u, &v);
        adj[u][v] = 1;
        adj[v][u] = 1;
    }

    printf("Enter start vertex: ");
    scanf("%d", &start);

    printf("\nBFS Traversal: ");
    bfs(start);

    for (i = 0; i < n; i++)
        visited[i] = 0;

    printf("\nDFS Traversal: ");
    dfs(start);
    printf("\n");
    return 0;
}

Sample run · what you type is highlighted

Enter number of vertices: 4
Enter number of edges: 4
Enter 4 edges (u v):
0 1
0 2
1 3
2 3
Enter start vertex: 0

BFS Traversal: 0 1 2 3
DFS Traversal: 0 1 3 2

The shortest DFS program: one recursive function. Each dfs(i) call goes one step deeper; each return is a backtrack.

Key lines

visited[u] = 1; first, so a cycle can never bring us back to u.
dfs(i); inside the loop — go deeper at once; u waits on the call stack.
When a call returns, the loop of the caller continues with its next neighbour — that is backtracking.

/* DFS (recursive) of an undirected graph using an adjacency matrix */
#include <stdio.h>
#define MAX 20

int adj[MAX][MAX];
int visited[MAX];
int n;

void dfs(int u) {
    int i;
    visited[u] = 1;                  /* mark */
    printf("%d ", u);                /* print */
    for (i = 0; i < n; i++) {        /* neighbours in order 0, 1, 2 ... */
        if (adj[u][i] == 1 && visited[i] == 0)
            dfs(i);                  /* go deeper; coming back here = backtrack */
    }
}

int main() {
    int e, i, j, u, v, start;

    printf("Enter number of vertices: ");
    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        visited[i] = 0;
        for (j = 0; j < n; j++)
            adj[i][j] = 0;
    }

    printf("Enter number of edges: ");
    scanf("%d", &e);

    printf("Enter %d edges (u v):\n", e);
    for (i = 0; i < e; i++) {
        scanf("%d %d", &u, &v);
        adj[u][v] = 1;
        adj[v][u] = 1;
    }

    printf("Enter start vertex: ");
    scanf("%d", &start);

    printf("\nDFS Traversal: ");
    dfs(start);
    printf("\n");
    return 0;
}

Sample run · what you type is highlighted

Enter number of vertices: 8
Enter number of edges: 10
Enter 10 edges (u v):
0 1
0 2
1 3
1 4
2 5
2 6
3 7
4 7
5 7
6 7
Enter start vertex: 0

DFS Traversal: 0 1 3 7 4 5 2 6

Recursive DFS on linked lists. Each call walks only the real neighbours, so the time is O(V + E).

Key lines

Same insert() and display() as the BFS list program.
for (p = head[u]; p != NULL; p = p->next) replaces the scan of a matrix row.

/* DFS using an adjacency list (array of linked lists). Time O(V + E). */
#include <stdio.h>
#include <stdlib.h>
#define MAX 20

struct node {
    int vertex;
    struct node *next;
};

struct node *head[MAX];     /* head[u] points to the first neighbour of u */
int visited[MAX];
int n;

/* put v in the list of u, keeping the list in increasing order */
void insert(int u, int v) {
    struct node *t, *p;
    t = (struct node *)malloc(sizeof(struct node));
    t->vertex = v;
    t->next = NULL;
    if (head[u] == NULL || v < head[u]->vertex) {   /* v becomes the first node */
        t->next = head[u];
        head[u] = t;
        return;
    }
    p = head[u];
    while (p->next != NULL && p->next->vertex < v)
        p = p->next;
    t->next = p->next;
    p->next = t;
}

void display() {
    int i;
    struct node *p;
    printf("\nAdjacency list:\n");
    for (i = 0; i < n; i++) {
        printf("%d", i);
        for (p = head[i]; p != NULL; p = p->next)
            printf(" -> %d", p->vertex);
        printf(" -> NULL\n");
    }
}

void dfs(int u) {
    struct node *p;
    visited[u] = 1;
    printf("%d ", u);
    for (p = head[u]; p != NULL; p = p->next) {     /* only real neighbours */
        if (visited[p->vertex] == 0)
            dfs(p->vertex);
    }
}

int main() {
    int e, i, u, v, start;
    struct node *p, *t;

    printf("Enter number of vertices: ");
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        head[i] = NULL;
        visited[i] = 0;
    }

    printf("Enter number of edges: ");
    scanf("%d", &e);

    printf("Enter %d edges (u v):\n", e);
    for (i = 0; i < e; i++) {
        scanf("%d %d", &u, &v);
        insert(u, v);
        insert(v, u);
    }

    printf("Enter start vertex: ");
    scanf("%d", &start);

    display();
    printf("\nDFS Traversal: ");
    dfs(start);
    printf("\n");

    for (i = 0; i < n; i++) {           /* free every node */
        p = head[i];
        while (p != NULL) {
            t = p;
            p = p->next;
            free(t);
        }
    }
    return 0;
}

Sample run · what you type is highlighted

Enter number of vertices: 8
Enter number of edges: 10
Enter 10 edges (u v):
0 1
0 2
1 3
1 4
2 5
2 6
3 7
4 7
5 7
6 7
Enter start vertex: 0

Adjacency list:
0 -> 1 -> 2 -> NULL
1 -> 0 -> 3 -> 4 -> NULL
2 -> 0 -> 5 -> 6 -> NULL
3 -> 1 -> 7 -> NULL
4 -> 1 -> 7 -> NULL
5 -> 2 -> 7 -> NULL
6 -> 2 -> 7 -> NULL
7 -> 3 -> 4 -> 5 -> 6 -> NULL

DFS Traversal: 0 1 3 7 4 5 2 6

DFS with a clock: d[u] when u is reached, f[u] when its call returns. It also reports whether the graph has a cycle.

Key lines

d[u] = ++t; at the start of the call, f[u] = ++t; at the end.
parent[i] = u; before going deeper, to remember the tree edge.
A neighbour that is already visited and is not the parent means a cycle (a back edge).
The sample graph has 10 edges and 8 vertices, so it must have cycles: Cycle: YES.

/* DFS with discovery / finish times and a cycle check (undirected graph) */
#include <stdio.h>
#define MAX 20

int adj[MAX][MAX];
int visited[MAX], parent[MAX];
int d[MAX], f[MAX];      /* discovery time, finish time */
int n, t = 0, cycle = 0;

void dfs(int u) {
    int i;
    visited[u] = 1;
    d[u] = ++t;                      /* first time we reach u */
    printf("%d ", u);
    for (i = 0; i < n; i++) {
        if (adj[u][i] == 1 && visited[i] == 0) {
            parent[i] = u;
            dfs(i);
        } else if (adj[u][i] == 1 && i != parent[u]) {
            cycle = 1;               /* visited and not the parent: a cycle */
        }
    }
    f[u] = ++t;                      /* all neighbours of u are done */
}

int main() {
    int e, i, j, u, v, start;

    printf("Enter number of vertices: ");
    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        visited[i] = 0;
        parent[i] = -1;
        for (j = 0; j < n; j++)
            adj[i][j] = 0;
    }

    printf("Enter number of edges: ");
    scanf("%d", &e);

    printf("Enter %d edges (u v):\n", e);
    for (i = 0; i < e; i++) {
        scanf("%d %d", &u, &v);
        adj[u][v] = 1;
        adj[v][u] = 1;
    }

    printf("Enter start vertex: ");
    scanf("%d", &start);

    printf("\nDFS Traversal: ");
    dfs(start);

    printf("\n\nVertex  Disc  Finish  Parent\n");
    for (i = 0; i < n; i++) {
        if (visited[i] == 0) {
            printf("%-7d not reached\n", i);
            continue;
        }
        printf("%-7d %-5d %-7d ", i, d[i], f[i]);
        if (parent[i] == -1)
            printf("-\n");
        else
            printf("%d\n", parent[i]);
    }

    if (cycle == 1)
        printf("\nCycle: YES\n");
    else
        printf("\nCycle: NO\n");
    return 0;
}

Sample run · what you type is highlighted

Enter number of vertices: 8
Enter number of edges: 10
Enter 10 edges (u v):
0 1
0 2
1 3
1 4
2 5
2 6
3 7
4 7
5 7
6 7
Enter start vertex: 0

DFS Traversal: 0 1 3 7 4 5 2 6

Vertex  Disc  Finish  Parent
0       1     16      -
1       2     15      0
2       8     11      5
3       3     14      1
4       5     6       7
5       7     12      7
6       9     10      2
7       4     13      3

Cycle: YES

DFS from every unvisited vertex. Prints each component on its own line and says whether the graph is connected.

Key lines

visited[] is cleared once in main, never inside dfs().
Each new dfs(i) call from main = one more component.

/* DFS of a graph that may be disconnected: count the components */
#include <stdio.h>
#define MAX 20

int adj[MAX][MAX];
int visited[MAX];
int n;

void dfs(int u) {
    int i;
    visited[u] = 1;
    printf("%d ", u);
    for (i = 0; i < n; i++) {
        if (adj[u][i] == 1 && visited[i] == 0)
            dfs(i);
    }
}

int main() {
    int e, i, j, u, v, start, count;

    printf("Enter number of vertices: ");
    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        visited[i] = 0;
        for (j = 0; j < n; j++)
            adj[i][j] = 0;
    }

    printf("Enter number of edges: ");
    scanf("%d", &e);

    printf("Enter %d edges (u v):\n", e);
    for (i = 0; i < e; i++) {
        scanf("%d %d", &u, &v);
        adj[u][v] = 1;
        adj[v][u] = 1;
    }

    printf("Enter start vertex: ");
    scanf("%d", &start);

    printf("\nDFS Traversal:\n");
    count = 1;
    printf("Component %d: ", count);
    dfs(start);

    for (i = 0; i < n; i++) {
        if (visited[i] == 0) {       /* not reached yet: a new component */
            count++;
            printf("\nComponent %d: ", count);
            dfs(i);
        }
    }

    printf("\n\nNumber of components = %d\n", count);
    printf("Connected graph: %s\n", count == 1 ? "YES" : "NO");
    return 0;
}

Sample run · what you type is highlighted

Enter number of vertices: 6
Enter number of edges: 4
Enter 4 edges (u v):
0 1
1 2
0 2
3 4
Enter start vertex: 0

DFS Traversal:
Component 1: 0 1 2
Component 2: 3 4
Component 3: 5

Number of components = 3
Connected graph: NO

Only when a non-recursive DFS is asked. Our own array replaces the call stack; the order printed is the same as the recursive program.

Key lines

stack[++top] = start; — push. u = stack[top--]; — pop.
if (visited[u] == 1) continue; — a vertex can be pushed twice; skip the old copy.
for (i = n - 1; i >= 0; i--) — push in reverse so the smallest neighbour is on top.
The stack size is MAX * MAX because of the repeated pushes.

/* DFS without recursion: our own stack does the work of the call stack */
#include <stdio.h>
#define MAX 20

int adj[MAX][MAX];
int visited[MAX];
int n;

void dfs(int start) {
    int stack[MAX * MAX], top = -1;  /* a vertex can be pushed more than once */
    int i, u;

    stack[++top] = start;            /* PUSH start */

    while (top >= 0) {
        u = stack[top--];            /* POP the top */
        if (visited[u] == 1)
            continue;                /* an old copy: skip it */
        visited[u] = 1;
        printf("%d ", u);
        for (i = n - 1; i >= 0; i--) {         /* push in REVERSE order */
            if (adj[u][i] == 1 && visited[i] == 0)
                stack[++top] = i;              /* so the smallest is on top */
        }
    }
}

int main() {
    int e, i, j, u, v, start;

    printf("Enter number of vertices: ");
    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        visited[i] = 0;
        for (j = 0; j < n; j++)
            adj[i][j] = 0;
    }

    printf("Enter number of edges: ");
    scanf("%d", &e);

    printf("Enter %d edges (u v):\n", e);
    for (i = 0; i < e; i++) {
        scanf("%d %d", &u, &v);
        adj[u][v] = 1;
        adj[v][u] = 1;
    }

    printf("Enter start vertex: ");
    scanf("%d", &start);

    printf("\nDFS Traversal: ");
    dfs(start);
    printf("\n");
    return 0;
}

Sample run · what you type is highlighted

Enter number of vertices: 8
Enter number of edges: 10
Enter 10 edges (u v):
0 1
0 2
1 3
1 4
2 5
2 6
3 7
4 7
5 7
6 7
Enter start vertex: 0

DFS Traversal: 0 1 3 7 4 5 2 6

5.8BFS vs DFS

	BFS	DFS
Full form	Breadth First Search	Depth First Search
Idea	Level by level (wide first)	One path to the end, then backtrack
Data structure	Queue — FIFO (front out, rear in)	Recursion — the call stack (LIFO). Without recursion: your own stack
Mark visited	On enqueue	On first visit / print
Practical graph from 0	0 1 2 3	0 1 3 2
Textbook 8-vertex graph from 1	1 2 3 4 5 6 7 8	1 2 4 8 5 6 3 7
Tree shape	Short and wide	Long and thin
Shortest hop-path	Yes	No
Memory	Queue may hold a whole level (big for wide graphs)	Call stack holds one path (big for deep graphs)
Time (list / matrix)	O(V + E) / O(V²)	O(V + E) / O(V²)
On a tree it is	Level-order traversal	Pre-order traversal
Cycle	Possible (non-tree edge in undirected graph)	Back edge — the standard method
Typical uses	Shortest path, levels, bipartite check, broadcast	Cycle check, topological sort, SCC, bridges, mazes
Disconnected	Restart from any unvisited vertex	Same

Pick BFS for fewest hops. Pick DFS for a path to the end or a cycle. Only “visit everyone” → either.

5.9Your turn — practice

Get a random graph (or pick one), write the BFS or DFS order, and press Check. If something is wrong you see the first wrong position and the reason — what was in the queue, or where DFS should have backtracked. Letters can be typed with or without spaces.

5.10Exam corner

How to write a 6-mark BFS / DFS answer

Definition in one line, and the data structure (BFS: queue · DFS: recursion / call stack).
Algorithm in steps (5.2 or 5.5).
Draw the graph and write the adjacency list — this fixes the neighbour order.
The trace table: step, what happens (dequeue / call / return), queue or call stack after, output so far (the Exam table tab).
Box the final answer with the start vertex: “BFS from A = A B C D E F G”.
Write the complexity: O(V + E) with a list, O(V²) with a matrix.

Q1Find BFS and DFS of the graph 1–2, 1–3, 2–4, 2–5, 3–6, 3–7, 4–8, 5–8, 6–8, 7–8 starting from 1.

BFS: queue 1 → 2 3 → 3 4 5 → 4 5 6 7 → 5 6 7 8 → … Answer 1 2 3 4 5 6 7 8.

DFS: dfs(1) calls dfs(2), which calls dfs(4), which calls dfs(8). dfs(8) calls dfs(5) — a dead end, so dfs(5) returns to dfs(8). dfs(8) then calls dfs(6), dfs(6) calls dfs(3), dfs(3) calls dfs(7). Answer 1 2 4 8 5 6 3 7.

Open “Textbook 8-vertex graph” in the dropdowns of 5.3 and 5.6 for the full tables.

Q2Differentiate between BFS and DFS (any six points).

Use the table in 5.8: idea, data structure, marking, shortest path, memory, tree shape, uses, time. Add one small graph with both orders.

Q3Why do we need the visited[] array? What happens without it?

A graph can have cycles. Without visited[], BFS keeps putting the same vertices in the queue and DFS keeps calling itself round the cycle — the program never stops (or overflows the stack). visited[] makes sure each vertex is processed exactly once.

Q4How can BFS or DFS tell whether a graph is connected? How many components does it have?

Run BFS/DFS once from any vertex. If every vertex is visited, the graph is connected. Otherwise restart from each unvisited vertex; the number of starts = the number of components. See the “every component” programs in 5.4 and 5.7.

Q5Is the BFS / DFS order of a graph unique?

No. It depends on the start vertex and on the order in which neighbours are taken. That is why the answer must state both, e.g. “from A, neighbours in alphabetical order”.

Q6How does DFS detect a cycle?

Keep the vertex colours. Reaching a grey vertex (its call is still on the call stack) through an edge that is not the one we came by is a back edge, and a back edge closes a cycle. The program “DFS — times and cycle check” in 5.7 does exactly this.

Remember

BFS = queue, level by level, mark on enqueue, gives fewest-edges paths.
DFS = recursion: call dfs on the first unvisited neighbour; a return is a backtrack. The call stack holds the current path.
Practical graph from 0: BFS 0 1 2 3, DFS 0 1 3 2.
Both are O(V + E) with a list and O(V²) with a matrix.
After BFS, reset visited[] before DFS. Unvisited vertices left at the end → restart (disconnected graph).

Unit V · Part 6 Advanced

MST, Shortest Path and Topological Sort

The algorithms that run inside maps, networks and build tools. Each one is a small change to BFS or DFS — see exactly where with the step players.

Beyond the core syllabus: spanning trees, Prim's and Kruskal's MST, Dijkstra's shortest path, topological sort. Commonly asked in university exams and placement interviews.

6.1Spanning tree and minimum spanning tree

Definition

A spanning tree of a connected graph G is a subgraph that includes every vertex of G and is a tree (connected, no cycle). It always has n − 1 edges. A minimum spanning tree (MST) is a spanning tree whose total edge weight is as small as possible.

In simple words

You must lay cables to connect 7 villages. Every village must be reachable, and cable is expensive. The MST tells you which roads to lay cable along so that the total cable length is the least.

A connected graph with n vertices can have many spanning trees. K_n has nⁿ⁻² of them (Cayley's formula): K₄ has 16.
Adding any one more edge to a spanning tree creates exactly one cycle. Removing any edge disconnects it.
If all edge weights are different, the MST is unique.
Both algorithms below are greedy: they always take the cheapest safe edge and never undo a choice.

6.2Prim's algorithm

Idea: grow one tree. Start from any vertex. At every step add the cheapest edge that joins a tree vertex to a non-tree vertex. It is BFS with a priority instead of a plain queue.

PRIM(G, s)
1. key[v] = ∞, parent[v] = NIL, inTree[v] = 0 for every v
2. key[s] = 0
3. Repeat n times:
     u = vertex with inTree[u] = 0 and the smallest key[u]
     inTree[u] = 1                  // add u (and edge parent[u]–u) to the MST
     For every neighbour v of u with inTree[v] = 0:
         If w(u, v) < key[v]:
             key[v] = w(u, v);  parent[v] = u

Order of edges added: A–D (5), D–F (6), A–B (7), B–E (7), E–C (5), E–G (9). Total = 39. Note that Prim can add a cheap edge (E–C, 5) late, because C was not reachable cheaply until E joined the tree.

Program 5 — Prim's MST (adjacency matrix, O(n²))

/* Prim's minimum spanning tree, O(n^2) with an adjacency matrix */
#include <stdio.h>
#include <limits.h>
#define MAX 20

int cost[MAX][MAX];     /* 0 = no edge */
int n;

void prim(int start) {
    int key[MAX], parent[MAX], inTree[MAX];
    int i, k, u, v, total = 0;
    for (i = 0; i < n; i++) {
        key[i] = INT_MAX;
        parent[i] = -1;
        inTree[i] = 0;
    }
    key[start] = 0;
    printf("\nEdge   Weight\n");
    for (k = 0; k < n; k++) {
        u = -1;                                   /* pick the smallest key */
        for (i = 0; i < n; i++)
            if (!inTree[i] && key[i] != INT_MAX && (u == -1 || key[i] < key[u]))
                u = i;
        if (u == -1) { printf("Graph is not connected\n"); return; }
        inTree[u] = 1;
        if (parent[u] != -1) {
            printf("%c - %c   %d\n", 'A' + parent[u], 'A' + u, cost[parent[u]][u]);
            total += cost[parent[u]][u];
        }
        for (v = 0; v < n; v++)                   /* update keys of neighbours */
            if (cost[u][v] && !inTree[v] && cost[u][v] < key[v]) {
                key[v] = cost[u][v];
                parent[v] = u;
            }
    }
    printf("Total weight of MST = %d\n", total);
}

int main() {
    int e, i, w;
    char u, v, s;
    printf("Number of vertices: ");
    scanf("%d", &n);
    printf("Number of edges: ");
    scanf("%d", &e);
    for (i = 0; i < e; i++) {
        printf("Edge %d (u v weight): ", i + 1);
        scanf(" %c %c %d", &u, &v, &w);
        cost[u - 'A'][v - 'A'] = cost[v - 'A'][u - 'A'] = w;
    }
    printf("Start vertex: ");
    scanf(" %c", &s);
    prim(s - 'A');
    return 0;
}

Input (graph of 6.1)

7
11
A B 7
A D 5
B C 8
B D 9
B E 7
C E 5
D E 15
D F 6
E F 8
E G 9
F G 11
A

Output

Edge   Weight
A - D   5
D - F   6
A - B   7
B - E   7
E - C   5
E - G   9
Total weight of MST = 39

6.3Kruskal's algorithm

Idea: forget about growing one tree. Sort all edges from cheapest to costliest and take them one by one. Skip an edge if its two ends are already connected (it would make a cycle). Stop at n − 1 edges.

KRUSKAL(G)
1. Sort all edges by weight (smallest first)
2. Make a separate set for every vertex: {A} {B} {C} ...
3. For each edge (u, v) in sorted order:
     If FIND(u) ≠ FIND(v):          // different sets → no cycle
         add (u, v) to the MST
         UNION(u, v)
     Else: reject (cycle)
4. Stop when the MST has n − 1 edges.

The same graph gives the same total, 39, but the edges are picked in a different order: A–D, C–E, D–F, A–B, B–E, (reject B–C, E–F, B–D), E–G.

Program 6 — Kruskal's MST with union-find

/* Kruskal's minimum spanning tree with union-find */
#include <stdio.h>
#define MAX 50

struct edge { int u, v, w; };

struct edge E[MAX];
int parent[MAX];
int n, e;

int find(int x) {                         /* root of x's set (with path compression) */
    if (parent[x] != x)
        parent[x] = find(parent[x]);
    return parent[x];
}

void sortEdges() {                        /* simple bubble sort by weight */
    int i, j;
    struct edge t;
    for (i = 0; i < e - 1; i++)
        for (j = 0; j < e - 1 - i; j++)
            if (E[j].w > E[j + 1].w) { t = E[j]; E[j] = E[j + 1]; E[j + 1] = t; }
}

int main() {
    int i, taken = 0, total = 0, ru, rv;
    char a, b;
    printf("Number of vertices: ");
    scanf("%d", &n);
    printf("Number of edges: ");
    scanf("%d", &e);
    for (i = 0; i < e; i++) {
        printf("Edge %d (u v weight): ", i + 1);
        scanf(" %c %c %d", &a, &b, &E[i].w);
        E[i].u = a - 'A';
        E[i].v = b - 'A';
    }
    for (i = 0; i < n; i++) parent[i] = i;  /* every vertex is its own set */
    sortEdges();

    printf("\nEdge   Weight  Result\n");
    for (i = 0; i < e && taken < n - 1; i++) {
        ru = find(E[i].u);
        rv = find(E[i].v);
        if (ru != rv) {
            parent[ru] = rv;                  /* union */
            taken++;
            total += E[i].w;
            printf("%c - %c   %2d    taken\n", 'A' + E[i].u, 'A' + E[i].v, E[i].w);
        } else {
            printf("%c - %c   %2d    rejected (cycle)\n", 'A' + E[i].u, 'A' + E[i].v, E[i].w);
        }
    }
    printf("Total weight of MST = %d\n", total);
    return 0;
}

Input: same as Program 5 (without the start vertex)

Output

Edge   Weight  Result
A - D    5    taken
C - E    5    taken
D - F    6    taken
A - B    7    taken
B - E    7    taken
B - C    8    rejected (cycle)
E - F    8    rejected (cycle)
B - D    9    rejected (cycle)
E - G    9    taken
Total weight of MST = 39

	Prim	Kruskal
Grows	One tree from a start vertex	A forest that merges into one tree
Picks	Cheapest edge leaving the tree	Cheapest edge overall that makes no cycle
Needs	Adjacency matrix/list + priority queue	Edge list + sorting + union-find
Time	O(n²) with a matrix; O(e log n) with a heap	O(e log e) (the sort dominates)
Better for	Dense graphs	Sparse graphs
Disconnected graph	Covers only one component	Gives a minimum spanning forest

6.4Dijkstra's shortest path

Idea: keep a tentative distance dist[v] for every vertex. Repeatedly pick the unfinished vertex with the smallest dist — its distance can no longer improve, so fix it. Then try to improve its neighbours: this is called relaxing an edge.

DIJKSTRA(G, s)
1. dist[v] = ∞, prev[v] = NIL, done[v] = 0 for every v;  dist[s] = 0
2. Repeat n times:
     u = unfinished vertex with the smallest dist[u]
     done[u] = 1
     For every neighbour v of u with done[v] = 0:      // RELAX
         If dist[u] + w(u, v) < dist[v]:
             dist[v] = dist[u] + w(u, v);  prev[v] = u
3. The path to t: follow prev[] back from t to s.

Notice: the direct edge A–B costs 4, but A → C → B costs 2 + 1 = 3. Dijkstra finds this when it relaxes C–B. The final distances are A 0, B 3, C 2, D 8, E 10, F 13.

Common mistake: Using Dijkstra with negative edge weights. Once a vertex is fixed it is never updated again, so a later negative edge cannot correct it. Use the Bellman–Ford algorithm for negative weights (it relaxes every edge n − 1 times, O(n·e)).

Program 7 — Dijkstra (adjacency matrix, O(n²))

/* Dijkstra's shortest paths, O(n^2) with an adjacency matrix */
#include <stdio.h>
#include <limits.h>
#define MAX 20

int cost[MAX][MAX];     /* 0 = no edge */
int n;

void printPath(int prev[], int v) {
    if (prev[v] != -1) {
        printPath(prev, prev[v]);
        printf(" -> ");
    }
    printf("%c", 'A' + v);
}

void dijkstra(int s) {
    int dist[MAX], prev[MAX], done[MAX];
    int i, k, u, v;
    for (i = 0; i < n; i++) {
        dist[i] = INT_MAX;
        prev[i] = -1;
        done[i] = 0;
    }
    dist[s] = 0;
    for (k = 0; k < n; k++) {
        u = -1;                                   /* unfinished vertex with smallest dist */
        for (i = 0; i < n; i++)
            if (!done[i] && dist[i] != INT_MAX && (u == -1 || dist[i] < dist[u]))
                u = i;
        if (u == -1) break;                       /* the rest are unreachable */
        done[u] = 1;
        for (v = 0; v < n; v++)                   /* relax every edge u -> v */
            if (cost[u][v] && !done[v] && dist[u] + cost[u][v] < dist[v]) {
                dist[v] = dist[u] + cost[u][v];
                prev[v] = u;
            }
    }
    printf("\nVertex  Distance  Path\n");
    for (i = 0; i < n; i++) {
        if (dist[i] == INT_MAX) { printf("  %c     unreachable\n", 'A' + i); continue; }
        printf("  %c     %4d      ", 'A' + i, dist[i]);
        printPath(prev, i);
        printf("\n");
    }
}

int main() {
    int e, i, w;
    char u, v, s;
    printf("Number of vertices: ");
    scanf("%d", &n);
    printf("Number of edges: ");
    scanf("%d", &e);
    for (i = 0; i < e; i++) {
        printf("Edge %d (u v weight): ", i + 1);
        scanf(" %c %c %d", &u, &v, &w);
        cost[u - 'A'][v - 'A'] = cost[v - 'A'][u - 'A'] = w;   /* undirected */
    }
    printf("Source vertex: ");
    scanf(" %c", &s);
    dijkstra(s - 'A');
    return 0;
}

Input (graph above)

6
9
A B 4
A C 2
B C 1
B D 5
C D 8
C E 10
D E 2
D F 6
E F 3
A

Output

Vertex  Distance  Path
  A        0      A
  B        3      A -> C -> B
  C        2      A -> C
  D        8      A -> C -> B -> D
  E       10      A -> C -> B -> D -> E
  F       13      A -> C -> B -> D -> E -> F

6.5Topological sort

Definition

A topological order of a DAG is a line-up of all vertices such that for every edge u → v, u comes before v.

In simple words

You want to get dressed: socks before shoes, shirt before tie. Topological sort gives an order that respects every “before” rule. If the rules go in a circle (A before B before A), no order is possible.

Kahn's method: repeatedly take a vertex with in-degree 0 (nothing left that must come before it), write it down, and delete its outgoing edges.

TOPO_SORT(G)
1. Compute in[v] for every vertex
2. Put every vertex with in[v] = 0 into a queue
3. While the queue is not empty:
     u = DEQUEUE();  print u
     For every edge u → v:
         in[v] = in[v] − 1
         If in[v] == 0: ENQUEUE(v)
4. If fewer than n vertices were printed → the graph has a cycle.

Program 8 — Topological sort (Kahn)

/* Topological sort (Kahn's algorithm) on a directed graph */
#include <stdio.h>
#define MAX 20

int adj[MAX][MAX], indeg[MAX];
int n;

int main() {
    int e, i, v, u, queue[MAX], front = 0, rear = -1, count = 0;
    char a, b;
    printf("Number of vertices: ");
    scanf("%d", &n);
    printf("Number of edges: ");
    scanf("%d", &e);
    for (i = 0; i < e; i++) {
        printf("Edge %d (from to): ", i + 1);
        scanf(" %c %c", &a, &b);
        adj[a - 'A'][b - 'A'] = 1;
        indeg[b - 'A']++;
    }
    for (i = 0; i < n; i++)                     /* all vertices with no prerequisite */
        if (indeg[i] == 0) queue[++rear] = i;

    printf("\nTopological order: ");
    while (front <= rear) {
        u = queue[front++];
        printf("%c ", 'A' + u);
        count++;
        for (v = 0; v < n; v++)
            if (adj[u][v]) {
                indeg[v]--;                     /* remove edge u -> v */
                if (indeg[v] == 0) queue[++rear] = v;
            }
    }
    if (count < n) printf("\nThe graph has a cycle - no topological order.");
    printf("\n");
    return 0;
}

Input (DAG above)

8
8
A C
B C
B D
C E
D F
E F
E G
F H

Output

Topological order: A B C D E F G H

6.6Algorithm lab

Run any of the four algorithms on the sample graphs or on your own. Open Edit the graph and set “New edge weight” before tapping two vertices.

6.7Which algorithm when?

Problem	Algorithm	Time
Visit everything / fewest hops (unweighted)	BFS	O(V + E)
Cycle check, components, maze	DFS	O(V + E)
Cheapest way to connect all vertices	Prim / Kruskal	O(E log V)
Shortest path, weights ≥ 0	Dijkstra	O(V²) or O((V + E) log V)
Shortest path, negative weights	Bellman–Ford	O(V · E)
Shortest paths between every pair	Floyd–Warshall	O(V³)
Order tasks with dependencies	Topological sort (Kahn or DFS)	O(V + E)

Remember from Part 6

Spanning tree: all n vertices, n − 1 edges, no cycle. MST: least total weight.
Prim grows one tree using the smallest key. Kruskal sorts edges and skips cycles with union-find.
Dijkstra fixes the closest unfinished vertex and relaxes its edges. No negative weights.
Topological sort works only on a DAG: keep removing in-degree-0 vertices.

Unit V · Part 7 Advanced

Advanced Graph Algorithms

What to do when weights are negative, when you need the distance between every pair, and how to find cycles, weak points, groups and colourings in a graph. Every algorithm has a step player.

Beyond the core syllabus: Bellman–Ford, Floyd–Warshall, cycle detection, components, bipartite check, bridges and cut vertices, strongly connected components, Euler and Hamiltonian paths, graph colouring. Asked in long university answers, GATE and placement interviews.

7.1Bellman–Ford: shortest path with negative weights

Why do we need it? Dijkstra fixes a vertex for ever as soon as it is the closest one. With a negative edge, a cheaper path can appear later, and Dijkstra misses it.

Definition

Bellman–Ford finds the shortest distance from one source s to every vertex. Edge weights may be negative. It also reports a negative cycle if one can be reached from s.

In simple words

Don't be clever, be patient. Relax every edge, then do it again, and again. A shortest path has at most n − 1 edges, so after n − 1 rounds every distance is correct. If a round n can still improve something, there must be a loop that keeps getting cheaper — a negative cycle.

BELLMAN-FORD(G, s)
1. dist[v] = ∞, prev[v] = NIL for every v;   dist[s] = 0
2. Repeat n − 1 times:                    // one "pass"
     For every edge (u, v) with weight w:
         If dist[u] + w < dist[v]:         // RELAX
             dist[v] = dist[u] + w;  prev[v] = u
     (if nothing changed in this pass, stop early)
3. For every edge (u, v):                 // extra check
     If dist[u] + w < dist[v]:  report "negative cycle"

Pass	B	C	D	E
Start	∞	∞	∞	∞
After pass 1	6	4	7	2
After pass 2	2	4	7	2
After pass 3	2	4	7	−2
After pass 4	2	4	7	−2

Edges are relaxed in the order A→B, A→D, B→C, B→D, B→E, C→B, D→C, D→E, E→A, E→C. The shortest path to E is A → D → C → B → E = 7 − 3 − 2 − 4 = −2. A different edge order gives the same final answer, but the in-between rows can change.

Negative cycle

If a cycle has a negative total, you can go round it forever and the cost keeps falling. Then "shortest path" has no meaning. Bellman–Ford catches this with the extra pass.

	Dijkstra	Bellman–Ford
Negative edges	Not allowed	Allowed
Negative cycle	Cannot detect	Detects it
Idea	Greedy: fix the closest vertex	Relax all edges n − 1 times
Time	O(n²) or O((n + e) log n)	O(n · e)
Used in	Maps, GPS	Distance-vector routing (RIP), currency arbitrage

Program 9 — Bellman–Ford with negative-cycle check

/* Bellman-Ford shortest paths (negative weights allowed), O(V * E) */
#include <stdio.h>
#include <limits.h>
#define MAX 20
#define MAXE 100

struct Edge { int u, v, w; } E[MAXE];
int n, e;

void printPath(int prev[], int v) {
    if (prev[v] != -1) {
        printPath(prev, prev[v]);
        printf(" -> ");
    }
    printf("%c", 'A' + v);
}

void bellmanFord(int s) {
    int dist[MAX], prev[MAX];
    int i, j, pass, changed;
    for (i = 0; i < n; i++) {
        dist[i] = INT_MAX;
        prev[i] = -1;
    }
    dist[s] = 0;
    for (pass = 1; pass <= n - 1; pass++) {       /* relax every edge n-1 times */
        changed = 0;
        for (j = 0; j < e; j++) {
            int u = E[j].u, v = E[j].v, w = E[j].w;
            if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                prev[v] = u;
                changed = 1;
            }
        }
        if (!changed) break;                      /* nothing improved: stop early */
    }
    for (j = 0; j < e; j++)                       /* one more pass: negative cycle? */
        if (dist[E[j].u] != INT_MAX && dist[E[j].u] + E[j].w < dist[E[j].v]) {
            printf("\nNegative cycle found: shortest paths are not defined.\n");
            return;
        }
    printf("\nPasses used: %d\n", pass > n - 1 ? n - 1 : pass);
    printf("Vertex  Distance  Path\n");
    for (i = 0; i < n; i++) {
        if (dist[i] == INT_MAX) { printf("  %c     unreachable\n", 'A' + i); continue; }
        printf("  %c     %4d      ", 'A' + i, dist[i]);
        printPath(prev, i);
        printf("\n");
    }
}

int main() {
    int i, w;
    char u, v, s;
    printf("Number of vertices: ");
    scanf("%d", &n);
    printf("Number of directed edges: ");
    scanf("%d", &e);
    for (i = 0; i < e; i++) {
        printf("Edge %d (u v weight): ", i + 1);
        scanf(" %c %c %d", &u, &v, &w);
        E[i].u = u - 'A'; E[i].v = v - 'A'; E[i].w = w;
    }
    printf("Source vertex: ");
    scanf(" %c", &s);
    bellmanFord(s - 'A');
    return 0;
}

Input (graph above)

5
10
A B 6
A D 7
B C 5
B D 8
B E -4
C B -2
D C -3
D E 9
E A 2
E C 7
A

Output

Passes used: 4
Vertex  Distance  Path
  A        0      A
  B        2      A -> D -> C -> B
  C        4      A -> D -> C
  D        7      A -> D
  E       -2      A -> D -> C -> B -> E

Output with the negative-cycle graph

Negative cycle found: shortest paths are not defined.

7.2Floyd–Warshall: shortest path between every pair

Definition

Floyd–Warshall computes the shortest distance between every pair of vertices (i, j) using a distance matrix D. Negative edges are allowed, negative cycles are not.

In simple words

Take the cities one by one. For city k ask every pair (i, j): "Is it shorter to go from i to j by passing through k?" If yes, write the new smaller number in the table. After you have tried every k, the table is complete.

D^k[i][j] = min( D^k−1[i][j], D^k−1[i][k] + D^k−1[k][j] )

FLOYD-WARSHALL(W)
1. D = W        // D[i][i] = 0, D[i][j] = weight, or ∞ if no edge
2. For k = 1 to n:                // k = the allowed middle vertex
     For i = 1 to n:
         For j = 1 to n:
             If D[i][k] + D[k][j] < D[i][j]:
                 D[i][j] = D[i][k] + D[k][j]
3. Return D

D⁰	A	B	C	D
A	0	3	∞	7
B	8	0	2	∞
C	5	∞	0	1
D	2	∞	∞	0

D⁴ (final)	A	B	C	D
A	0	3	5	6
B	5	0	2	3
C	3	6	0	1
D	2	5	7	0

Exam tip: The k loop must be the outermost. In each round k, row k and column k never change, so copy them first and fill only the other cells — it saves time. Write all matrices D⁰, D¹, … Dⁿ.

Time O(n³), space O(n²). Simple code, great for small dense graphs.
Running Dijkstra from every vertex costs O(n · (n + e) log n) — better for big sparse graphs with no negative edges.
A negative number on the diagonal at the end means a negative cycle.
With 0/1 values and OR/AND instead of min/+, the same loops give Warshall's transitive closure (can i reach j at all?).

Program 10 — Floyd–Warshall

/* Floyd-Warshall: shortest distance between every pair, O(V^3) */
#include <stdio.h>
#define MAX 20
#define INF 99999

int D[MAX][MAX];
int n;

void printMatrix(const char *title) {
    int i, j;
    printf("\n%s\n    ", title);
    for (j = 0; j < n; j++) printf("%4c", 'A' + j);
    printf("\n");
    for (i = 0; i < n; i++) {
        printf("%c : ", 'A' + i);
        for (j = 0; j < n; j++) {
            if (D[i][j] >= INF) printf("   -");
            else printf("%4d", D[i][j]);
        }
        printf("\n");
    }
}

void floyd() {
    int i, j, k;
    for (k = 0; k < n; k++)                 /* allow vertex k as a middle stop */
        for (i = 0; i < n; i++)
            for (j = 0; j < n; j++)
                if (D[i][k] < INF && D[k][j] < INF && D[i][k] + D[k][j] < D[i][j])
                    D[i][j] = D[i][k] + D[k][j];
}

int main() {
    int e, i, j, w;
    char u, v;
    printf("Number of vertices: ");
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            D[i][j] = (i == j) ? 0 : INF;
    printf("Number of directed edges: ");
    scanf("%d", &e);
    for (i = 0; i < e; i++) {
        printf("Edge %d (u v weight): ", i + 1);
        scanf(" %c %c %d", &u, &v, &w);
        D[u - 'A'][v - 'A'] = w;
    }
    printMatrix("Initial matrix D0 (- = no edge):");
    floyd();
    printMatrix("Shortest distances:");
    return 0;
}

Input

4
7
A B 3
A D 7
B A 8
B C 2
C A 5
C D 1
D A 2

Output

Initial matrix D0 (- = no edge):
       A   B   C   D
A :    0   3   -   7
B :    8   0   2   -
C :    5   -   0   1
D :    2   -   -   0

Shortest distances:
       A   B   C   D
A :    0   3   5   6
B :    5   0   2   3
C :    3   6   0   1
D :    2   5   7   0

7.3Cycle detection

Many questions start with "does this graph have a cycle?" — a tree must not have one, a topological order needs none, a deadlock is one. The answer is a small change to DFS, and the rule is different for undirected and directed graphs.

Graph	Cycle exists if DFS…	Why the extra rule
Undirected	meets a visited vertex that is not the parent	The edge back to the parent is the same edge we came along, not a loop.
Directed	meets a grey vertex (still on the current path)	A black (finished) vertex can be reached by two paths without any cycle, e.g. A→B→D and A→C→D.

Watch the step where C→D reaches D. D is still grey, so D → E → C → D is a cycle. DFS can stop at the first back edge — one is enough to prove a cycle.

Other ways to detect a cycle:

Undirected, union-find (like Kruskal): for each edge, if both ends are already in the same set → cycle.
Directed, Kahn's topological sort: if fewer than n vertices come out, the rest are on a cycle (see 6.5).
Quick count: a connected undirected graph with e ≥ n edges always has a cycle (a tree has only n − 1).

Program 11 — Cycle detection in a directed graph (DFS colours)

/* Cycle detection in a directed graph using DFS colours
   0 = white (not visited), 1 = grey (on the current path), 2 = black (finished) */
#include <stdio.h>
#define MAX 20

int adj[MAX][MAX], color[MAX], parent[MAX];
int n;

int dfs(int u) {
    int v, x;
    color[u] = 1;                                   /* grey: on the path */
    for (v = 0; v < n; v++) {
        if (!adj[u][v]) continue;
        if (color[v] == 1) {                        /* back edge -> cycle */
            printf("Cycle found: %c", 'A' + v);
            {   int path[MAX], k = 0;
                for (x = u; x != v; x = parent[x]) path[k++] = x;
                while (k > 0) printf(" -> %c", 'A' + path[--k]);
            }
            printf(" -> %c\n", 'A' + v);
            return 1;
        }
        if (color[v] == 0) {
            parent[v] = u;
            if (dfs(v)) return 1;
        }
    }
    color[u] = 2;                                   /* black: finished */
    return 0;
}

int main() {
    int e, i;
    char u, v;
    printf("Number of vertices: ");
    scanf("%d", &n);
    printf("Number of directed edges: ");
    scanf("%d", &e);
    for (i = 0; i < e; i++) {
        printf("Edge %d (u v): ", i + 1);
        scanf(" %c %c", &u, &v);
        adj[u - 'A'][v - 'A'] = 1;
    }
    printf("\n");
    for (i = 0; i < n; i++) {
        if (color[i] == 0) {
            parent[i] = -1;
            if (dfs(i)) return 0;
        }
    }
    printf("No cycle: the graph is a DAG.\n");
    return 0;
}

Input (graph above)

5
6
A B
A C
B D
C D
D E
E C

Output

Cycle found: D -> E -> C -> D

Output with the DAG of Part 6

No cycle: the graph is a DAG.

7.4Connected components and bipartite check

Counting components is the simplest use of BFS or DFS: go through the vertices; every time you find an unvisited one, start a new search and give everything it reaches the same number (colour).

Theorem

A graph is bipartite if and only if it has no cycle of odd length.

In simple words

Colour the start white. Its neighbours must be dark, their neighbours white, and so on. If an edge ever joins two vertices of the same colour, you are stuck — that edge closes an odd cycle. BFS does this colouring level by level: even levels = X, odd levels = Y.

Uses: matching students to projects, jobs to machines (both are bipartite graphs); checking if a 2-slot timetable is possible; Kₘ,ₙ problems.

7.5Bridges and articulation points

Bridge (cut edge)

An edge whose removal increases the number of connected components.

Articulation point (cut vertex)

A vertex whose removal (with its edges) increases the number of components.

Slow way: remove each edge (or vertex) and run DFS again — O(e · (n + e)). Fast way (Tarjan): one DFS that stores two numbers for each vertex.

disc[u] — the time DFS first reached u (1, 2, 3, …).
low[u] — the smallest disc that u's subtree can reach using at most one back edge. It tells us how high the subtree can "climb back".

Test (v is a DFS child of u)	Meaning
low[v] > disc[u] → u–v is a bridge	Nothing under v can climb back to u or above, so u–v is the only link.
u not root and low[v] ≥ disc[u] → u is a cut vertex	The subtree of v cannot get above u without going through u.
u is root with ≥ 2 DFS children → u is a cut vertex	The children's subtrees are joined only through the root.

Why care? In a computer or road network, a bridge is a single cable or road whose failure splits the network, and a cut vertex is a single router or junction. Engineers add backup links exactly there.

Program 12 — Bridges and cut vertices (Tarjan)

/* Bridges and articulation points (cut vertices) with Tarjan's DFS, O(V + E) */
#include <stdio.h>
#define MAX 20

int adj[MAX][MAX], disc[MAX], low[MAX], parent[MAX], isCut[MAX];
int n, timer = 0;

int min(int a, int b) { return a < b ? a : b; }

void dfs(int u) {
    int v, children = 0;
    disc[u] = low[u] = ++timer;
    for (v = 0; v < n; v++) {
        if (!adj[u][v]) continue;
        if (disc[v] == 0) {                       /* tree edge */
            children++;
            parent[v] = u;
            dfs(v);
            low[u] = min(low[u], low[v]);
            if (low[v] > disc[u])
                printf("Bridge: %c - %c\n", 'A' + u, 'A' + v);
            if (parent[u] != -1 && low[v] >= disc[u])
                isCut[u] = 1;
        } else if (v != parent[u]) {              /* back edge */
            low[u] = min(low[u], disc[v]);
        }
    }
    if (parent[u] == -1 && children >= 2)         /* root rule */
        isCut[u] = 1;
}

int main() {
    int e, i;
    char u, v;
    printf("Number of vertices: ");
    scanf("%d", &n);
    printf("Number of edges: ");
    scanf("%d", &e);
    for (i = 0; i < e; i++) {
        printf("Edge %d (u v): ", i + 1);
        scanf(" %c %c", &u, &v);
        adj[u - 'A'][v - 'A'] = adj[v - 'A'][u - 'A'] = 1;
    }
    printf("\n");
    for (i = 0; i < n; i++)
        if (disc[i] == 0) { parent[i] = -1; dfs(i); }
    printf("Cut vertices:");
    for (i = 0; i < n; i++) if (isCut[i]) printf(" %c", 'A' + i);
    printf("\n\nVertex  disc  low\n");
    for (i = 0; i < n; i++) printf("  %c     %2d   %2d\n", 'A' + i, disc[i], low[i]);
    return 0;
}

Input (graph above)

7
8
A B
A C
B C
C D
D E
D F
E F
F G

Output

Bridge: F - G
Bridge: C - D
Cut vertices: C D F

Vertex  disc  low
  A      1    1
  B      2    1
  C      3    1
  D      4    4
  E      5    4
  F      6    4
  G      7    7

7.6Strongly connected components (SCC)

Definition

In a directed graph, a strongly connected component is a largest group of vertices in which every vertex can reach every other by following the arrows.

Kosaraju's algorithm — two DFS passes:

KOSARAJU(G)
1. Run DFS on G. When a vertex FINISHES, push it on a stack.
2. Build Gᵀ: reverse every edge.
3. While the stack is not empty:
     u = POP()
     If u is not visited in pass 2:
         DFS(Gᵀ, u)  — every vertex reached is ONE SCC

Why reverse the edges?

The vertex that finishes last sits in a "source" SCC. In the reversed graph, that SCC has no way out, so DFS from it stays inside and collects exactly that one SCC. Then the next one, and so on.

Tarjan's SCC algorithm does the same job in a single DFS using the low[] idea of 7.5. Both are O(n + e). Uses: finding groups of web pages that link to each other, circular dependencies in software, 2-SAT.

Program 13 — Strongly connected components (Kosaraju)

/* Strongly connected components with Kosaraju's algorithm, O(V + E)
   Pass 1: DFS on G, push each vertex when it finishes.
   Pass 2: DFS on the reversed graph in reverse finish order. */
#include <stdio.h>
#define MAX 20

int adj[MAX][MAX], visited[MAX], stack[MAX], top = -1;
int n;

void dfs1(int u) {
    int v;
    visited[u] = 1;
    for (v = 0; v < n; v++)
        if (adj[u][v] && !visited[v]) dfs1(v);
    stack[++top] = u;                       /* finished: push */
}

void dfs2(int u) {                          /* uses reversed edges: adj[v][u] */
    int v;
    visited[u] = 1;
    printf(" %c", 'A' + u);
    for (v = 0; v < n; v++)
        if (adj[v][u] && !visited[v]) dfs2(v);
}

int main() {
    int e, i, count = 0;
    char u, v;
    printf("Number of vertices: ");
    scanf("%d", &n);
    printf("Number of directed edges: ");
    scanf("%d", &e);
    for (i = 0; i < e; i++) {
        printf("Edge %d (u v): ", i + 1);
        scanf(" %c %c", &u, &v);
        adj[u - 'A'][v - 'A'] = 1;
    }
    for (i = 0; i < n; i++)
        if (!visited[i]) dfs1(i);
    printf("\nFinish order:");
    for (i = 0; i <= top; i++) printf(" %c", 'A' + stack[i]);
    printf("\n");
    for (i = 0; i < n; i++) visited[i] = 0;
    while (top >= 0) {
        int x = stack[top--];
        if (!visited[x]) {
            printf("SCC %d:", ++count);
            dfs2(x);
            printf("\n");
        }
    }
    printf("Number of SCCs = %d\n", count);
    return 0;
}

Input (graph above)

8
10
A B
B C
C A
B D
D E
E F
F D
G F
G H
H G

Output

Finish order: C F E D B A H G
SCC 1: G H
SCC 2: A C B
SCC 3: D F E
Number of SCCs = 3

7.7Euler and Hamiltonian paths

In 1736 the city of Königsberg had 7 bridges joining 4 land areas. People asked: can you walk across every bridge exactly once? Euler proved it is impossible — and invented graph theory.

Connected graph	Euler circuit (start = end)	Euler path (start ≠ end)
Undirected	Every vertex has even degree	Exactly 2 vertices have odd degree (start at one, end at the other)
Directed	in(v) = out(v) for every v	One vertex out = in + 1 (start), one in = out + 1 (end), all others equal

Hierholzer's method is O(e). The older Fleury's method also works: at each step take any unused edge, but never cross a bridge of the remaining graph unless you have no other choice.

Hamiltonian path and cycle

Definition

A Hamiltonian path visits every vertex exactly once. A Hamiltonian cycle also returns to the start.

	Euler	Hamiltonian
Uses every…	edge once	vertex once
Easy test?	Yes — count odd degrees	No known fast test (NP-complete)
Find it	O(e)	Backtracking, O(n!) worst case
Real problem	Postman route, drawing puzzles	Travelling salesman, tours

Sufficient conditions (if true, a Hamiltonian cycle surely exists, n ≥ 3):

Dirac: every vertex has degree ≥ n/2.
Ore: deg(u) + deg(v) ≥ n for every non-adjacent pair u, v.
K_n always has one.

7.8Graph colouring

Definition

A proper colouring gives each vertex a colour so that no edge joins two vertices of the same colour. The smallest number of colours needed is the chromatic number χ(G).

Graph	χ(G)
No edges (null graph)	1
Bipartite with at least one edge (trees, even cycles)	2
Odd cycle C_2k+1	3
Complete graph K_n	n
Any planar graph (map)	≤ 4 (Four Colour Theorem)
Any graph with largest degree Δ	≤ Δ + 1 (greedy always achieves this)

WELSH-POWELL(G)
1. Sort the vertices by degree, largest first.
2. For each vertex v in this order:
     Give v the smallest colour number not used by any coloured neighbour.

This graph is a wheel: hub C joined to the 5-cycle A–B–E–F–D. The rim is an odd cycle (needs 3 colours) and the hub touches all of it (one more), so χ = 4 and greedy found the best answer here. On other graphs greedy can use more colours than needed — finding χ exactly is NP-hard.

Real use: exam timetable

Each subject is a vertex. Join two subjects if some student takes both. A colouring = a timetable: same colour = same time slot, and no student has two exams at once. χ(G) = the fewest slots. The same idea assigns CPU registers, radio frequencies and Sudoku digits.

Program 14 — Greedy colouring (Welsh–Powell)

/* Greedy graph colouring (Welsh-Powell order: highest degree first) */
#include <stdio.h>
#define MAX 20

int adj[MAX][MAX], deg[MAX], order[MAX], color[MAX];
int n;

int main() {
    int e, i, j, k, c, used[MAX], maxc = 0;
    char u, v;
    printf("Number of vertices: ");
    scanf("%d", &n);
    printf("Number of edges: ");
    scanf("%d", &e);
    for (i = 0; i < e; i++) {
        printf("Edge %d (u v): ", i + 1);
        scanf(" %c %c", &u, &v);
        adj[u - 'A'][v - 'A'] = adj[v - 'A'][u - 'A'] = 1;
    }
    for (i = 0; i < n; i++) {
        deg[i] = 0;
        for (j = 0; j < n; j++) deg[i] += adj[i][j];
        order[i] = i;
        color[i] = -1;
    }
    for (i = 0; i < n - 1; i++)               /* sort by degree, largest first (stable) */
        for (j = 0; j < n - 1 - i; j++)
            if (deg[order[j]] < deg[order[j + 1]]) {
                int t = order[j]; order[j] = order[j + 1]; order[j + 1] = t;
            }
    printf("\nOrder:");
    for (i = 0; i < n; i++) printf(" %c(%d)", 'A' + order[i], deg[order[i]]);
    printf("\n");
    for (k = 0; k < n; k++) {
        int x = order[k];
        for (c = 0; c < n; c++) used[c] = 0;
        for (j = 0; j < n; j++)               /* colours taken by neighbours */
            if (adj[x][j] && color[j] != -1) used[color[j]] = 1;
        for (c = 0; used[c]; c++);            /* smallest free colour */
        color[x] = c;
        if (c + 1 > maxc) maxc = c + 1;
        printf("%c gets colour %d\n", 'A' + x, c + 1);
    }
    printf("Colours used = %d\n", maxc);
    return 0;
}

Input (graph above)

6
10
A B
A C
A D
B C
B E
C D
C E
C F
D F
E F

Output

Order: C(5) A(3) B(3) D(3) E(3) F(3)
C gets colour 1
A gets colour 2
B gets colour 3
D gets colour 3
E gets colour 2
F gets colour 4
Colours used = 4

7.9Advanced lab

Pick any algorithm from this part. Choose a ready graph or open Edit the graph to draw your own (tap two vertices to join them, set a weight for new edges). Your exam question? Type its edges and watch the answer step by step.

7.10Which algorithm when?

Question	Algorithm	Key idea	Time
Fewest edges from s	BFS	Queue, level by level	O(n + e)
Shortest path, weights ≥ 0	Dijkstra	Fix the closest vertex	O((n + e) log n)
Shortest path, negative weights	Bellman–Ford	Relax all edges n − 1 times	O(n · e)
Shortest path, every pair	Floyd–Warshall	Try every k as a middle stop	O(n³)
Shortest path in a DAG	Topological order + relax	Relax edges in topo order	O(n + e)
Cheapest network (MST)	Prim / Kruskal	Greedy safe edge	O(e log n)
Is there a cycle?	DFS (parent / grey)	Back edge = cycle	O(n + e)
Order tasks	Topological sort	Remove in-degree 0	O(n + e)
How many pieces?	BFS / DFS / union-find	New search = new component	O(n + e)
Two groups possible?	BFS 2-colouring	No odd cycle	O(n + e)
Weak links in a network	Tarjan (disc / low)	low[v] vs disc[u]	O(n + e)
Groups that reach each other	Kosaraju / Tarjan SCC	DFS, reverse, DFS	O(n + e)
Use every edge once	Euler (Hierholzer)	0 or 2 odd vertices	O(e)
Visit every vertex once	Hamiltonian (backtracking)	Try and undo	O(n!)
Fewest time slots / colours	Greedy colouring	Smallest free colour	O(n + e) after sort

Remember from Part 7

Bellman–Ford: n − 1 passes over all edges; an n-th improvement means a negative cycle. O(n · e).
Floyd–Warshall: D[i][j] = min(D[i][j], D[i][k] + D[k][j]) with k outermost. O(n³).
Cycle: undirected → visited non-parent; directed → grey vertex.
Bipartite ⇔ no odd cycle ⇔ χ ≤ 2.
Bridge: low[v] > disc[u]. Cut vertex: low[v] ≥ disc[u] (root: 2+ children).
SCC (Kosaraju): DFS for finish order, reverse edges, DFS in reverse finish order.
Euler: 0 odd vertices → circuit, 2 → path. Hamiltonian: no easy test.

Unit V · Revision

Revision & Exam

Everything on one page the night before the exam: formulas, complexities, traps, model answers and a mixed quiz.

R.1Formula sheet

Fact	Formula
Graph	G = (V, E), order n = \|V\|, size e = \|E\|
Handshake lemma	Σ deg(v) = 2e
Digraph degrees	Σ in(v) = Σ out(v) = e
Odd-degree vertices	Always an even number of them
Max edges, simple undirected	n(n − 1) / 2
Max edges, simple directed	n(n − 1)
Complete graph K_n	n(n − 1)/2 edges, every degree n − 1
k-regular graph	nk / 2 edges
Complete bipartite K_m,n	m · n edges
Tree / spanning tree	n − 1 edges
Forest with c trees	n − c edges
Spanning trees of K_n (Cayley)	n^{n − 2}
Adjacency matrix ones	2e (undirected), e (directed)
Adjacency list nodes	2e (undirected), e (directed)
Bellman–Ford passes	n − 1 (+ 1 check for a negative cycle)
Floyd–Warshall step	D[i][j] = min(D[i][j], D[i][k] + D[k][j])
Bridge / cut vertex	low[v] > disc[u] / low[v] ≥ disc[u]
Euler circuit / path	0 odd vertices / exactly 2 odd vertices
Chromatic number	χ(K_n) = n, bipartite = 2, planar ≤ 4, any ≤ Δ + 1

R.2Complexity table

Algorithm	Matrix	List / heap	Uses
BFS	O(n²)	O(n + e)	Queue
DFS	O(n²)	O(n + e)	Stack / recursion
Prim	O(n²)	O(e log n)	Priority queue
Kruskal	—	O(e log e)	Sort + union-find
Dijkstra	O(n²)	O((n + e) log n)	Priority queue
Topological sort	O(n²)	O(n + e)	Queue of in-degree 0
Bellman–Ford	O(n³)	O(n · e)	Edge list
Floyd–Warshall	O(n³)	—	Distance matrix
Cycle check, components, bipartite	O(n²)	O(n + e)	DFS / BFS
Bridges, cut vertices (Tarjan)	O(n²)	O(n + e)	DFS + disc / low
SCC (Kosaraju)	O(n²)	O(n + e)	2 DFS + reversed graph
Euler path (Hierholzer)	—	O(e)	Stack

R.3Common mistakes

1. Path length is the number of edges, not vertices.

2. A self-loop adds 2 to the degree in an undirected graph.

3. In BFS mark a vertex visited when it is enqueued, or it may enter the queue twice.

4. BFS/DFS order depends on the neighbour order. State “neighbours taken in alphabetical order”.

5. For a disconnected graph, one BFS/DFS does not reach everything — restart from an unvisited vertex.

6. Weakly connected is not strongly connected. Check that arrows allow travel both ways.

7. Same vertex count, edge count and degrees do not prove two graphs are isomorphic. Give the mapping.

8. Dijkstra fails with negative weights; topological sort fails on any directed cycle.

9. In Floyd–Warshall the k loop is outermost. Putting i or j outside gives wrong answers.

10. Bridge test uses > (low[v] > disc[u]); cut-vertex test uses ≥. The DFS root is a cut vertex only if it has 2 or more children.

11. Euler = every edge once; Hamiltonian = every vertex once. Do not mix them.

R.4Model answers

Q1Define a graph. Differentiate between directed and undirected graphs. (5 marks)

A graph G = (V, E) is a non-linear data structure made of a finite non-empty set V of vertices and a set E of edges, where each edge connects a pair of vertices.

In an undirected graph each edge is an unordered pair (u, v) = (v, u) and can be travelled both ways; its adjacency matrix is symmetric; each vertex has one degree; maximum edges n(n − 1)/2. In a directed graph each edge is an ordered pair <u, v> from tail u to head v and can be travelled one way only; its matrix need not be symmetric; each vertex has an in-degree and an out-degree; maximum edges n(n − 1). Draw one small example of each.

Q2Explain the following terms with an example: degree, path, cycle, loop, multiple edges, connected graph.

Use Figure 1 of Part 1. Degree = edges at a vertex, deg(B) = 3. Path = sequence of adjacent vertices without repetition, A–B–D–F. Cycle = path returning to its start, B–C–E–D–B. Loop = edge (v, v). Multiple edges = two or more edges between the same pair. Connected graph = a path exists between every pair of vertices.

Q3Prove that the number of odd-degree vertices in any graph is even.

By the handshake lemma Σ deg(v) = 2e, which is even. Split the sum into even-degree vertices and odd-degree vertices. The even part is even, so the odd part = 2e − (even) is also even. A sum of odd numbers is even only when there is an even count of them. Hence the number of odd-degree vertices is even. ∎

Q4Explain any five types of graphs with diagrams.

Choose from Part 3: simple, multigraph, weighted, regular, complete, bipartite, strongly/weakly connected, DAG, isomorphic. For each: one-line rule + small diagram + one property (e.g. K_n has n(n − 1)/2 edges).

Q5Represent a given graph using an adjacency matrix and an adjacency list. Compare the two.

Draw the n × n matrix with 1 where an edge exists (symmetric for undirected), and the array of head pointers with linked lists of neighbours. Comparison: matrix space O(n²) vs list O(n + e); edge check O(1) vs O(deg); neighbour listing O(n) vs O(deg); matrix for dense graphs, list for sparse graphs. Use the table in 4.6.

Q6Write an algorithm for BFS and trace it on a graph.

Write the algorithm in 5.2. Then trace with the dry-run table: columns Step, Dequeue, Enqueue, Queue, Output. Finish with the BFS order and draw the BFS spanning tree (thick edges). On the practical graph 0–1, 0–2, 1–3, 2–3 from 0 the order is 0 1 2 3. State complexity O(n + e) with lists, O(n²) with a matrix.

Q7Write a C function for DFS. What is its time complexity?

The recursive dfs() in 5.5 (program in 5.7): mark visited, print, recurse on each unvisited neighbour. Time O(n²) with an adjacency matrix because each call scans a full row; O(n + e) with an adjacency list. Space O(n) for visited[] and the recursion stack.

Q8Compare BFS and DFS.

Use the table in 5.8: queue vs stack, level order vs depth order, mark-on-enqueue vs mark-on-visit, both O(n + e) / O(n²), BFS gives shortest unweighted path, DFS detects cycles with back edges. Same practical graph: BFS 0 1 2 3, DFS 0 1 3 2.

Q9What is a spanning tree? Find the MST of a graph using Prim's / Kruskal's algorithm.

Definition from 6.1. Show the steps: for Prim a table of key/parent per step; for Kruskal the sorted edge list with taken/rejected marks. Draw the final tree and write the total weight. Mention both are greedy and give n − 1 edges.

Q10Find the shortest path from a source using Dijkstra's algorithm.

Make a table with one column per vertex and one row per step. Each row: the vertex fixed in this step and the updated dist values (∞ at the start). Circle the fixed values. At the end read every path from prev[]. Note the condition: no negative weights.

Q·A1Explain Bellman–Ford with an example. How is it different from Dijkstra? (10 marks)

Write the algorithm of 7.1: initialise dist, relax all edges n − 1 times, then one extra pass for a negative cycle. Draw the 5-vertex graph, list the edge order and show the dist table after each pass (A 0, B 2, C 4, D 7, E −2). Then give the comparison table: negative edges allowed, detects negative cycles, O(n · e) against Dijkstra's O(n²).

Q·A2Find all-pairs shortest paths using Floyd–Warshall. (10 marks)

Write the recurrence D^k[i][j] = min(D^k−1[i][j], D^k−1[i][k] + D^k−1[k][j]). Write D⁰ from the graph, then D¹ … Dⁿ — in each, copy row k and column k unchanged and check the remaining cells. Circle the changed cells. State O(n³) time and O(n²) space.

Q·A3What are articulation points and bridges? How are they found? (5 marks)

Give both definitions with the figure of 7.5. Explain disc and low, then the three rules (bridge: low[v] > disc[u]; cut vertex: low[v] ≥ disc[u] for a non-root; root with ≥ 2 children). One DFS, O(n + e). Mention network reliability as the use.

Q·A4State the conditions for an Euler path and circuit. Explain the Königsberg bridge problem.

Draw the 4-vertex multigraph with 7 edges. Degrees 5, 3, 3, 3 → four odd vertices → no Euler path. Rule: connected and 0 odd vertices → circuit; exactly 2 odd → path from one odd vertex to the other. Contrast with Hamiltonian (every vertex once, NP-complete).

R.5Mixed quiz

Every figure, animation and dry-run table in these notes is produced by the same JavaScript engine, and every C program was compiled with gcc and run on the inputs shown, so the figures, the player and the program output agree.