Graphs in Data Structures: Complete Guide with BFS, DFS and Dijkstra Worked Examples

A graph looks simple when it is only a picture of nodes and edges. Errors begin when you must convert that picture into a representation, follow a fixed traversal order, or choose a valid shortest-path algorithm. On the unweighted graph below, alphabetical neighbor order fixes reproducible BFS and DFS traces after you derive its list and matrix. On the separate weighted graph, every Dijkstra relaxation and predecessor remains checkable from the stated edges.

For directed-DFS edge classification, topological sort, and a broad Bellman-Ford/Floyd-Warshall comparison, continue to Graph Algorithms: BFS, DFS, and shortest paths worked out. Keep the two edge sets on this page in view to audit every adjacency entry, BFS queue state, DFS recursive call, Dijkstra relaxation, and predecessor chain by hand.

1. Graphs in Data Structures: vertices, edges and the terms that control the answer

A graph is G = (V, E), with vertex set V and edge set E. Directed edges have direction; undirected edges do not. A weighted graph gives each edge a value. A path connects vertices, a simple path repeats no vertex, and a cycle returns to its start. A connected component is a maximal connected part. Degree counts incident edges; indegree and outdegree count incoming and outgoing directed edges. A tree is a connected, acyclic undirected graph.

Our unweighted example has V = {A, B, C, D, E, F} and E = {A-B, A-C, B-D, B-E, C-F, E-F}. The degrees are 2, 3, 2, 1, 2, 2; their sum is 2+3+2+1+2+2 = 12 = 2|E|, since |E| = 6. Each undirected edge is counted at both endpoints. Euler paths, Hamiltonian cycles and colouring use different invariants: edge parity, vertex coverage and colouring constraints.

2. Adjacency list vs adjacency matrix: build both from the same graph

An adjacency list stores the neighbors of each vertex. In alphabetical order, our graph becomes:

A: B, C
B: A, D, E
C: A, F
D: B
E: B, F
F: C, E

Every undirected edge appears twice, once in each endpoint's list. The same graph has this adjacency matrix in vertex order A, B, C, D, E, F:

The matrix is symmetric because every edge works in both directions. Its diagonal is zero because there are no self-loops. An adjacency list uses Theta(V+E) space and scans the neighbors of u in Theta(deg(u)). A matrix uses Theta(V^2) space, checks one edge in Theta(1), and scans all possible neighbors in Theta(V).

3. Breadth-first search worked example: queue states and an unweighted shortest path

Breadth-first search explores one layer at a time. Start at A, scan each adjacency list alphabetically, and mark a vertex visited when it enters the queue. The full trace is:

1. Start: [A].

2. Process A, enqueue B, C: [B, C].

3. Process B, enqueue D, E: [C, D, E].

4. Process C, enqueue F: [D, E, F].

5. Process D: [E, F].

6. Process E: [F].

7. Process F: [].

The BFS order is A, B, C, D, E, F. Its parent links are B<-A, C<-A, D<-B, E<-B, and F<-C. Following parents from F gives A-C-F, a shortest path of 2 edges. A-B-E-F is valid but has 3 edges, so it is longer. BFS minimises edge count in an unweighted graph. Its runtime is Theta(V+E) with an adjacency list and Theta(V^2) with a matrix.

4. Depth-first search worked example: recursion, backtracking and order dependence

Recursive DFS follows one branch as far as possible. From A, choosing neighbors alphabetically, the calls go A -> B -> D. Backtrack to B, then visit E -> F -> C. Finally, backtrack through F, E, B, and A when no unvisited neighbor remains.

The discovery order is A, B, D, E, F, C, with DFS-tree edges {A-B, B-D, B-E, E-F, F-C}. DFS reveals depth, components and cycle structure; BFS reveals layers and unweighted shortest paths. Both take Theta(V+E) with adjacency lists. Neither order is universally fixed because it depends on neighbor order.

5. Dijkstra's algorithm worked example: settle distances and reconstruct the path

Now use an undirected weighted graph with vertices {S, A, B, C, D, T}. Its non-negative edges are S-A:4, S-B:2, B-A:1, A-C:5, B-C:8, B-D:10, C-D:2, C-T:6, and D-T:3. Set dist(S)=0 and every other distance to infinity.

For negative-edge Bellman-Ford passes and all-pairs Floyd-Warshall matrices, use Shortest Path Algorithms: Dijkstra, Bellman-Ford and Floyd-Warshall with Worked Examples for GATE CS. That earlier comparison uses a directed five-vertex example to separate algorithm families; the undirected six-vertex calculation here isolates Dijkstra's non-negative invariant, competing S-to-T routes, and predecessor reconstruction.

1. Settle S=0. Relaxing its edges gives A=4 and B=2.

2. Settle B=2. The route through B improves A to 2+1=3, sets C=2+8=10, and sets D=2+10=12.

3. Settle A=3. It improves C to 3+5=8.

4. Settle C=8. It improves D to 8+2=10 and sets T=8+6=14.

5. Settle D=10. It improves T to 10+3=13.

6. Settle T=13. The final distance has been reached.

The predecessor chain is T<-D<-C<-A<-B<-S. Reversing it gives shortest path S-B-A-C-D-T, with weight 2+1+5+2+3 = 13. By comparison, S-B-A-C-T weighs 2+1+5+6 = 14. Dijkstra is correct because every edge weight is non-negative. A negative edge requires another method, such as Bellman-Ford.

6. Graph algorithm selection: match the question to the method

Do not select an algorithm only because the input is a graph. First identify the graph's properties and the output the question asks for.

Representation determines storage and scanning cost. Graph properties determine which algorithms are valid. The requested output determines which valid algorithm is useful. Both BFS and DFS test reachability, but BFS is the direct choice for an unweighted shortest path. Dijkstra handles non-negative weighted shortest paths, not a minimum spanning tree. Euler paths, Hamiltonian cycles and colouring require the separate graph-theory treatment linked earlier.

7. Graph questions in GATE CS: common traps and reproducible checks

Most graph-tracing errors come from a small set of causes:

• Unspecified neighbor order permits several traversal orders. State alphabetical order before tracing.

• Marking a vertex visited only when dequeued can create duplicates. Mark it when enqueued in BFS.

• BFS does not solve weighted shortest paths. Dijkstra does not allow negative weights.

• An undirected adjacency matrix is symmetric; a directed graph's matrix need not be.

• In undirected DFS, an edge back to the parent does not by itself prove a cycle.

• |E|=|V|-1 alone does not prove a tree. The graph must also be connected. Equivalently, add acyclicity to the edge-count condition.

Typical tasks ask you to build a representation, trace a queue or recursion stack, identify a component or cycle, choose an algorithm, or calculate cost. Apply these checks in Graph MCQs: 10 Solved BFS, DFS, Connectivity (GATE). For the wider study sequence, see GATE CS Exam Preparation.

8. Graphs in Data Structures: the short version and next step

Identify the graph type, choose a list or matrix, fix neighbor order, use BFS or DFS for traversal, and use Dijkstra only for non-negative weighted shortest paths. Reproduce both examples without looking: BFS and DFS on {A, B, C, D, E, F}, then Dijkstra from S to T. Check for BFS A, B, C, D, E, F, DFS A, B, D, E, F, C, and distance 13. For a structured path through GATE CS preparation, continue with GATE Guidance by Sanchit Sir.