Graphs

Graph terminology, adjacency matrices, linked adjacency lists, BFS with a queue, and DFS with recursion or a stack.

Arrays store values in sequence. Linked lists connect one node to the next.

A graph is more general: any vertex may connect to any other vertex.

Graphs model roads between cities, friendships between people, links between web pages, computer networks, course prerequisites, and possible moves in a game.

This chapter brings earlier structures together: arrays build adjacency matrices, structures and linked lists build adjacency lists, queues produce BFS, and recursion or an explicit stack produces DFS.

Why Do We Need Graphs?

Suppose five people are connected like this:

The connections are:

0 -- 1
0 -- 2
1 -- 3
1 -- 4
2 -- 4

An array cannot naturally describe these arbitrary relationships. A linked list is also insufficient because one item may have several neighbors.

A graph stores two things:

vertices, representing the objects;
edges, representing the relationships between them.

For the drawing above:

vertices = {0, 1, 2, 3, 4}
edges    = {(0,1), (0,2), (1,3), (1,4), (2,4)}

The numbers are labels. Vertex 4 is not “larger” or “later” than vertex 1. The labels simply let the program identify each object.

Graphs are useful because they let us ask relationship questions:

Is one object directly connected to another?
Can one object be reached from another through several connections?
What route uses the fewest connections?
Does a route return to where it started?
Which objects belong to separate connected groups?
In what order can all reachable objects be visited?

The graph stores the relationships. BFS, DFS, and later algorithms answer questions about those relationships.

Real-Life Uses

Road maps: cities or intersections are vertices; roads are edges; distance or travel time can be a weight.
Airline routes: airports are vertices and direct flights are edges.
Friendship networks: people are vertices and friendships are undirected edges.
Following networks: accounts are vertices and “follows” relationships are directed edges.
Delivery networks: warehouses and destinations are vertices; available routes are edges.
Utility networks: power stations, substations, and buildings are connected by transmission lines.
Public transport: stations are vertices and bus or train connections are edges.

Computer Uses

Computer networks: routers or devices are vertices; physical or wireless links are edges.
Internet routing: routing algorithms choose paths through connected routers.
Web crawling: pages are vertices and hyperlinks are directed edges.
Social recommendations: mutual friends and nearby connections help suggest new contacts.
Game maps: locations are vertices and legal movements are edges.
File and module dependencies: a directed edge records that one file depends on another.
Package managers: software packages and dependency relationships form directed graphs.
Search engines: links between pages help determine discovery and importance.
Artificial intelligence: possible states are vertices and legal actions connect them.
Database relationships: records and their connections can be represented as graph data.

Turning a Situation into a Graph

Before writing code, decide what the vertices and edges mean.

Suppose a campus has four buildings:

0 = Gate
1 = Library
2 = Cafeteria
3 = Auditorium

Walkways exist between:

Gate -- Library
Gate -- Cafeteria
Library -- Auditorium
Cafeteria -- Auditorium

The graph model is:

vertices = buildings
edges    = direct walkways

Now the questions become precise:

graph[0][1] asks whether the Gate and Library have a direct walkway.
A path 0 -> 1 -> 3 shows that the Auditorium is reachable from the Gate.
BFS can find a route using the fewest walkways.
DFS can determine whether any route exists.

If a walkway is one-way, use a directed edge. If travel time matters, attach a weight. The same physical situation can therefore produce different graphs depending on the question being solved.

This modelling step is important: a graph is not merely a drawing or a matrix. It is a decision about which objects and relationships matter.

Essential Vocabulary

A graph is commonly written as:

G = (V, E)

V is the set of vertices and E is the set of edges.

For the edge 0 -- 1:

vertices 0 and 1 are adjacent;
vertex 1 is a neighbor of vertex 0;
the edge is incident on both vertices.

Other important terms:

Degree: number of edges connected to a vertex.
Path: sequence of connected vertices.
Cycle: path that returns to its starting vertex.
Connected graph: every vertex can be reached from every other vertex.
Component: one connected part of a disconnected graph.

In the example, vertex 1 has neighbors 0, 3, and 4, so its degree is 3.

The sequence 3 -> 1 -> 0 -> 2 is a path. The sequence 0 -> 1 -> 4 -> 2 -> 0 is a cycle.

Adjacent Is Not the Same as Reachable

Vertices 0 and 3 are not adjacent because no edge 0 -- 3 exists.

They are still reachable from each other:

0 -> 1 -> 3

Adjacent means one direct edge. Reachable means at least one path exists, possibly using many edges.

This distinction matters in code:

graph[0][3] checks direct adjacency;
BFS or DFS checks reachability through any number of intermediate vertices.

Degree Counts Direct Connections

Degree does not count every reachable vertex. It counts only edges touching the vertex.

In the sample graph:

degree(0) = 2
degree(1) = 3
degree(2) = 2
degree(3) = 1
degree(4) = 2

Vertex 3 can eventually reach every vertex, but its degree is only 1 because it has one direct neighbor.

Types of Graphs

Undirected Graph

An undirected edge works in both directions:

0 -- 1

If 0 is connected to 1, then 1 is also connected to 0. Friendships and two-way roads are common examples.

Directed Graph

A directed edge has an arrow:

0 --> 1

This means movement from 0 to 1 is allowed, but movement from 1 to 0 is not automatically allowed. Web links and prerequisite relationships are directed.

For directed graphs:

in-degree counts incoming edges;
out-degree counts outgoing edges.

Weighted Graph

A weighted edge stores a value such as distance, time, or cost:

Dhaka ---- 245 km ---- Chattogram

An unweighted graph records only whether a connection exists.

Cyclic and Acyclic Graphs

A cyclic graph contains at least one cycle. An acyclic graph contains none.

For example, the sample graph is cyclic because 0 -> 1 -> 4 -> 2 -> 0 returns to its starting vertex. If one of the edges in that route were removed, that particular cycle would disappear.

Choose the Type from the Relationship

Situation	Direction	Weight
Mutual friendship	Undirected	Usually unweighted
One account follows another	Directed	Usually unweighted
Two-way roads with distances	Undirected	Weighted
One-way roads with travel times	Directed	Weighted
Web page hyperlinks	Directed	Usually unweighted
Direct computer cable connections	Undirected	May be weighted by delay or capacity

“Directed,” “undirected,” “weighted,” and “unweighted” are not coding preferences. They describe the meaning of the original relationship.

Graph Operations

Unlike a stack or queue, a graph does not have only one universally fixed operation set. Common operations include:

addVertex: create a new vertex;
addEdge: connect two vertices;
removeEdge: remove a connection;
hasEdge: test direct adjacency;
neighbors: list directly connected vertices;
degree: count direct connections;
BFS: traverse breadth first;
DFS: traverse depth first.

The representation determines how these operations work internally. In an adjacency matrix, adding an edge changes array cells. In an adjacency list, adding the same edge creates linked-list nodes.

Ways to Represent a Graph

A drawing is useful for people, but a program needs values in memory. Three common representations are edge lists, adjacency matrices, and adjacency lists.

