дискретная математика графы

Ответ от Ёистемный Администратор[гуру]
Представь, что нужно, к примеру, установить кучу программ, но они зависят одна от другой (стрелки графа - это зависимости) . Поэтому в любом порядке их устанавливать нельзя, ибо тогда одна программа начнет ругаться, что не установлена другая. Топологическая сортировка позволяет найти такую последовательность, при которой проблем не будет (на графе из каждой вершины стрелки идут только в те вершины, которые в полученной в результате сортировки последовательности стоят после нее) . Самый простой пример - программа A зависит от программы B, а та в свою очередь зависит от программы C. Тогда искомый порядок: (C,B,A).
На Википедии есть и другие примеры, чть более сложные.
Принцип работы алгоритма состоит в том, что на каждом шаге из графа выбирается та вершина, в которую не идет никакая стрелка и добавляется в последовательность. А все стрелки из этой вершины соответственно удаляются вместе с ней из графа. На следующем шаге - другая вершина и т. д.