Implementation (Part 2)

Lesson 6 of 9 in Coddy's Topological Sort - Graph Algorithms course.

Now we repeatedly remove in-degree-0 vertices to build the order.

Challenge

Medium

Now build the full ordering.

Write a function named topologicalSort that takes n and the flat edges array (directed u -> v), and returns a topological order of the vertices.

Use Kahn's algorithm: compute in-degrees, then repeatedly take the smallest vertex with in-degree 0, append it, and reduce the in-degree of its out-neighbors. The inputs for this challenge are acyclic.

Taking the smallest available vertex each step makes the answer unique.

Try it yourself

#include <stdlib.h>

int* topologicalSort(int n, int* edges, int edges_size, 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 Topological Sort - 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