The graph and its representation are different ideas. The sample drawing, edge list, matrix, and adjacency list below all describe the same five vertices and five edges.

Edge List

Store each edge as a pair:

(0, 1)
(0, 2)
(1, 3)
(1, 4)
(2, 4)

An edge list is easy to read and useful when an algorithm processes every edge. Finding all neighbors of one vertex is slower because the whole list may need scanning.

Adjacency Matrix

An adjacency matrix uses one row and one column per vertex.

      0  1  2  3  4
   +---------------
0  | 0  1  1  0  0
1  | 1  0  0  1  1
2  | 1  0  0  0  1
3  | 0  1  0  0  0
4  | 0  1  1  0  0

The rule is:

graph[u][v] = 1  -> an edge exists from u to v
graph[u][v] = 0  -> no edge exists from u to v

For example, graph[1][4] is 1, so vertices 1 and 4 are adjacent. graph[2][3] is 0, so they are not adjacent.

The diagonal is 0 because this example has no self-loops.

For an undirected graph, the matrix is symmetric:

graph[u][v] == graph[v][u]

An adjacency matrix is a good first representation because array indexing is visible and predictable.

Adjacency List

An adjacency list stores only the neighbors of each vertex:

0 -> 1 -> 2
1 -> 0 -> 3 -> 4
2 -> 0 -> 4
3 -> 1
4 -> 1 -> 2

This resembles an array of linked lists:

the array index identifies a vertex;
the linked list at that index stores its neighbors.

The linked-list knowledge from the earlier chapter therefore becomes useful again.

Adjacency Matrix: Follow the Execution

We will implement the sample graph with a fixed-size matrix. The explanation follows runtime order: main, initialization, edge insertion, and display.

main -> initializeGraph -> addEdge five times -> displayGraph

int main() {
    initializeGraph(5);

    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(1, 3);
    addEdge(1, 4);
    addEdge(2, 4);

    displayGraph();

    return 0;
}

Execution begins in main.

initializeGraph(5) prepares storage for vertices 0 through 4. The program then calls addEdge once for each connection in the drawing.

The insertion order does not change which graph is stored. It only determines when each matrix cell becomes 1.

After all edges are inserted, displayGraph() prints the finished matrix.

#define MAX_VERTICES 10

int graph[MAX_VERTICES][MAX_VERTICES];
int vertexCount;

void initializeGraph(int vertices) {
    vertexCount = vertices;

    for (int i = 0; i < vertexCount; i++) {
        for (int j = 0; j < vertexCount; j++) {
            graph[i][j] = 0;
        }
    }
}

graph reserves a maximum 10 x 10 matrix. vertexCount records how much of that matrix is currently active.

When main calls initializeGraph(5), vertices receives 5, so vertexCount becomes 5.

The outer loop selects each row. For every row, the inner loop visits every column and stores 0.

After initialization:

The matrix now represents five vertices with no edges.

void addEdge(int source, int destination) {
    graph[source][destination] = 1;
    graph[destination][source] = 1;
}

The first call is addEdge(0, 1).

graph[0][1] = 1 stores the direction from 0 to 1. The second assignment stores the reverse direction from 1 to 0.

The state change is:

before addEdge(0, 1):
graph[0][1] = 0
graph[1][0] = 0

after addEdge(0, 1):
graph[0][1] = 1
graph[1][0] = 1

Both assignments are required for an undirected graph. Omitting the second line would store a directed edge.

void displayGraph() {
    printf("Adjacency Matrix:\n");

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

The outer loop chooses a row. The inner loop prints every value in that row.

After printing five values, printf("\n") moves to the next output line.

The result is:

Adjacency Matrix:
0 1 1 0 0
1 0 0 1 1
1 0 0 0 1
0 1 0 0 0
0 1 1 0 0

When displayGraph returns, main reaches return 0 and the program ends.

Adjacency Matrix: Full Code

#include <stdio.h>

#define MAX_VERTICES 10

int graph[MAX_VERTICES][MAX_VERTICES];
int vertexCount;

void initializeGraph(int vertices) {
    vertexCount = vertices;

    for (int i = 0; i < vertexCount; i++) {
        for (int j = 0; j < vertexCount; j++) {
            graph[i][j] = 0;
        }
    }
}

void addEdge(int source, int destination) {
    graph[source][destination] = 1;
    graph[destination][source] = 1;
}

void displayGraph() {
    printf("Adjacency Matrix:\n");

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

int main() {
    initializeGraph(5);

    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(1, 3);
    addEdge(1, 4);
    addEdge(2, 4);

    displayGraph();

    return 0;
}

Linked Adjacency List

The matrix reserves one cell for every possible pair of vertices. An adjacency list stores only edges that actually exist.

Because students already know structures and linked lists, we can build the representation directly:

typedef struct Node {
    int vertex;
    struct Node *next;
} Node;

Node *adjacencyList[MAX_VERTICES];

Each array index represents one vertex. The pointer stored at that index is the head of a linked list containing that vertex’s neighbors.

For example:

adjacencyList[0] -> 2 -> 1 -> NULL

This means vertex 0 is adjacent to vertices 2 and 1.

Adjacency List: Follow the Execution

main -> initializeListGraph
     -> addListEdge -> createNode twice
     -> displayListGraph
     -> freeListGraph

int main() {
    initializeListGraph(5);

    addListEdge(0, 1);
    addListEdge(0, 2);
    addListEdge(1, 3);
    addListEdge(1, 4);
    addListEdge(2, 4);

    displayListGraph();
    freeListGraph();

    return 0;
}

The same five edges are used again. Only the storage representation changes.

initializeListGraph(5) prepares five empty list heads. Every addListEdge call inserts one neighbor into each endpoint’s list because the graph is undirected.

The lists are displayed and then freed before the program ends.

void initializeListGraph(int vertices) {
    vertexCount = vertices;

    for (int i = 0; i < vertexCount; i++) {
        adjacencyList[i] = NULL;
    }
}

At the beginning:

adjacencyList[0] = NULL
adjacencyList[1] = NULL
adjacencyList[2] = NULL
adjacencyList[3] = NULL
adjacencyList[4] = NULL

Each vertex exists, but none has a neighbor yet.

Node *createNode(int vertex) {
    Node *newNode = malloc(sizeof(Node));

    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }

    newNode->vertex = vertex;
    newNode->next = NULL;

    return newNode;
}

This is the same allocation pattern used for linked lists, stacks, and queues.

malloc reserves enough memory for one Node. The node stores a neighbor number and a pointer to the next neighbor.

The null check prevents the program from dereferencing an invalid pointer if allocation fails.

void addListEdge(int source, int destination) {
    Node *newNode = createNode(destination);
    newNode->next = adjacencyList[source];
    adjacencyList[source] = newNode;

    newNode = createNode(source);
    newNode->next = adjacencyList[destination];
    adjacencyList[destination] = newNode;
}

For addListEdge(0, 1), the first node stores 1 in vertex 0’s list:

adjacencyList[0] -> 1 -> NULL

The second node stores the reverse connection:

adjacencyList[1] -> 0 -> NULL

The insertion uses the familiar linked-list operation:

newNode->next = head;
head = newNode;

Here, adjacencyList[source] plays the role of head.

One edge requires two separate nodes in an undirected adjacency list. The nodes contain different neighbor values and belong to different linked lists.

void displayListGraph() {
    printf("Adjacency List:\n");

    for (int i = 0; i < vertexCount; i++) {
        printf("%d -> ", i);

        Node *current = adjacencyList[i];
        while (current != NULL) {
            printf("%d -> ", current->vertex);
            current = current->next;
        }

        printf("NULL\n");
    }
}

The for loop selects one vertex. current then traverses that vertex’s linked list until it reaches NULL.

Because each new neighbor was inserted at the head, the display order is the reverse of insertion order. That does not change the graph.

void freeListGraph() {
    for (int i = 0; i < vertexCount; i++) {
        Node *current = adjacencyList[i];

        while (current != NULL) {
            Node *nodeToDelete = current;
            current = current->next;
            free(nodeToDelete);
        }

        adjacencyList[i] = NULL;
    }
}

The next pointer is saved before the current node is freed. After every node in one list is released, its head returns to NULL.

This cleanup is necessary because the adjacency-list version uses dynamic memory.

Adjacency List: Full Code

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 10

typedef struct Node {
    int vertex;
    struct Node *next;
} Node;

Node *adjacencyList[MAX_VERTICES];
int vertexCount;

void initializeListGraph(int vertices) {
    vertexCount = vertices;

    for (int i = 0; i < vertexCount; i++) {
        adjacencyList[i] = NULL;
    }
}

Node *createNode(int vertex) {
    Node *newNode = malloc(sizeof(Node));

    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }

    newNode->vertex = vertex;
    newNode->next = NULL;

    return newNode;
}

