Implementation (Part 2)
Урок 6 из 9 курса Топологическая сортировка — алгоритмы на графах на Coddy.
Теперь мы многократно удаляем вершины с входящей степенью 0, чтобы построить порядок.
Задание
СреднеТеперь постройте полный порядок.
Напишите функцию с именем topologicalSort, которая принимает n и плоский массив edges (ориентированные ребра u -> v) и возвращает топологический порядок вершин.
Используйте алгоритм Кана: вычислите полустепени захода (in-degrees), затем многократно выбирайте наименьшую вершину с полустепенью захода 0, добавляйте её в результат и уменьшайте полустепень захода её соседей, в которые ведут исходящие ребра. Входные данные для этой задачи являются ациклическими.
Выбор наименьшей доступной вершины на каждом шаге делает ответ уникальным.
Попробуйте сами
#include <stdlib.h>
int* topologicalSort(int n, int* edges, int edges_size, int* returnSize) {
// Напишите код здесь
*returnSize = 0;
return edges;
}
Проверьте себяВ этом уроке есть небольшой тест. Начните урок, чтобы ответить на вопросы и сохранить прогресс.
Все уроки раздела Топологическая сортировка — алгоритмы на графах
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity