Топологическая сортировка на C: Погружаемся в мир алгоритмов

Привет, дорогие читатели! Сегодня мы с вами отправимся в увлекательное путешествие по миру алгоритмов, а именно — в мир топологической сортировки. Если вы когда-либо задавались вопросом, как организовать задачи так, чтобы они выполнялись в правильном порядке, то эта статья для вас. Мы разберем, что такое топологическая сортировка, как она работает, и, конечно же, как реализовать ее на языке программирования C.

Топологическая сортировка — это не просто набор абстрактных понятий. Это мощный инструмент, который используется в самых разных областях, от компиляции кода до планирования задач. Итак, давайте начнем с основ.

Что такое топологическая сортировка?

Топологическая сортировка — это упорядочивание вершин ориентированного ациклического графа (ОАГ) в линейном порядке, так что для каждого ребра (u, v) вершина u предшествует вершине v. Звучит немного сложно? Давайте разберем это на простом примере.

Представьте, что у вас есть несколько задач, которые нужно выполнить. Некоторые из этих задач зависят от других. Например, чтобы закончить проект, вам сначала нужно написать код, а затем протестировать его. В этом случае задача “тестирование” зависит от задачи “кодирование”. Топологическая сортировка поможет вам определить порядок выполнения этих задач.

Применение топологической сортировки

Топологическая сортировка находит применение в самых разных областях:

• Компиляция программ: компиляторы используют топологическую сортировку для определения порядка компиляции исходных файлов.
• Планирование задач: в системах управления проектами для определения порядка выполнения задач.
• Оптимизация маршрутов: в системах, где необходимо найти оптимальный путь для выполнения задач.

Как работает топологическая сортировка?

Существует несколько алгоритмов для выполнения топологической сортировки, но мы сосредоточимся на двух самых популярных: алгоритм Кана и алгоритм глубинного поиска (DFS). Давайте рассмотрим их по порядку.

Алгоритм Кана

Алгоритм Кана основан на использовании входной степени вершин. Входная степень вершины — это количество рёбер, которые ведут к этой вершине. Алгоритм можно описать следующими шагами:

1. Создайте граф и вычислите входные степени всех вершин.
2. Поместите все вершины с нулевой входной степенью в очередь.
3. Пока очередь не пуста, извлекайте вершину из очереди и добавляйте ее в результирующий список.
4. Для каждого соседа извлеченной вершины уменьшайте его входную степень на 1. Если входная степень соседа стала равной 0, добавьте его в очередь.

Пример реализации алгоритма Кана на C

Теперь давайте посмотрим, как реализовать алгоритм Кана на языке C. Ниже приведен пример кода:

#include 
#include 

#define MAX 100

int graph[MAX][MAX], in_degree[MAX], queue[MAX], front = -1, rear = -1;
int n;

void topological_sort() {
    for (int i = 0; i < n; i++) {
        if (in_degree[i] == 0) {
            queue[++rear] = i;
        }
    }

    while (front != rear) {
        int u = queue[++front];
        printf("%d ", u);

        for (int v = 0; v < n; v++) {
            if (graph[u][v] == 1) {
                in_degree[v]--;
                if (in_degree[v] == 0) {
                    queue[++rear] = v;
                }
            }
        }
    }
}

int main() {
    printf("Введите количество вершин: ");
    scanf("%d", &n);

    printf("Введите матрицу смежности:n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &graph[i][j]);
            if (graph[i][j] == 1) {
                in_degree[j]++;
            }
        }
    }

    printf("Топологическая сортировка: ");
    topological_sort();
    return 0;
}

В этом коде мы создаем граф с помощью матрицы смежности и вычисляем входные степени вершин. Затем с помощью алгоритма Кана мы выводим топологическую сортировку.

Алгоритм глубинного поиска (DFS)

Другой подход к топологической сортировке — это использование алгоритма глубинного поиска. Этот метод работает немного иначе и может быть более интуитивно понятным для тех, кто знаком с DFS. Алгоритм можно описать следующими шагами:

1. Создайте граф и массив для отслеживания посещенных вершин.
2. Для каждой непосещенной вершины выполните DFS, помечая вершину как посещенную.
3. После завершения обхода добавьте вершину в стек.
4. В конце извлеките вершины из стека, чтобы получить топологическую сортировку.

Пример реализации алгоритма DFS на C

Теперь давайте посмотрим, как реализовать алгоритм DFS для топологической сортировки на C:

#include 
#include 

#define MAX 100

int graph[MAX][MAX], visited[MAX], n;
int stack[MAX], top = -1;

void dfs(int v) {
    visited[v] = 1;

    for (int i = 0; i < n; i++) {
        if (graph[v][i] == 1 && !visited[i]) {
            dfs(i);
        }
    }

    stack[++top] = v;
}

void topological_sort() {
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i);
        }
    }

    printf("Топологическая сортировка: ");
    while (top != -1) {
        printf("%d ", stack[top--]);
    }
}

int main() {
    printf("Введите количество вершин: ");
    scanf("%d", &n);

    printf("Введите матрицу смежности:n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &graph[i][j]);
        }
    }

    topological_sort();
    return 0;
}

В этом коде мы используем DFS для обхода графа и помещаем вершины в стек. В конце мы извлекаем вершины из стека, чтобы получить топологическую сортировку.

Сравнение алгоритмов

Теперь, когда мы рассмотрели оба алгоритма, давайте сравним их по нескольким критериям:

Как видно, оба алгоритма имеют схожую временную сложность, но различаются по подходу. Выбор алгоритма зависит от конкретной задачи и предпочтений разработчика.

Заключение

Топологическая сортировка — это мощный инструмент для решения множества задач, связанных с упорядочиванием зависимостей. Мы рассмотрели, что такое топологическая сортировка, как она работает и как реализовать ее на языке C с помощью двух популярных алгоритмов. Надеюсь, эта статья была полезной и понятной для вас!

Не забывайте, что практика — это ключ к успеху. Попробуйте реализовать свои собственные примеры топологической сортировки и экспериментируйте с различными графами. Удачи вам в ваших начинаниях!