void addListEdge(int source, int destination) {
    Node *newNode = createNode(destination);
    newNode->next = adjacencyList[source];
    adjacencyList[source] = newNode;

    newNode = createNode(source);
    newNode->next = adjacencyList[destination];
    adjacencyList[destination] = newNode;
}

void displayListGraph() {
    printf("Adjacency List:\n");

    for (int i = 0; i < vertexCount; i++) {
        printf("%d -> ", i);

        Node *current = adjacencyList[i];
        while (current != NULL) {
            printf("%d -> ", current->vertex);
            current = current->next;
        }

        printf("NULL\n");
    }
}

void freeListGraph() {
    for (int i = 0; i < vertexCount; i++) {
        Node *current = adjacencyList[i];

        while (current != NULL) {
            Node *nodeToDelete = current;
            current = current->next;
            free(nodeToDelete);
        }

        adjacencyList[i] = NULL;
    }
}

int main() {
    initializeListGraph(5);

    addListEdge(0, 1);
    addListEdge(0, 2);
    addListEdge(1, 3);
    addListEdge(1, 4);
    addListEdge(2, 4);

    displayListGraph();
    freeListGraph();

    return 0;
}

Small Representation Modifications

Make the Graph Directed

Remove one line from addEdge:

void addEdge(int source, int destination) {
    graph[source][destination] = 1;
}

Now addEdge(0, 1) stores 0 -> 1 without automatically storing 1 -> 0.

Store Edge Weights

Add a weight parameter and store it instead of 1:

void addEdge(int source, int destination, int weight) {
    graph[source][destination] = weight;
    graph[destination][source] = weight;
}

In this version, 0 still means no edge. Positive values represent edge costs.

Remove an Edge

Reset both matrix cells:

void removeEdge(int source, int destination) {
    graph[source][destination] = 0;
    graph[destination][source] = 0;
}

Insertion and deletion are symmetrical: adding writes 1; removing writes 0.

Matrix vs. List

Question	Adjacency matrix	Adjacency list
Space	O(V²)	O(V + E)
Check one edge	O(1)	O(degree)
Visit all neighbors	O(V)	O(degree)
Beginner implementation	Simpler	More pointer work
Best fit	Dense graphs	Sparse graphs

We will use the matrix for the first BFS and DFS implementations so every neighbor check remains easy to trace. We will then show how the same traversals follow linked adjacency lists.

For the five-vertex sample, the matrix reserves 5 x 5 = 25 cells. The undirected adjacency list stores two neighbor nodes per edge, so five edges require ten nodes.

The difference becomes clearer for a graph with 1000 vertices and only 2000 edges:

matrix: 1,000,000 cells
list:   1,000 heads and about 4,000 neighbor nodes

The list is usually better for sparse graphs. The matrix remains useful when the graph is small or dense, or when the program frequently asks whether one particular edge exists.

One Traversal Pattern, Two Storage Rules

BFS and DFS are both graph traversals: systematic ways to discover every vertex reachable from a starting vertex.

They share the same overall pattern:

mark the start vertex as discovered
put the start vertex into the frontier

while the frontier is not empty:
    remove one vertex from the frontier
    process that vertex

    for each of its neighbors:
        if the neighbor is undiscovered:
            mark the neighbor as discovered
            put the neighbor into the frontier

The frontier contains vertices that have been discovered but whose neighbors have not yet been fully processed.

Only the frontier’s removal rule changes:

Traversal	Frontier	Removal rule	Resulting behavior
BFS	Queue	FIFO: oldest discovery first	Expands level by level
DFS	Stack	LIFO: newest discovery first	Follows one direction deeply

This is the central relationship:

same graph + same visited rule + queue frontier = BFS
same graph + same visited rule + stack frontier = DFS

The matrix and list versions also share this pattern. They differ only in how they enumerate the current vertex’s neighbors:

// Matrix: test every possible vertex.
for (int neighbor = 0; neighbor < vertexCount; neighbor++) {
    if (graph[current][neighbor] == 1) {
        // neighbor exists
    }
}

// List: follow only stored neighbors.
Node *currentNode = adjacencyList[current];
while (currentNode != NULL) {
    int neighbor = currentNode->vertex;
    // neighbor exists
    currentNode = currentNode->next;
}

Keeping this shared pattern in mind makes the four implementations easier to compare.

Why Do We Need a Visited Array?

The graph contains the undirected edge 0 -- 1.

Without a visited array:

visit 0
0 leads to 1
visit 1
1 leads back to 0
visit 0 again
0 leads to 1 again
...

The traversal may repeat forever.

We use:

int visited[MAX_VERTICES];

The meaning is:

visited[v] = 0 -> vertex v has not been discovered
visited[v] = 1 -> vertex v has been discovered

Before each new traversal, every entry must return to 0.

void resetVisited() {
    for (int i = 0; i < vertexCount; i++) {
        visited[i] = 0;
    }
}

Why Do the Reset Functions Appear?

C automatically initializes global integer arrays to 0, while the queue indexes and stack top are declared as -1. Therefore, a program that performs exactly one traversal could work without calling reset functions first.

The values change during a traversal, however:

