Graphs

Graph models and terminology; edge lists, matrices, adjacency containers, weighted and dynamic storage, identity, validation, serialization, and introductory BFS/DFS.

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.

Physical Networks

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.

Digital Networks

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(void) {
    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(void) {
    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(void) {
    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(void) {
    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.

Storage Comparison

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)
Implementation surface	Direct indexing	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.

Representation Invariants

The same abstract graph can be stored in several forms, so each representation needs its own consistency rules.

For a simple undirected adjacency matrix:

graph[u][v] == graph[v][u]
graph[v][v] == 0 when self-loops are forbidden
every active endpoint lies in [0, vertexCount)

For an undirected adjacency list:

an entry u -> v has a matching entry v -> u
both stored directions carry the same weight
each destination is a valid vertex
parallel entries are absent when the graph is simple

One undirected logical edge is normally stored as two directed arcs in adjacency lists. An edge counter should increase once, not once per arc. A directed edge needs only its outgoing arc; an incoming-adjacency index is optional additional storage.

These invariants explain why an undirected update must commit both sides. If allocation for the reverse adjacency node fails, the operation must either undo the forward insertion or reserve both nodes before changing the graph.

Additional Graph Forms

A simple graph has no self-loops and no parallel edges. A multigraph permits several distinct edges between the same endpoint pair. Airline flights between the same cities or several physical cables between devices may need separate edge identities, labels, and weights.

A self-loop connects a vertex to itself. In a directed graph it contributes one to both indegree and outdegree. In the conventional undirected definition, it contributes two to degree because both incident ends meet the same vertex.

Some related terms distinguish repeated structure:

A walk follows consecutive edges and may repeat vertices or edges.
A trail is a walk that does not repeat an edge.
A simple path does not repeat a vertex.
An edge is incident to each endpoint it touches.

If parallel edges matter, a boolean matrix cell is insufficient. It can store a count, a collection of edge IDs, or be replaced by an edge list or adjacency lists that retain each edge as a separate record.

Weighted Presence

Using weight 0 to mean “no edge” silently prevents a legitimate zero-weight edge. Store presence separately from weight:

typedef struct {
    int weight;
    int present;
} WeightedCell;

int weighted_edge_set(WeightedCell matrix[][MAX_VERTICES],
                      int vertices, int source, int destination,
                      int weight, int directed) {
    if (source < 0 || source >= vertices ||
        destination < 0 || destination >= vertices) {
        return 0;
    }

    matrix[source][destination].present = 1;
    matrix[source][destination].weight = weight;
    if (!directed) {
        matrix[destination][source].present = 1;
        matrix[destination][source].weight = weight;
    }
    return 1;
}

Now present == 0 means no edge, while any int weight—including zero or a negative value—can be stored. Whether a particular graph algorithm accepts negative weights is a separate algorithmic condition.

Neighbor Containers

“Adjacency list” means one neighbor collection per vertex; that collection need not be a linked list.

Neighbor container	Edge lookup	Iteration	Update trade-off
Linked list	`O(degree)`	sequential, weak locality	local insertion, pointer overhead
Unsorted vector	`O(degree)`	compact and cache-friendly	amortized append, deletion may move an entry
Sorted vector	`O(log degree)` search	ordered and compact	insertion/deletion shifts entries
Hash set	expected `O(1)`	unordered	extra capacity and hashing

Choosing adjacency lists therefore does not completely determine edge-query cost. Select the inner container from degree distribution, ordering requirements, mutation frequency, and memory overhead.

Neighbor order is usually not part of the abstract graph. Changing insertion order or using unordered deletion can change a valid BFS or DFS visitation order without changing the graph itself.

Vertex Identity

Dense IDs 0 through V - 1 make matrix rows and outer adjacency arrays simple. External labels such as names can map to those IDs through a dictionary.

Appending a vertex to adjacency-list storage adds one empty neighbor collection. Growing an adjacency matrix requires a larger square and copying existing cells, which costs O(V^2).

Vertex deletion forces an identity decision:

Compact IDs: move the final vertex into the removed slot and repair every stored reference. Storage remains dense, but an existing vertex changes ID.
Stable IDs: leave a vacant slot or use a generation-checked handle. Such a handle stores both a slot number and that slot’s version; reusing the slot increments the version, so an old handle is rejected instead of silently naming the new vertex. IDs remain stable, but iteration must skip vacancies.

Deleting a directed vertex also requires removing incoming edges. If only outgoing lists are stored, finding every incoming edge may scan the entire graph. Maintaining both outgoing and incoming lists accelerates predecessor queries and deletion at the cost of duplicated state.

Graph Reference

The earlier matrix and linked-list programs make their mechanics visible. The following complete C17 program shows a more practical sparse representation: every vertex owns a dynamic array of outgoing arcs. It supports directed or undirected weighted graphs with a fixed vertex set, permits self-loops, rejects parallel edges, and accepts zero or negative weights because an arc’s existence—not its weight—records presence.

#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    size_t to;
    int weight;
} VectorArc;

typedef struct {
    VectorArc *items;
    size_t size;
    size_t capacity;
} VectorArcList;

typedef struct {
    VectorArcList *out;
    size_t vertex_count;
    size_t edge_count;
    bool directed;
} VectorGraph;

static void vector_arc_list_init(VectorArcList *list) {
    list->items = NULL;
    list->size = 0;
    list->capacity = 0;
}

static void vector_arc_list_destroy(VectorArcList *list) {
    free(list->items);
    vector_arc_list_init(list);
}

static bool vector_arc_list_reserve(VectorArcList *list,
                                    size_t requested) {
    if (requested <= list->capacity) {
        return true;
    }
    if (requested > SIZE_MAX / sizeof *list->items) {
        return false;
    }

    VectorArc *new_items = realloc(list->items,
                                   requested * sizeof *list->items);
    if (new_items == NULL) {
        return false;
    }
    list->items = new_items;
    list->capacity = requested;
    return true;
}

static bool vector_arc_list_ensure_room(VectorArcList *list) {
    if (list->size < list->capacity) {
        return true;
    }

    size_t next = list->capacity == 0 ? 4 : list->capacity * 2;
    if (next < list->capacity) {
        return false;
    }
    return vector_arc_list_reserve(list, next);
}

static size_t vector_arc_find(const VectorArcList *list, size_t to) {
    for (size_t i = 0; i < list->size; i++) {
        if (list->items[i].to == to) {
            return i;
        }
    }
    return SIZE_MAX;
}

static void vector_arc_append_reserved(VectorArcList *list,
                                       size_t to, int weight) {
    assert(list->size < list->capacity);
    list->items[list->size] = (VectorArc){.to = to, .weight = weight};
    list->size++;
}

static void vector_arc_erase_unordered(VectorArcList *list,
                                       size_t index) {
    assert(index < list->size);
    list->items[index] = list->items[list->size - 1];
    list->size--;
}

static bool vector_graph_init(VectorGraph *graph, size_t vertices,
                              bool directed) {
    graph->out = NULL;
    graph->vertex_count = 0;
    graph->edge_count = 0;
    graph->directed = directed;

    if (vertices == 0) {
        return true;
    }
    if (vertices > SIZE_MAX / sizeof *graph->out) {
        return false;
    }

    graph->out = malloc(vertices * sizeof *graph->out);
    if (graph->out == NULL) {
        return false;
    }
    graph->vertex_count = vertices;
    for (size_t vertex = 0; vertex < vertices; vertex++) {
        vector_arc_list_init(&graph->out[vertex]);
    }
    return true;
}

static void vector_graph_destroy(VectorGraph *graph) {
    for (size_t vertex = 0;
         vertex < graph->vertex_count;
         vertex++) {
        vector_arc_list_destroy(&graph->out[vertex]);
    }
    free(graph->out);
    graph->out = NULL;
    graph->vertex_count = 0;
    graph->edge_count = 0;
}

static bool vector_graph_has_edge(const VectorGraph *graph,
                                  size_t from, size_t to,
                                  int *weight) {
    if (from >= graph->vertex_count || to >= graph->vertex_count) {
        return false;
    }

    size_t index = vector_arc_find(&graph->out[from], to);
    if (index == SIZE_MAX) {
        return false;
    }
    if (weight != NULL) {
        *weight = graph->out[from].items[index].weight;
    }
    return true;
}

static bool vector_graph_add_edge(VectorGraph *graph,
                                  size_t from, size_t to,
                                  int weight) {
    if (from >= graph->vertex_count || to >= graph->vertex_count) {
        return false;
    }
    if (vector_arc_find(&graph->out[from], to) != SIZE_MAX) {
        return false;
    }

    VectorArcList *forward = &graph->out[from];
    VectorArcList *reverse = &graph->out[to];
    if (!vector_arc_list_ensure_room(forward)) {
        return false;
    }
    if (!graph->directed && from != to &&
        !vector_arc_list_ensure_room(reverse)) {
        return false;
    }

    vector_arc_append_reserved(forward, to, weight);
    if (!graph->directed && from != to) {
        vector_arc_append_reserved(reverse, from, weight);
    }
    graph->edge_count++;
    return true;
}

static bool vector_graph_remove_edge(VectorGraph *graph,
                                     size_t from, size_t to) {
    if (from >= graph->vertex_count || to >= graph->vertex_count) {
        return false;
    }

    size_t forward = vector_arc_find(&graph->out[from], to);
    if (forward == SIZE_MAX) {
        return false;
    }

    size_t reverse = SIZE_MAX;
    if (!graph->directed && from != to) {
        reverse = vector_arc_find(&graph->out[to], from);
        if (reverse == SIZE_MAX) {
            return false;
        }
    }

    vector_arc_erase_unordered(&graph->out[from], forward);
    if (reverse != SIZE_MAX) {
        vector_arc_erase_unordered(&graph->out[to], reverse);
    }
    graph->edge_count--;
    return true;
}

static void vector_graph_print(const VectorGraph *graph) {
    for (size_t from = 0; from < graph->vertex_count; from++) {
        printf("%zu:", from);
        const VectorArcList *neighbors = &graph->out[from];
        for (size_t i = 0; i < neighbors->size; i++) {
            printf(" (%zu,%d)",
                   neighbors->items[i].to,
                   neighbors->items[i].weight);
        }
        putchar('\n');
    }
}

int main(void) {
    VectorGraph graph;
    if (!vector_graph_init(&graph, 4, false)) {
        return EXIT_FAILURE;
    }

    struct {
        size_t from;
        size_t to;
        int weight;
    } edges[] = {
        {0, 1, 7},
        {0, 2, 4},
        {1, 2, 2},
        {1, 3, 6},
        {2, 3, 5}
    };

    size_t edge_total = sizeof edges / sizeof edges[0];
    for (size_t i = 0; i < edge_total; i++) {
        if (!vector_graph_add_edge(&graph,
                                   edges[i].from,
                                   edges[i].to,
                                   edges[i].weight)) {
            vector_graph_destroy(&graph);
            return EXIT_FAILURE;
        }
    }

    vector_graph_print(&graph);

    int weight;
    if (vector_graph_has_edge(&graph, 1, 3, &weight)) {
        printf("weight 1--3: %d\n", weight);
    }
    if (!vector_graph_remove_edge(&graph, 1, 2)) {
        vector_graph_destroy(&graph);
        return EXIT_FAILURE;
    }
    printf("edges after removal: %zu\n", graph.edge_count);

    vector_graph_destroy(&graph);
    return EXIT_SUCCESS;
}

For an undirected insertion, both neighbor arrays reserve space before either arc is appended. If the second reservation fails, the first array may have extra spare capacity, but the edge set and edge count remain unchanged. This is a strong failure guarantee for the graph’s observable value.

An undirected self-loop is represented by one stored arc and one logical edge. A degree function must nevertheless count that loop twice, following the mathematical definition of undirected degree. Deletion uses swap-with-last, so it is fast after lookup but does not preserve neighbor order. Any borrowed pointer into a neighbor array may also become invalid after insertion reallocates that array.

Representation Engineering

Let deg(u) mean the number of outgoing neighbors stored for vertex u. The table uses tight Theta bounds for the stated representations and assumes a simple graph, so insertion must first reject a duplicate edge.

Operation	Edge list	Matrix	Unsorted adjacency vectors
Storage	`Theta(E)`	`Theta(V^2)`	`Theta(V + E)`
Test edge `u,v`	`Theta(E)`	`Theta(1)`	`Theta(deg(u))`
Enumerate neighbors of `u`	`Theta(E)`	`Theta(V)`	`Theta(deg(u))`
Add edge	`Theta(E)`	`Theta(1)`	`Theta(deg(u))`, then amortized append
Remove edge	`Theta(E)`	`Theta(1)`	`Theta(deg(u))`
Iterate all edges	`Theta(E)`	`Theta(V^2)`	`Theta(V + E)`
Add vertex	usually amortized `Theta(1)`	`Theta(V^2)` resize	usually amortized `Theta(1)`
Remove vertex	`Theta(E)`	`Theta(V^2)`	`Theta(V + E)` without an incoming index

A multigraph that simply appends a new parallel edge can avoid duplicate detection, so edge insertion into a growable edge list or neighbor vector becomes amortized Theta(1). An undirected adjacency update may need to inspect and update both endpoints. Big-O alone also hides locality: contiguous vectors usually scan faster than separately allocated linked nodes even when both scans are linear.

Choose an edge list when work mainly scans or sorts all edges, neighbor queries are rare, or each edge needs an independent record. Choose a matrix when the vertex set is moderate and stable, the graph is dense, and arbitrary edge tests dominate. Choose adjacency collections when the graph is sparse and neighbor enumeration dominates. A hybrid such as a vector plus a hash index can combine fast iteration with expected constant-time edge lookup, but every update then has two representations to keep consistent.

Edge Identity

An array index is not automatically a stable edge ID. Swap-with-last deletion changes which edge occupies an index, while shifting deletion changes every later index. Stable choices include monotonically assigned IDs mapped to current slots, tombstoned records that are never renumbered, or handles containing a slot and generation. Generation-checked handles reject an old reference after its slot is reused. This distinction matters in multigraphs, where (u,v) does not identify one particular parallel edge.

Matrix Packing

An undirected matrix mirrors each ordinary edge across the diagonal. Storing only the upper triangle nearly halves its cells. For 0 <= u < v < V, a packed array that excludes the diagonal can use:

index(u, v) = u * (2V - u - 1) / 2 + (v - u - 1)

Normalize an unordered pair by swapping endpoints when u > v. If self-loops are allowed, store the diagonal separately or derive a second formula. Packing changes a constant factor, not the Theta(V^2) storage class, and the index arithmetic itself must be checked for size_t overflow.

Serialization

A durable graph file must state more than its visible edges. Record the vertex set or vertex count so isolated vertices survive; record whether the graph is directed; and preserve weight types, zero weights, self-loops, parallel-edge identities, labels, and any attributes. For an undirected graph, write each logical edge once rather than writing both stored arcs.

Loading is another mutation with a failure contract. Parse and validate into temporary storage, reject invalid endpoints or forbidden duplicates, verify any declared counts, and publish the new graph only after the whole input succeeds. A round trip—serialize, deserialize, then compare every vertex and edge—is stronger than checking that a file merely looks plausible.

Bulk Construction

Adding edges one at a time is convenient, but repeatedly growing every neighbor vector may allocate and copy more than necessary. When a complete edge list is available, construction can proceed in phases:

validate every endpoint and the loop/parallel-edge policy;
count the required outgoing arcs for each vertex;
allocate each neighbor collection once at its final size;
fill arcs using per-vertex write cursors;
validate counts, then publish the graph.

For an undirected ordinary edge (u,v), increase both degree counts. A self-loop follows the chosen storage convention: the reference representation stores one arc even though mathematical degree counts it twice. Directed construction increments only out_count[u]; a graph storing incoming lists also increments in_count[v].

This two-pass layout costs Theta(V + E) time and avoids intermediate capacity slack. It also makes a strong failure guarantee natural: all arrays belong to a temporary graph until every allocation and fill succeeds. On failure, destroy the temporary graph and leave the destination unchanged.

Duplicate rejection needs additional work. Sorting edge records, using a temporary set per vertex, or filling then sorting each neighbor collection can expose duplicates. The correct choice follows whether deterministic neighbor order, memory limits, or construction speed matters. A trusted already-normalized input may state uniqueness as a precondition, but an external file should be validated.

Mutation Versions

Graph iterators and algorithms often retain vertex or neighbor positions while they work. A neighbor-vector insertion may reallocate one vertex’s array; swap-with-last deletion may change which arc occupies an index; vertex compaction can rewrite IDs throughout the graph.

A graph-level version counter offers a simple fail-fast contract. Every structural edge or vertex mutation increments it. An iterator or traversal context saves the starting version and checks it before continuing. A mismatch reports invalidation instead of following stale storage.

One graph-wide counter is conservative: adding an edge in a distant component invalidates every iterator. Per-vertex neighbor versions permit finer-grained iteration but add more state and do not protect contexts that depend on the whole edge set. Choose the smallest contract the application can reason about reliably.

Changing only the weight of an existing edge may count as structural or nonstructural. If an iterator exposes weights or a running procedure relies on them, allowing silent change is unsafe. The interface should define whether weight replacement increments the same version.

An immutable snapshot avoids invalidation entirely. Build a new graph representation and keep the old one alive while readers finish. That costs additional memory and needs ownership or reference counting, but it can simplify read-heavy systems where consistent views matter more than in-place update speed.

Graph Oracles

For a small graph, a presence matrix is an excellent reference model even when the implementation under test uses adjacency vectors. Apply each generated vertex-valid edge insertion, removal, and weight replacement to both. Then compare every ordered endpoint pair, edge count, and—for undirected storage—degree under the documented loop convention.

Generate empty graphs, isolated vertices, loops, reverse directed pairs, duplicate attempts, parallel edges when permitted, and removals of absent edges. Bias vertex counts and degrees around vector growth boundaries. For stable handles, remove a vertex, reuse its slot, and confirm the former generation is rejected.

Allocation-failure tests should interrupt forward and reverse arc reservation separately. The logical undirected edge must be either present on both sides with one edge count or absent on both; a one-sided arc is never an acceptable partial success. Bulk loading should similarly leave the prior destination graph unchanged after any parse, validation, or allocation failure.

Comparing only one BFS or DFS order is not a complete representation test because several neighbor orders are valid. Compare the edge relation directly, then test traversal properties separately in the Algorithms course.

Graph Validation

Tests should attack the invariant, not only compare one printed picture:

Start with zero vertices, one vertex, and several isolated vertices.
Exercise both the accepted and rejected self-loop policy.
Add and remove the first edge, a middle edge, and the final edge.
Verify the duplicate or parallel-edge policy explicitly.
In a directed graph, test u -> v and v -> u independently.
After every undirected update, verify mirrored destinations and equal weights.
Store zero, negative, and extreme valid weights.
Reject endpoint IDs equal to or greater than vertex_count before indexing.
Force repeated neighbor-vector growth and check that every old edge survives.
Simulate allocation failure before a two-sided undirected insertion commits.

For small random graphs, perform the same sequence of updates on a matrix and an adjacency representation, then compare their complete edge sets. Independent representations make excellent test oracles because the same bug is less likely to occur in both.

Traversal Scope

This course uses BFS and DFS as introductory applications showing how graph representations interact with queues, stacks, recursion, and visited state. Their full correctness arguments, edge classifications, cycle detection, topological ordering, strongly connected components, and detailed complexity analysis belong to Algorithms: Graph Traversal.

Edit this graph and run both frontier disciplines on exactly the same edges. Highlighted discovery edges form the traversal tree; Back and Step expose when a vertex becomes discovered rather than merely processed. The interactive DFS stores a continuation frame for each active vertex, so it advances one neighbor at a time and produces the same kind of parent tree as recursive DFS. The compact C stack examples later in this chapter push all currently unvisited neighbors at once; they are useful LIFO-frontier reachability traversals, but their push-time parent edges and timestamps should not be interpreted as a canonical recursive DFS forest.

Enable JavaScript to use the graph-traversal experiment.

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(void) {
    initializeGraph(5);

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

    bfs(0);

    return 0;
}

main(void) 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(void) {
    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 active vertex. Recursion supplies this LIFO rule automatically. An equivalent explicit stack stores a continuation frame containing a vertex and the next neighbor that its suspended call must inspect.

The first explicit-stack code below uses a smaller variation: it pushes every currently unvisited neighbor and marks each one immediately. That LIFO frontier still visits every reachable vertex and often produces the familiar deep-looking order, which makes it useful for learning stack mechanics and for reachability. It does not suspend one exact neighbor loop, so on graphs with cross-connections its push-time parent choices can differ from recursive DFS. The distinction matters for canonical DFS trees, discovery/finish timestamps, edge classification, and algorithms based on those properties.

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

In the compact frontier variation, suppose one vertex pushes several neighbors. The last one pushed becomes the first one popped, so that newest option is processed immediately. Older options remain lower in the stack. This creates a LIFO reachability order, but those older siblings were already marked even though their own neighbor scans have not begun.

A canonical DFS instead keeps the current vertex’s unfinished neighbor scan on the stack:

move forward along a route
save the current vertex and its next neighbor position
when the route ends, return to the newest saved alternative

That is exact backtracking. A recursive call frame stores the continuation implicitly; an iterative implementation stores (vertex, next_neighbor) explicitly.

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.

Frontier 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.

This invariant is sufficient for reachability and connected-component membership. Canonical DFS maintains a different active-path invariant: each frame represents a suspended neighbor scan, and the frames form the current root-to-vertex route. Parent arrays, discovery and finish times, current-path cycle checks, and DFS edge classifications should be built from that recursive or continuation-frame form, not from the compact push-all frontier’s push order.

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.

Reachability and connected-group exploration work with either stack form. Maze-style backtracking, current-route cycle reasoning, dependency finishing order, and other applications that depend on the recursive DFS forest require recursion or explicit continuation frames. This chapter retains the push-all array stack to connect the representation directly to the Stacks chapter, then shows the recursive form; Algorithms develops the canonical invariants and applications.

DFS Frontier 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. This compact DFS function is the push-all LIFO frontier variation. It establishes reachability and the shown visitation order, but recording parent when pushing would not necessarily reproduce the recursive DFS parent forest.

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

int main(void) {
    initializeGraph(5);

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

    dfs(0);

    return 0;
}

main(void) 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(void) {
    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 push-all explicit-stack implementation is presented first because it connects directly to the Stacks chapter and mirrors the queue-based BFS loop. This recursive form is not merely shorter: each call suspends its neighbor loop until the chosen child returns, so it provides the canonical DFS parent tree and supports discovery/finish timestamps. An iterative equivalent stores a frame containing the vertex and its next neighbor position instead of storing only vertex IDs.

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 compact 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 push-all frontier structure as bfsList. It resets state, marks and inserts the start, removes one current vertex, prints it, and scans the same linked neighbor list. It is therefore a LIFO reachability traversal, not a continuation-frame implementation of recursive DFS.

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(void) {
    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(void) {
    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 and components; canonical DFS also supports cycles and 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 compact traversals mark vertices before inserting them and use the same matrix or list neighbor test. Changing FIFO queue operations to LIFO stack operations changes breadth-first processing into a LIFO reachability traversal. To match recursive DFS exactly, replace the vertex-only stack with continuation frames and advance one neighbor per active frame.

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.

Graph Hazards

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.

Graph 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.

Graph Challenges

Arc Symmetry

Explain why one undirected edge becomes two neighbor entries in an adjacency list but one conceptual edge in the graph.

Representation Trace

For a four-vertex graph with one isolated vertex, draw the matrix and adjacency lists after each edge insertion and deletion.

Graph Representations

Write validators for undirected matrix symmetry and mirrored adjacency-list arcs.
Replace the weighted matrix’s zero sentinel with separate presence and weight fields, then store a zero-weight edge.
Represent a multigraph with stable edge IDs and remove only one of several parallel edges.
Add vertex append to both matrix and adjacency-list representations and measure the amount of copied storage.

Neighbor Storage

Replace linked neighbor lists with dynamic arrays and compare memory layout, edge lookup, iteration, and deletion behavior.
Maintain both incoming and outgoing lists for a directed graph and state the invariant connecting them.

Stable Vertices

Design stable vertex handles that reject references to a removed slot after that slot is reused. Specify the slot, version, validation, and overflow rules.

Hybrid Storage

Build a hybrid neighbor vector plus hash index. State the invariant connecting the two structures and make every failed insertion leave both unchanged.
Store an undirected Boolean matrix as packed bits in one triangle. Derive and test the index formula at row boundaries and near the largest supported vertex count.
Serialize and deserialize a weighted graph, preserving isolated vertices, zero-weight edges, direction, loops, and any parallel-edge identities allowed by your API.