Implementation (Part 1)

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

We start with in-degrees, the heart of Kahn's algorithm.

Challenge

Easy

The engine of Kahn's algorithm is the in-degree of each vertex. Let's compute that first.

Write a function named inDegrees that takes n and the flat edges array (directed pairs u -> v), and returns an array where position v is the number of edges pointing into vertex v.

For example, inDegrees(4, [0,1, 0,2, 1,3, 2,3]) returns [0, 1, 1, 2].

Try it yourself

#include <stdlib.h>

int* inDegrees(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 CodeImplementation (Part 1)Implementation (Part 2)

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2