BFS and DFS leave discovered vertices marked as 1 in visited.
Queue operations change front and rear.
Stack operations change top.

resetVisited() lets a later BFS or DFS start without inheriting the previous traversal’s marks. It is necessary when, for example, one program calls BFS and then DFS on the same graph.

resetQueue() restores the same queue state originally created by:

int front = -1;
int rear = -1;

The complete BFS shown here normally empties its queue and returns the indexes to -1, so resetting the queue is not strictly required for its first complete run. Calling resetQueue() still makes bfs() start from a known empty state if the queue was previously used or an earlier search stopped before draining it.

resetStack() does the same job for DFS by restoring top to -1.

These reset functions are initialization helpers. They are not special BFS or DFS operations. They make the traversal functions reusable and safer to call more than once.

Discovering Is Different from Processing

A vertex is discovered when it is first found and placed into the queue or stack. It is processed later, when it is removed and its neighbors are examined.

The implementations mark a vertex at discovery time:

visited[neighbor] = 1;
enqueue(neighbor);  // BFS

or:

visited[neighbor] = 1;
push(neighbor);     // DFS

Marking before insertion guarantees that each vertex enters the frontier at most once. If marking were delayed until removal, two different vertices could discover and insert the same neighbor before either copy was processed.

This invariant keeps the frontier size at most V and prevents repeated work.

Breadth-First Search

BFS visits vertices in layers.

Starting from vertex 0:

distance 0: 0
distance 1: 1, 2
distance 2: 3, 4

A queue creates this order. Vertices 1 and 2 are discovered first, so they are processed before 3 and 4.

Why FIFO Produces Layers

When BFS processes vertex 0, it enqueues every vertex one edge away. Those vertices are now at the front of the queue.

While processing them, BFS may discover vertices two edges away, but the new vertices join at the rear. FIFO order therefore finishes the entire one-edge layer before processing the two-edge layer.

The same argument continues for every distance:

all distance-0 vertices are processed before distance 1
all distance-1 vertices are processed before distance 2
all distance-2 vertices are processed before distance 3

For an unweighted graph, the first time BFS discovers a vertex is through a path containing the fewest possible edges. This is why BFS can calculate shortest unweighted distances.

Two optional arrays make that result useful:

distance[neighbor] = distance[current] + 1;
parent[neighbor] = current;

distance records the fewest edges from the start. Following parent backward reconstructs the corresponding path.

BFS Invariant

At the beginning of every BFS loop iteration:

every queued vertex is already marked visited;
no vertex appears in the queue more than once;
vertices leave the queue in nondecreasing distance from the start.

BFS does not guarantee a minimum-weight path when edges have different costs. A weighted graph requires an algorithm such as Dijkstra’s algorithm instead.

BFS Applications

Fewest-hop routes: BFS finds a path using the fewest edges in an unweighted graph.
Social-network distance: find friends, friends-of-friends, and the number of connections separating two people.
Network broadcasting: process devices in increasing hop distance from the sender.
Minimum-move puzzles: when every move has equal cost, each state is a vertex and BFS finds the fewest moves.
Nearby-place discovery: visit locations one connection away before locations two or more connections away.
Web crawling by depth: process directly linked pages before pages farther from the starting page.

These applications need BFS because arrival order matters. The queue keeps older, nearer discoveries in front of newer, farther discoveries.

BFS Queue Trace

The queue is shown from front to rear.

Start:
mark 0 visited
enqueue 0
queue = [0]

Dequeue 0:
visit 0
discover 1 -> mark and enqueue
discover 2 -> mark and enqueue
queue = [1, 2]

Dequeue 1:
visit 1
0 is already visited
discover 3 -> mark and enqueue
discover 4 -> mark and enqueue
queue = [2, 3, 4]

Dequeue 2:
visit 2
0 and 4 are already visited
queue = [3, 4]

Dequeue 3:
visit 3
1 is already visited
queue = [4]

Dequeue 4:
visit 4
1 and 2 are already visited
queue = []

BFS output:

0 1 2 3 4

Vertex 4 is marked when it is enqueued from vertex 1. Therefore vertex 2 does not enqueue it a second time.

BFS with an Adjacency Matrix: Function-by-Function

#include <stdio.h>

#define MAX_VERTICES 10

int graph[MAX_VERTICES][MAX_VERTICES];
int visited[MAX_VERTICES];
int vertexCount;

int queue[MAX_VERTICES];
int front = -1;
int rear = -1;

graph stores the adjacency matrix. visited records whether each vertex has already been discovered, and vertexCount records the active number of vertices.

The queue uses the same array, front, and rear design introduced in the Queues chapter. The empty state is front == -1 and rear == -1.

The queue operations keep the same state changes as that chapter. Two interface details are adapted for an algorithm:

enqueue does not print an insertion message, because BFS should print traversal output rather than queue-debugging output.
dequeue returns the removed value, because BFS needs that vertex as current.

The queue itself is still the same linear array queue.

void initializeGraph(int vertices) {
    vertexCount = vertices;

    for (int i = 0; i < vertexCount; i++) {
        for (int j = 0; j < vertexCount; j++) {
            graph[i][j] = 0;
        }
    }
}

initializeGraph(vertices) records the number of vertices and fills the active matrix with zeros. At this point, the vertices exist but no edges connect them.

The nested loops must run before edges are inserted. Otherwise, later initialization would erase the 1 values written by addEdge.

void addEdge(int source, int destination) {
    graph[source][destination] = 1;
    graph[destination][source] = 1;
}

addEdge writes both directions because this example uses an undirected graph. For addEdge(0, 1), the function sets both graph[0][1] and graph[1][0] to 1.

void resetVisited() {
    for (int i = 0; i < vertexCount; i++) {
        visited[i] = 0;
    }
}

resetVisited() clears marks left by an earlier traversal. The first traversal would also see zeros because visited is global, but explicitly resetting it allows bfs() to be called again.

void resetQueue() {
    front = -1;
    rear = -1;
}

resetQueue() restores the queue’s empty state. It does not need to erase old array values because front and rear determine which cells belong to the logical queue.

int isQueueEmpty() {
    return front == -1;
}

isQueueEmpty() returns true when no vertex is waiting. BFS uses this function as its loop condition.

void enqueue(int value) {
    if (rear == MAX_VERTICES - 1) {
        printf("Queue Overflow\n");
        return;
    }

    if (front == -1) {
        front = 0;
    }

    rear++;
    queue[rear] = value;
}

enqueue(value) inserts a discovered vertex at the rear. The first insertion changes front to 0; every insertion advances rear and stores the value.

BFS marks each vertex before enqueueing it, so no vertex should enter the queue twice. A queue with MAX_VERTICES cells is therefore large enough.

int dequeue() {
    if (isQueueEmpty()) {
        return -1;
    }

    int value = queue[front];
    front++;

    if (front > rear) {
        front = -1;
        rear = -1;
    }

    return value;
}

dequeue() saves and returns the vertex at the front. After advancing front, it restores the empty state if the last queued vertex was removed.

