DFS
Lesson 11 of 14 in Coddy's Graphs - Data Structures Series #9 course.
Depth-First Search goes deep before going wide. Starting at a vertex, it follows one edge as far as possible, then backtracks and tries the next one. The iterative version uses a stack: pop a vertex, record it, push its unvisited neighbors back on.
To make DFS produce a deterministic traversal order in this challenge, push the neighbors in reverse-sorted order. That way the smallest neighbor lands on top of the stack and gets processed first, matching the order a recursive DFS over ascending neighbors would produce.
Watch out for a vertex being pushed twice (different neighbors can both have it). Check the visited set at the top of the loop and skip if already visited.
Challenge
EasyWrite a function dfs that gets a 2D int array adjacency (each row is a [u, v] edge) and an int start, and returns the DFS visit order from start as a list of ints.
Build the graph by adding each edge. Iterative DFS using a stack: pop a vertex, if not visited, record it and push its neighbors in reverse-sorted order so the smallest is processed first.
You must use the Graph class (provided in graph) - do not use language built-ins (maps, sets) to model the adjacency. Auxiliary data for the algorithm (visited sets, stacks) may use stdlib types.
Try it yourself
#include <stdio.h>
#include "solution.h"
int main() {
int n, m, start;
if (scanf("%d %d %d", &n, &m, &start) != 3) return 0;
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
int out[MAX_VERTICES];
int outn = dfs(adjacency, m, start, out);
for (int i = 0; i < outn; i++) {
if (i > 0) printf(" ");
printf("%d", out[i]);
}
printf("\n");
return 0;
}