Graph traversal — DFS

#include <stdio.h>

stdio.h declares printf, puts, getchar and putchar. The input helper reads characters with getchar; the main program prints operation results using the output functions.

#include <stdlib.h>

stdlib.h declares strtol for converting an integer token. It also declares malloc and free, which the linked structures and tree programs use to obtain and release node storage.

#include <string.h>

string.h declares utilities such as memset. It is part of the shared header list; merely including a header does not call any function or change stored values.

#include <ctype.h>
#include <errno.h>

ctype.h supplies isspace for recognising whitespace. errno.h supplies errno so the program can detect a range error reported by strtol.

/* Read a complete integer token; reject bad or oversized input safely. */
int readInt(int *value) {

The comment states the purpose of readInt. Its int *value parameter receives the address of a caller variable. The helper returns 1 after storing a valid value there, or 0 on failure; these flags are separate from main’s process exit status.

    char token[64];
    int ch;
    size_t used = 0;

token holds up to 63 input characters and a null terminator. ch is int so it can distinguish character input from EOF. used starts at zero and counts the stored token characters.

    while ((ch = getchar()) != EOF && isspace((unsigned char)ch)) { }
    if (ch == EOF) return 0;

getchar reads one character at a time. The loop discards whitespace before the token. The unsigned-char cast supplies an allowed argument to isspace. If EOF is reached before a token starts, return 0 without changing the caller variable.

    do {
        if (used < sizeof token - 1) token[used++] = (char)ch;

The do-while body handles the first non-whitespace character already read. The size check leaves one buffer slot for a null terminator. used++ uses the old index for storage, then advances the count.

        else {
            while ((ch = getchar()) != EOF && !isspace((unsigned char)ch)) { }
            return 0;
        }

When the buffer has no character space left, consume the rest of that token through whitespace or EOF, then return failure. The program does not silently treat a truncated prefix as the full input number.

        ch = getchar();
    } while (ch != EOF && !isspace((unsigned char)ch));

Keep collecting until whitespace or EOF. The terminating whitespace has been consumed by getchar; it is not stored as part of the token.

    token[used] = '\0';
    char *end;
    errno = 0;

Write the null terminator after the stored token. end will identify where conversion stopped. Reset errno before strtol so a previous library error cannot be mistaken for this conversion’s result.

    long result = strtol(token, &end, 10);

strtol reads token in base 10 and returns a long. Passing &end lets it write the address of the first unconverted character. A sign such as - is allowed as part of a valid integer token.

    if (errno || *end != '\0' || result < -1000000 || result > 1000000) return 0;

A nonzero errno rejects a reported conversion error. *end must be the null terminator, so input such as 12x is rejected rather than accepted as 12. The allowed value range is -1,000,000 to 1,000,000.

    *value = (int)result;
    return 1;
}

After validation, cast result to int and assign it through *value. Return 1 for success. The brace ends readInt. The caller variable remains unchanged on the earlier failure returns.

#define MAX_VERTICES 20
int graph[MAX_VERTICES][MAX_VERTICES];
int visited[MAX_VERTICES];
int vertices;

MAX_VERTICES is 20. The file-scope arrays graph and visited have static storage and start at zero. graph[u][v] records an edge, visited[v] records discovery, and vertices is the number of active vertex indexes, 0 through vertices - 1.

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

dfs receives a vertex index. Mark it visited immediately, then print it. Early marking prevents a later edge in a cycle from recursively revisiting the same vertex.

    for (int neighbour = 0; neighbour < vertices; ++neighbour)
        if (graph[vertex][neighbour] && !visited[neighbour]) dfs(neighbour);
}

Scan possible neighbour indexes in ascending order. Recurse only if the matrix records an edge and the neighbour has not been visited. Each call explores its deeper branch before returning to continue the current row scan; this gives depth-first order.

/* Input: V E, E undirected edges (u v), then start vertex. */
int main(void) {

Read the vertex count and edge count, then that many undirected endpoint pairs, then the start vertex. These graph inputs differ from the command-driven stack and list programs.

    int edges, start;
    if (!readInt(&vertices) || !readInt(&edges) || vertices < 1 ||
        vertices > MAX_VERTICES || edges < 0 || edges > vertices * (vertices - 1) / 2) goto invalid;

Declare edges and start, then read the vertex and edge counts. The vertex count must be 1–20 and edges must be nonnegative and no larger than V(V - 1)/2, the maximum for a simple undirected graph without self-loops. Short-circuit OR prevents later expressions from using a value whose read failed.

    for (int i = 0; i < edges; ++i) {
        int u, v;

Loop edges times. u and v are the endpoint indexes of the current undirected connection.

        if (!readInt(&u) || !readInt(&v) || u < 0 || u >= vertices ||
            v < 0 || v >= vertices || u == v || graph[u][v]) goto invalid;

Each endpoint must be between 0 and vertices - 1. u == v rejects self-loops, and graph[u][v] rejects a repeated edge. Earlier OR conditions check bounds before the matrix lookup, so invalid indexes are not used.

        graph[u][v] = graph[v][u] = 1;
    }

Set graph[u][v] and graph[v][u] to 1. The equal entries let either endpoint discover the other. The brace ends edge input.

    if (!readInt(&start) || start < 0 || start >= vertices) goto invalid;
    printf("DFS (start component):"); dfs(start); putchar('\n');

Check the start index, then call dfs and print a newline. The first report contains only vertices reachable from the supplied start; it does not invent edges to disconnected vertices.

    /* Optional second report includes disconnected and isolated vertices. */
    memset(visited, 0, sizeof visited);
    printf("DFS (all components):"); dfs(start);

The comment explains the optional all-components report. memset sets the visited array back to zero so the second traversal can visit the start component again. Then print its new label and traverse from start.

    for (int v = 0; v < vertices; ++v) if (!visited[v]) dfs(v);
    putchar('\n'); return 0;

Inspect vertex indexes in ascending order. Start another traversal only for an unvisited vertex, covering disconnected components and isolated vertices exactly once in this report. End the line and return success.

invalid:
    puts("Invalid graph input."); return 1;
}

The earlier goto invalid statements arrive at this label. Print the graph-input error and return failure. The graph arrays do not own separately allocated nodes requiring cleanup.