The returned value becomes the next vertex whose matrix row BFS scans.

void bfs(int start) {
    resetVisited();
    resetQueue();

    visited[start] = 1;
    enqueue(start);

    printf("BFS: ");

    while (!isQueueEmpty()) {
        int current = dequeue();
        printf("%d ", current);

        for (int neighbor = 0; neighbor < vertexCount; neighbor++) {
            if (graph[current][neighbor] == 1 && visited[neighbor] == 0) {
                visited[neighbor] = 1;
                enqueue(neighbor);
            }
        }
    }

    printf("\n");
}

bfs(start) first calls the two reset helpers that were defined above it. It then marks and enqueues the start vertex:

visited[start] = 1;
enqueue(start);

This order matters. If marking were delayed until dequeue, more than one edge could discover and enqueue the same vertex.

After the two lines execute for start = 0:

visited = [1, 0, 0, 0, 0]
queue   = [0]
front   = 0
rear    = 0

The loop condition checks whether work remains:

while (!isQueueEmpty()) {

During the first iteration, dequeue() returns 0. That value is stored in current and printed.

The neighbor loop then scans row 0 of the matrix:

row 0 = [0, 1, 1, 0, 0]

At neighbor = 1, an edge exists and visited[1] is 0. Vertex 1 is marked and enqueued. The same happens for vertex 2.

The combined condition requires both facts:

graph[current][neighbor] == 1 && visited[neighbor] == 0

An existing edge is not enough if the neighbor was already discovered.

When the queue becomes empty, the loop ends, BFS prints a newline, and control returns to main.

int main() {
    initializeGraph(5);

    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(1, 3);
    addEdge(1, 4);
    addEdge(2, 4);

    bfs(0);

    return 0;
}

main() appears last because it calls the functions defined above it. Execution still begins in main.

The program first initializes the matrix, inserts the five edges, and then calls bfs(0). The traversal prints:

BFS: 0 1 2 3 4

BFS with an Adjacency Matrix: Full Code

#include <stdio.h>

#define MAX_VERTICES 10

int graph[MAX_VERTICES][MAX_VERTICES];
int visited[MAX_VERTICES];
int vertexCount;

int queue[MAX_VERTICES];
int front = -1;
int rear = -1;

void initializeGraph(int vertices) {
    vertexCount = vertices;

    for (int i = 0; i < vertexCount; i++) {
        for (int j = 0; j < vertexCount; j++) {
            graph[i][j] = 0;
        }
    }
}

void addEdge(int source, int destination) {
    graph[source][destination] = 1;
    graph[destination][source] = 1;
}

void resetVisited() {
    for (int i = 0; i < vertexCount; i++) {
        visited[i] = 0;
    }
}

void resetQueue() {
    front = -1;
    rear = -1;
}

int isQueueEmpty() {
    return front == -1;
}

void enqueue(int value) {
    if (rear == MAX_VERTICES - 1) {
        printf("Queue Overflow\n");
        return;
    }

    if (front == -1) {
        front = 0;
    }

    rear++;
    queue[rear] = value;
}

int dequeue() {
    if (isQueueEmpty()) {
        return -1;
    }

    int value = queue[front];
    front++;

    if (front > rear) {
        front = -1;
        rear = -1;
    }

    return value;
}

void bfs(int start) {
    resetVisited();
    resetQueue();

    visited[start] = 1;
    enqueue(start);

    printf("BFS: ");

    while (!isQueueEmpty()) {
        int current = dequeue();
        printf("%d ", current);

        for (int neighbor = 0; neighbor < vertexCount; neighbor++) {
            if (graph[current][neighbor] == 1 && visited[neighbor] == 0) {
                visited[neighbor] = 1;
                enqueue(neighbor);
            }
        }
    }

    printf("\n");
}

int main() {
    initializeGraph(5);

    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(1, 3);
    addEdge(1, 4);
    addEdge(2, 4);

    bfs(0);

    return 0;
}

Depth-First Search

DFS repeatedly processes the most recently discovered vertex. A stack supplies this LIFO rule.

Starting at 0, DFS chooses one available direction and keeps extending it before returning to older alternatives:

visit 0
go to 1
go to 3
3 has no unvisited neighbor
return to the most recent unfinished choice
go to 4
go to 2

DFS output for the sample graph is:

0 1 3 4 2

Why LIFO Produces Depth

Suppose DFS discovers several neighbors of the current vertex. The last one pushed becomes the first one popped, so that newest route is processed immediately. Older alternatives remain lower in the stack until the newer route has no remaining work.

This is backtracking:

move forward along a route
save unfinished alternatives
when the route ends, return to the newest saved alternative

DFS does not visit vertices by distance. It may reach a nearby vertex through a long route before processing a shorter alternative, so DFS does not guarantee shortest paths.

DFS Invariant

At the beginning of every DFS loop iteration:

every stacked vertex is already marked visited;
no vertex appears in the stack more than once;
the top contains the newest unfinished discovery.

DFS is useful for reachability, connected components, cycle detection, dependency exploration, and backtracking. Additional arrays such as parent and discovery time can record the search tree and the order in which vertices were entered.

DFS Applications

Reachability: determine whether any path exists between two vertices.
Maze exploration: follow one route deeply and return when it reaches a dead end.
Connected groups: explore every vertex belonging to one connected component.
Cycle investigation: track whether exploration returns to a vertex on the current route.
Dependency exploration: fully inspect everything reachable through one dependency before moving to another.
Backtracking problems: use the current path, return to the last choice, and try another branch.

These applications benefit from DFS because the most recently discovered direction is explored first. This chapter’s main implementation uses the explicit array stack from the Stacks chapter; the recursive alternative receives the same LIFO behavior from the program’s call stack.

DFS Stack Trace

The stack is shown from bottom to top, with the top at the right.

Start:
mark 0 visited
push 0
stack = [0]

Pop 0:
visit 0
push 2, then push 1
stack = [2, 1]

Pop 1:
visit 1
0 is already visited
push 4, then push 3
stack = [2, 4, 3]

Pop 3:
visit 3
1 is already visited
stack = [2, 4]

Pop 4:
visit 4
1 and 2 are already visited
stack = [2]

Pop 2:
visit 2
0 and 4 are already visited
stack = []

Neighbors are checked from largest to smallest before they are pushed. LIFO reverses that insertion order, so the smallest-numbered available neighbor is processed first.

DFS with an Adjacency Matrix: Function-by-Function

#include <stdio.h>

#define MAX_VERTICES 10

int graph[MAX_VERTICES][MAX_VERTICES];
int visited[MAX_VERTICES];
int vertexCount;

int stack[MAX_VERTICES];
int top = -1;

graph, visited, and vertexCount have the same roles as in matrix BFS. The frontier is now the array stack from the Stacks chapter, controlled by top.

The stack operations keep the same state changes as that chapter. As with the BFS queue, the algorithm adapts the interface slightly:

push does not print a debugging message;
pop returns the removed vertex so DFS can store it in current.

void initializeGraph(int vertices) {
    vertexCount = vertices;

    for (int i = 0; i < vertexCount; i++) {
        for (int j = 0; j < vertexCount; j++) {
            graph[i][j] = 0;
        }
    }
}

initializeGraph records the active vertex count and clears the matrix before any edges are added.

void addEdge(int source, int destination) {
    graph[source][destination] = 1;
    graph[destination][source] = 1;
}

addEdge stores both directions of an undirected edge, exactly as it does in matrix BFS.

void resetVisited() {
    for (int i = 0; i < vertexCount; i++) {
        visited[i] = 0;
    }
}

resetVisited() clears marks from an earlier traversal.

void resetStack() {
    top = -1;
}

resetStack() restores the empty state introduced in the Stacks chapter. Old array values are ignored because no index at or below top is active.

int isStackEmpty() {
    return top == -1;
}

isStackEmpty() reports whether any discovered vertex is waiting to be processed.

void push(int value) {
    if (top == MAX_VERTICES - 1) {
        printf("Stack Overflow\n");
        return;
    }

    top++;
    stack[top] = value;
}

push(value) uses the same two updates as the array stack chapter: increase top, then store the value at stack[top].

int pop() {
    if (isStackEmpty()) {
        return -1;
    }

    int value = stack[top];
    top--;

    return value;
}

pop() saves stack[top], decreases top, and returns the saved vertex. Returning it instead of printing it lets DFS process that vertex.

void dfs(int start) {
    resetVisited();
    resetStack();

    visited[start] = 1;
    push(start);

    printf("DFS: ");

    while (!isStackEmpty()) {
        int current = pop();
        printf("%d ", current);

        for (int neighbor = vertexCount - 1; neighbor >= 0; neighbor--) {
            if (graph[current][neighbor] == 1 && visited[neighbor] == 0) {
                visited[neighbor] = 1;
                push(neighbor);
            }
        }
    }

    printf("\n");
}

Compare this directly with matrix BFS:

BFS: dequeue current -> scan neighbors -> enqueue each new neighbor
DFS: pop current     -> scan neighbors -> push each new neighbor

Both functions reset their state, mark and insert the start vertex, remove one current vertex at a time, print it, discover neighbors, and finish when their frontier is empty.

The DFS neighbor loop counts downward. Pushing 2 and then 1 leaves 1 on top, so smaller-numbered neighbors are processed first.

int main() {
    initializeGraph(5);

    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(1, 3);
    addEdge(1, 4);
    addEdge(2, 4);

    dfs(0);

    return 0;
}

main() builds the same matrix as BFS and changes only the traversal call. The output is:

DFS: 0 1 3 4 2

DFS with an Adjacency Matrix: Full Code

#include <stdio.h>

#define MAX_VERTICES 10

int graph[MAX_VERTICES][MAX_VERTICES];
int visited[MAX_VERTICES];
int vertexCount;

int stack[MAX_VERTICES];
int top = -1;

void initializeGraph(int vertices) {
    vertexCount = vertices;

    for (int i = 0; i < vertexCount; i++) {
        for (int j = 0; j < vertexCount; j++) {
            graph[i][j] = 0;
        }
    }
}

void addEdge(int source, int destination) {
    graph[source][destination] = 1;
    graph[destination][source] = 1;
}

void resetVisited() {
    for (int i = 0; i < vertexCount; i++) {
        visited[i] = 0;
    }
}

void resetStack() {
    top = -1;
}

int isStackEmpty() {
    return top == -1;
}

void push(int value) {
    if (top == MAX_VERTICES - 1) {
        printf("Stack Overflow\n");
        return;
    }

    top++;
    stack[top] = value;
}

int pop() {
    if (isStackEmpty()) {
        return -1;
    }

    int value = stack[top];
    top--;

    return value;
}

void dfs(int start) {
    resetVisited();
    resetStack();

    visited[start] = 1;
    push(start);

    printf("DFS: ");

    while (!isStackEmpty()) {
        int current = pop();
        printf("%d ", current);

        for (int neighbor = vertexCount - 1; neighbor >= 0; neighbor--) {
            if (graph[current][neighbor] == 1 && visited[neighbor] == 0) {
                visited[neighbor] = 1;
                push(neighbor);
            }
        }
    }

    printf("\n");
}

int main() {
    initializeGraph(5);

    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(1, 3);
    addEdge(1, 4);
    addEdge(2, 4);

    dfs(0);

    return 0;
}

Recursive DFS Alternative

DFS is also commonly written with recursion. Recursive calls use the program’s call stack, so the LIFO rule is still present even when push and pop are not written explicitly.

void dfsVisit(int current) {
    visited[current] = 1;
    printf("%d ", current);

    for (int neighbor = 0; neighbor < vertexCount; neighbor++) {
        if (graph[current][neighbor] == 1 && visited[neighbor] == 0) {
            dfsVisit(neighbor);
        }
    }
}

void dfsRecursive(int start) {
    resetVisited();

    printf("Recursive DFS: ");
    dfsVisit(start);
    printf("\n");
}

The explicit-stack implementation is presented first because it connects directly to the Stacks chapter and mirrors the queue-based BFS loop. The recursive form is shorter, but its stack operations are performed invisibly by function calls and returns.

BFS and DFS with a Linked Adjacency List

The matrix implementations scan a complete row to find neighbors. A linked adjacency list already contains exactly the neighbors that exist, so its traversals follow nodes instead of scanning every possible vertex.

The frontier and visited rules do not change:

BFS marks a vertex and places it in a queue.
DFS marks a vertex and places it in a stack.
Both mark a vertex before another edge can discover it again.

The implementation below builds one adjacency-list graph and runs both traversals. As in the Stacks and Queues chapters, we will examine each part before combining it into a complete program.

Adjacency-List Traversals: Function-by-Function

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 10

typedef struct Node {
    int vertex;
    struct Node *next;
} Node;

Node *adjacencyList[MAX_VERTICES];
int visited[MAX_VERTICES];
int vertexCount;

int queue[MAX_VERTICES];
int front = -1;
int rear = -1;

int stack[MAX_VERTICES];
int top = -1;

Each Node stores one neighbor. adjacencyList[v] points to the first neighbor of vertex v.

The visited array is shared by BFS and DFS, but each traversal resets it before starting. BFS uses the array queue from the Queues chapter, and DFS uses the array stack from the Stacks chapter.

void initializeListGraph(int vertices) {
    vertexCount = vertices;

    for (int i = 0; i < vertexCount; i++) {
        adjacencyList[i] = NULL;
    }
}

vertexCount records how many vertex indexes are active. Setting every head to NULL creates vertices with no neighbors:

0 -> NULL
1 -> NULL
2 -> NULL
3 -> NULL
4 -> NULL

Node *createNode(int vertex) {
    Node *newNode = malloc(sizeof(Node));

    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }

    newNode->vertex = vertex;
    newNode->next = NULL;

    return newNode;
}

