Implementation (Part 2)

Lesson 6 of 9 in Coddy's Depth-First Search - Graph Algorithms course.

Now we traverse the whole graph with a stack.

Challenge

Medium

Now build the full traversal.

Write a function named dfs that takes n, the flat edges array (undirected), and a start vertex, and returns the order in which DFS visits vertices, beginning at start.

First build the adjacency list (sort each vertex's neighbors ascending). Then run an iterative DFS with a stack. Only vertices reachable from start are visited.

To visit neighbors in ascending order, push them onto the stack from largest to smallest.

Try it yourself

#include <stdlib.h>

int* dfs(int n, int* edges, int edges_size, int start, int* returnSize) {
    // Write code here
    *returnSize = 0;
    return edges;
}

Test yourself

This lesson includes a short quiz. Start the lesson to answer it and track your progress.

All lessons in Depth-First Search - Graph Algorithms

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo Code Implementation (Part 1)Implementation (Part 2) Project lesson

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2