malloc reserves memory for one linked-list node. The node stores the neighbor number received through vertex.

The null check must happen before using newNode. If allocation fails, the program reports the problem and stops instead of dereferencing an invalid pointer.

void addListEdge(int source, int destination) {
    Node *newNode = createNode(destination);
    newNode->next = adjacencyList[source];
    adjacencyList[source] = newNode;

    newNode = createNode(source);
    newNode->next = adjacencyList[destination];
    adjacencyList[destination] = newNode;
}

For addListEdge(0, 1), the first node puts 1 in vertex 0’s list. The second node puts 0 in vertex 1’s list:

0 -> 1 -> NULL
1 -> 0 -> NULL

Both nodes are needed because the sample graph is undirected. Inserting at the head takes constant time, but it also means the most recently added neighbor appears first during traversal.

void resetVisited() {
    for (int i = 0; i < vertexCount; i++) {
        visited[i] = 0;
    }
}

BFS changes visited, so DFS cannot reuse those old values. Calling resetVisited() before each traversal gives every vertex the undiscovered state again.

void resetQueue() {
    front = -1;
    rear = -1;
}

resetQueue() restores the empty state by moving both queue indexes back to -1. Old values may remain in the array, but they are outside the logical queue and will be overwritten by later insertions.

int isQueueEmpty() {
    return front == -1;
}

isQueueEmpty() returns true when no discovered vertex is waiting. BFS uses it to decide whether its processing loop should continue.

void enqueue(int value) {
    if (rear == MAX_VERTICES - 1) {
        printf("Queue Overflow\n");
        return;
    }

    if (front == -1) {
        front = 0;
    }

    rear++;
    queue[rear] = value;
}

The first insertion changes front from -1 to 0. Every insertion moves rear forward and stores the new vertex there.

BFS marks each vertex before enqueueing it, so no vertex should enter the queue more than once. A queue of MAX_VERTICES cells is therefore sufficient.

int dequeue() {
    if (isQueueEmpty()) {
        return -1;
    }

    int value = queue[front];
    front++;

    if (front > rear) {
        front = -1;
        rear = -1;
    }

    return value;
}

dequeue() saves the oldest queued vertex and advances front. When the last value is removed, both indexes return to -1.

The returned value becomes the current vertex whose adjacency list BFS will examine.

void resetStack() {
    top = -1;
}

resetStack() restores the empty stack state before DFS begins.

int isStackEmpty() {
    return top == -1;
}

isStackEmpty() tells DFS whether another discovered vertex remains to be processed.

void push(int value) {
    if (top == MAX_VERTICES - 1) {
        printf("Stack Overflow\n");
        return;
    }

    top++;
    stack[top] = value;
}

push(value) uses the same array and top updates as the Stacks chapter.

int pop() {
    if (isStackEmpty()) {
        return -1;
    }

    int value = stack[top];
    top--;

    return value;
}

pop() returns the newest stacked vertex so DFS can process it. Apart from returning instead of printing the value, this is the same pop operation used earlier.

void bfsList(int start) {
    resetVisited();
    resetQueue();

    visited[start] = 1;
    enqueue(start);

    printf("BFS with list: ");

    while (!isQueueEmpty()) {
        int current = dequeue();
        printf("%d ", current);

        Node *currentNode = adjacencyList[current];

        while (currentNode != NULL) {
            int neighbor = currentNode->vertex;

            if (visited[neighbor] == 0) {
                visited[neighbor] = 1;
                enqueue(neighbor);
            }

            currentNode = currentNode->next;
        }
    }

    printf("\n");
}

The outer while loop processes queued vertices in FIFO order. For each dequeued vertex, currentNode starts at the head of its neighbor list.

The inner while loop performs the work that the matrix version’s for loop performed. It reads the current neighbor, marks and enqueues that neighbor if necessary, and advances to the next node:

currentNode = currentNode->next;

The vertex is marked before enqueue(neighbor). This prevents two different edges from placing the same vertex in the queue twice.

void dfsList(int start) {
    resetVisited();
    resetStack();

    visited[start] = 1;
    push(start);

    printf("DFS with list: ");

    while (!isStackEmpty()) {
        int current = pop();
        printf("%d ", current);

        Node *currentNode = adjacencyList[current];

        while (currentNode != NULL) {
            int neighbor = currentNode->vertex;

            if (visited[neighbor] == 0) {
                visited[neighbor] = 1;
                push(neighbor);
            }

            currentNode = currentNode->next;
        }
    }

    printf("\n");
}

dfsList has the same structure as bfsList. It resets state, marks and inserts the start, removes one current vertex, prints it, and scans the same linked neighbor list.

Only the frontier operations differ:

bfsList: enqueue start -> dequeue current -> enqueue neighbors
dfsList: push start    -> pop current     -> push neighbors

Because a stack reverses insertion order, the last neighbor pushed is processed first.

void freeListGraph() {
    for (int i = 0; i < vertexCount; i++) {
        Node *current = adjacencyList[i];

        while (current != NULL) {
            Node *nodeToDelete = current;
            current = current->next;
            free(nodeToDelete);
        }

        adjacencyList[i] = NULL;
    }
}

The traversal algorithms only read the lists; they do not free them. Cleanup happens after both traversals finish.

The next pointer is saved before the current node is freed. Otherwise, the program would lose the address of the remaining list.

int main() {
    initializeListGraph(5);

    addListEdge(0, 1);
    addListEdge(0, 2);
    addListEdge(1, 3);
    addListEdge(1, 4);
    addListEdge(2, 4);

    bfsList(0);
    dfsList(0);

    freeListGraph();

    return 0;
}

main creates the same graph used by the matrix implementations. BFS runs first, DFS resets the visited array and runs second, and the allocated nodes are finally released.

Because addListEdge inserts at the head, the stored neighbor order is:

0 -> 2 -> 1 -> NULL
1 -> 4 -> 3 -> 0 -> NULL
2 -> 4 -> 0 -> NULL
3 -> 1 -> NULL
4 -> 2 -> 1 -> NULL

The program therefore prints:

BFS with list: 0 2 1 4 3
DFS with list: 0 1 3 4 2

BFS follows the stored list order because a queue preserves insertion order. DFS reverses that order because a stack removes the last pushed neighbor first. Different neighbor-storage orders can produce different valid traversal orders without changing reachability.

BFS and DFS with an Adjacency List: Full Code

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 10

typedef struct Node {
    int vertex;
    struct Node *next;
} Node;

Node *adjacencyList[MAX_VERTICES];
int visited[MAX_VERTICES];
int vertexCount;

int queue[MAX_VERTICES];
int front = -1;
int rear = -1;

int stack[MAX_VERTICES];
int top = -1;

void initializeListGraph(int vertices) {
    vertexCount = vertices;

    for (int i = 0; i < vertexCount; i++) {
        adjacencyList[i] = NULL;
    }
}

Node *createNode(int vertex) {
    Node *newNode = malloc(sizeof(Node));

    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }

    newNode->vertex = vertex;
    newNode->next = NULL;

    return newNode;
}

void addListEdge(int source, int destination) {
    Node *newNode = createNode(destination);
    newNode->next = adjacencyList[source];
    adjacencyList[source] = newNode;

    newNode = createNode(source);
    newNode->next = adjacencyList[destination];
    adjacencyList[destination] = newNode;
}

void resetVisited() {
    for (int i = 0; i < vertexCount; i++) {
        visited[i] = 0;
    }
}

void resetQueue() {
    front = -1;
    rear = -1;
}

int isQueueEmpty() {
    return front == -1;
}

void enqueue(int value) {
    if (rear == MAX_VERTICES - 1) {
        printf("Queue Overflow\n");
        return;
    }

    if (front == -1) {
        front = 0;
    }

    rear++;
    queue[rear] = value;
}

int dequeue() {
    if (isQueueEmpty()) {
        return -1;
    }

    int value = queue[front];
    front++;

    if (front > rear) {
        front = -1;
        rear = -1;
    }

    return value;
}

void resetStack() {
    top = -1;
}

int isStackEmpty() {
    return top == -1;
}

void push(int value) {
    if (top == MAX_VERTICES - 1) {
        printf("Stack Overflow\n");
        return;
    }

    top++;
    stack[top] = value;
}

int pop() {
    if (isStackEmpty()) {
        return -1;
    }

    int value = stack[top];
    top--;

    return value;
}

void bfsList(int start) {
    resetVisited();
    resetQueue();

    visited[start] = 1;
    enqueue(start);

    printf("BFS with list: ");

    while (!isQueueEmpty()) {
        int current = dequeue();
        printf("%d ", current);

        Node *currentNode = adjacencyList[current];

        while (currentNode != NULL) {
            int neighbor = currentNode->vertex;

            if (visited[neighbor] == 0) {
                visited[neighbor] = 1;
                enqueue(neighbor);
            }

            currentNode = currentNode->next;
        }
    }

    printf("\n");
}

void dfsList(int start) {
    resetVisited();
    resetStack();

    visited[start] = 1;
    push(start);

    printf("DFS with list: ");

    while (!isStackEmpty()) {
        int current = pop();
        printf("%d ", current);

        Node *currentNode = adjacencyList[current];

        while (currentNode != NULL) {
            int neighbor = currentNode->vertex;

            if (visited[neighbor] == 0) {
                visited[neighbor] = 1;
                push(neighbor);
            }

            currentNode = currentNode->next;
        }
    }

    printf("\n");
}

void freeListGraph() {
    for (int i = 0; i < vertexCount; i++) {
        Node *current = adjacencyList[i];

        while (current != NULL) {
            Node *nodeToDelete = current;
            current = current->next;
            free(nodeToDelete);
        }

        adjacencyList[i] = NULL;
    }
}

int main() {
    initializeListGraph(5);

    addListEdge(0, 1);
    addListEdge(0, 2);
    addListEdge(1, 3);
    addListEdge(1, 4);
    addListEdge(2, 4);

    bfsList(0);
    dfsList(0);

    freeListGraph();

    return 0;
}

BFS vs. DFS

Property	BFS	DFS
Main structure	Queue	Stack
Exploration	Layer by layer	One path deeply
Unweighted shortest path	Yes	No guarantee
Next vertex	Oldest discovery	Newest discovery
Common uses	Distance, levels, shortest unweighted paths	Reachability, components, cycles, ordering

Their implementations deliberately have the same shape:

Shared step	BFS	DFS
Clear traversal state	`resetVisited()`	`resetVisited()`
Clear frontier	`resetQueue()`	`resetStack()`
Insert start	`enqueue(start)`	`push(start)`
Continue condition	`!isQueueEmpty()`	`!isStackEmpty()`
Remove current	`dequeue()`	`pop()`
Insert new neighbor	`enqueue(neighbor)`	`push(neighbor)`

Both traversals mark vertices before inserting them and use the same matrix or list neighbor test. Changing FIFO queue operations to LIFO stack operations changes the traversal from breadth first to depth first.

Time and Space Complexity

With the adjacency matrix used here, every visited vertex scans an entire row, so the time is:

O(V²)

With an adjacency list, each vertex and edge is processed only as needed:

O(V + E)

The visited array uses O(V) space. In the worst case, either the BFS queue or DFS stack may also hold O(V) vertices.

The representation changes running time, but it does not change the meaning of BFS or DFS:

matrix BFS and list BFS both use FIFO
matrix DFS and list DFS both use LIFO

Choosing BFS or DFS

Ask what the problem needs:

Need the fewest unweighted edges? -> BFS
Need all vertices by distance layer? -> BFS
Need to explore one route deeply?   -> DFS
Need only to know whether a route exists? -> either
Need traversal of every component?  -> either, with repeated starts

BFS and DFS are not competing “better” and “worse” versions of the same algorithm. They process the frontier in different orders, so they are suited to different questions.

Disconnected Graphs

bfs(0) and dfs(0) visit only vertices reachable from 0.

Suppose vertex 5 has no edges. A traversal starting at 0 will not visit it because no path leads there.

To traverse every component, start a new traversal from each still-unvisited vertex. The Algorithms course develops this pattern further for component counting, cycle detection, and topological sorting.

Common Mistakes

Forgetting that valid vertex indexes are 0 through vertexCount - 1.
Adding only one matrix entry for an undirected edge.
Assuming a 0 weight can represent a real edge when 0 already means no edge.
Confusing a path with an edge: a path may contain many edges.
Assuming every graph is connected.
Reading matrix rows as destinations and columns as sources inconsistently.
Forgetting to free dynamically allocated adjacency-list nodes.
Creating only one neighbor node for an undirected adjacency-list edge.
Forgetting to reset visited before a new traversal.
Marking a BFS vertex too late and enqueuing duplicates.
Forgetting that BFS requires FIFO queue behavior.
Forgetting that iterative DFS requires LIFO stack behavior.
Scanning DFS neighbors in the wrong direction when a particular output order is expected.
Forgetting the visited check and repeatedly following an undirected edge backward.
Assuming DFS always returns a shortest path.
Expecting one unique traversal order even when neighbor order changes.

Practice

Draw a graph with vertices 0, 1, 2, 3 and edges (0,1), (0,2), (1,3), (2,3).
Write its adjacency matrix and adjacency list.
Add those edges using the full C program and verify the printed matrix.
Add removeEdge, remove (0,2), and verify that both symmetric cells become 0.
Convert addEdge to the directed version. What changes in the matrix?
Add a function hasEdge(source, destination) that returns 1 if an edge exists and 0 otherwise.
Add a function that prints every neighbor of a given vertex.
Count the degree of each vertex by summing its matrix row.
Trace BFS from vertex 1, showing the queue after every dequeue.
Trace recursive DFS from vertex 2, showing every call and return.
Modify BFS to store each vertex’s distance and parent.
Add an isolated sixth vertex and verify that traversal from 0 does not visit it.
Count the connected components by starting a new traversal at every unvisited vertex.
Run bfsList and dfsList on the linked representation. Identify the lines that differ between their queue and stack frontier operations.