Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty

Определение графа

Граф - множество точек, соединённых между собой рёбрами.

Типы графов:

Ориентированные

Ориентированными графами называют графы, в которых рёбра имеют направление

@font-face {

font-family: "Virgil";

src: url("https://excalidraw.com/Virgil.woff2");

}

@font-face {

font-family: "Cascadia";

src: url("https://excalidraw.com/Cascadia.woff2");

}

1324

Неориентированные

Неориентированные графами называют графы, в которых рёбра не имеют направление

@font-face {

font-family: "Virgil";

src: url("https://excalidraw.com/Virgil.woff2");

}

@font-face {

font-family: "Cascadia";

src: url("https://excalidraw.com/Cascadia.woff2");

}

1324

Методы хранения графов

Хранить граф в виде матрицы смежности

@font-face {

font-family: "Virgil";

src: url("https://excalidraw.com/Virgil.woff2");

}

@font-face {

font-family: "Cascadia";

src: url("https://excalidraw.com/Cascadia.woff2");

}

123412341111111000000000МАТРИЦА СМЕЖНОСТИ2143СООТВЕТСТВУЮЩИЙ ГРАФ

Пример:

@font-face {

font-family: "Virgil";

src: url("https://excalidraw.com/Virgil.woff2");

}

@font-face {

font-family: "Cascadia";

src: url("https://excalidraw.com/Cascadia.woff2");

}

32123

Хранить граф в виде списка рёбер

@font-face {

font-family: "Virgil";

src: url("https://excalidraw.com/Virgil.woff2");

}

@font-face {

font-family: "Cascadia";

src: url("https://excalidraw.com/Cascadia.woff2");

}

(0; 1)(0; 2)(1; 2)(1; 3)(2; 1)(3; 2)1023СПИСОК РЁБЕРСООТВЕТСТВУЮЩИЙ ГРАФ

Пример:

@font-face {

font-family: "Virgil";

src: url("https://excalidraw.com/Virgil.woff2");

}

@font-face {

font-family: "Cascadia";

src: url("https://excalidraw.com/Cascadia.woff2");

}

(1; 2)(2; 1)12

Хранить граф в виде списка смежности

@font-face {

font-family: "Virgil";

src: url("https://excalidraw.com/Virgil.woff2");

}

@font-face {

font-family: "Cascadia";

src: url("https://excalidraw.com/Cascadia.woff2");

}

1023СПИСОК СМЕЖНОСТИСООТВЕТСТВУЮЩИЙ ГРАФ( 0; 1; 2 )( 1; 2; 3 )( 2; 1 )( 3; 2 )

Пример:

@font-face {

font-family: "Virgil";

src: url("https://excalidraw.com/Virgil.woff2");

}

@font-face {

font-family: "Cascadia";

src: url("https://excalidraw.com/Cascadia.woff2");

}

102( 0; 1; 2 )

Характеристика графов

N - число точек в графе M - число рёбер в графе

@font-face {

font-family: "Virgil";

src: url("https://excalidraw.com/Virgil.woff2");

}

@font-face {

font-family: "Cascadia";

src: url("https://excalidraw.com/Cascadia.woff2");

}

1023N = 4M = 6

Определение

Топологическая сортировка - алгоритм, который упорядочивает вершины ориентированного графа в порядке неубывания.

Принцип работы алгоритма

Алгоритм находит вершину, в которую не входит ни одно ребро
Помещает найденную вершину в отсортированную последовательность
Отмечает исходящие из неё рёбра как пройденные

Эту последовательность действий алгоритм повторяет до тех пор, пока в графе остаются вершины.

Алгоритм работает только для ацикличного связного графа.

Схематическая работа алгоритма

У нас есть неотсортированный граф следующего вида:

@font-face {

font-family: "Virgil";

src: url("https://excalidraw.com/Virgil.woff2");

}

@font-face {

font-family: "Cascadia";

src: url("https://excalidraw.com/Cascadia.woff2");

}

251436

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

В данном случае это вершина "2":

@font-face {

font-family: "Virgil";

src: url("https://excalidraw.com/Virgil.woff2");

}

@font-face {

font-family: "Cascadia";

src: url("https://excalidraw.com/Cascadia.woff2");

}

251436

После этого нужно пометить эту вершину графа и смежные с этой вершиной рёбра.

@font-face {

font-family: "Virgil";

src: url("https://excalidraw.com/Virgil.woff2");

}

@font-face {

font-family: "Cascadia";

src: url("https://excalidraw.com/Cascadia.woff2");

}

251436

Далее сохраняем отмеченную вершину

@font-face {

font-family: "Virgil";

src: url("https://excalidraw.com/Virgil.woff2");

}

@font-face {

font-family: "Cascadia";

src: url("https://excalidraw.com/Cascadia.woff2");

}

514362

Повторяем этот цикл действий, пока количество неотмеченных вершин не равно нулю.

@font-face {

font-family: "Virgil";

src: url("https://excalidraw.com/Virgil.woff2");

}

@font-face {

font-family: "Cascadia";

src: url("https://excalidraw.com/Cascadia.woff2");

}

514362

@font-face {

font-family: "Virgil";

src: url("https://excalidraw.com/Virgil.woff2");

}

@font-face {

font-family: "Cascadia";

src: url("https://excalidraw.com/Cascadia.woff2");

}

543621

@font-face {

font-family: "Virgil";

src: url("https://excalidraw.com/Virgil.woff2");

}

@font-face {

font-family: "Cascadia";

src: url("https://excalidraw.com/Cascadia.woff2");

}

543621

@font-face {

font-family: "Virgil";

src: url("https://excalidraw.com/Virgil.woff2");

}

@font-face {

font-family: "Cascadia";

src: url("https://excalidraw.com/Cascadia.woff2");

}

436215

На этом этапе нужно выбрать любую из двух вершин ("4" или "3"), потому что для графа может существовать одна или несколько верных последовательностей его отсортированных вершин.

@font-face {

font-family: "Virgil";

src: url("https://excalidraw.com/Virgil.woff2");

}

@font-face {

font-family: "Cascadia";

src: url("https://excalidraw.com/Cascadia.woff2");

}

436215

@font-face {

font-family: "Virgil";

src: url("https://excalidraw.com/Virgil.woff2");

}

@font-face {

font-family: "Cascadia";

src: url("https://excalidraw.com/Cascadia.woff2");

}

362154

@font-face {

font-family: "Virgil";

src: url("https://excalidraw.com/Virgil.woff2");

}

@font-face {

font-family: "Cascadia";

src: url("https://excalidraw.com/Cascadia.woff2");

}

362154

@font-face {

font-family: "Virgil";

src: url("https://excalidraw.com/Virgil.woff2");

}

@font-face {

font-family: "Cascadia";

src: url("https://excalidraw.com/Cascadia.woff2");

}

3215463

У вершины "3" нет неотмеченных смежных, поэтому алгоритм добавляет её в отсортированную последовательность.

@font-face {

font-family: "Virgil";

src: url("https://excalidraw.com/Virgil.woff2");

}

@font-face {

font-family: "Cascadia";

src: url("https://excalidraw.com/Cascadia.woff2");

}

2 1 5 4 6 3

Вычислительная сложность

Вычислительная сложность $O(N + M$ ) достигается перебором всех вершин и рёбер графа.

Где $N$ - кол-во вершин, а $M$ - кол-во рёбер.

Псевдокод

Функция топологическая_сортировка(граф)
    вывод = пустая последовательность

    Пока количество неотмеченных вершин в графе > 0
        Для вершин из неотмеченных вершин графа
            Если количество неотмеченных родителей для вершины = 0, то
                пометить вершину как отсортированную
                Добавить в вывод вершину

    Вернуть результат

Реализация на Python

Аннотация:
topological_sort - функция топологической сортировки
graph - граф
queue - пустая последовательность графа
get_unmarked_nodes_amount() - функция, считающая кол-во неотмеченных вершин
unmarked_node - неотмеченная вершина
get_unmarked_nodes() - функция, возвращающая неотмеченные вершины
get_unmarked_parents_amount() - Функция, считающая кол-во неотмеченных родителей у вершины
mark_node_as_sorted - функция, которая помечатет вершину как отсортированную

def topological_sort(graph):
    queue = []

    while graph.get_unmarked_nodes_amount() > 0:
        for unmarked_node in graph.get_unmarked_nodes():
            if graph.get_unmarked_parents_amount(unmarked_node) == 0:
                graph.mark_node_as_sorted(unmarked_node)
                queue.append(unmarked_node)

    return queue

Олимпиадная реализация на C++

Аннотация:
typedef - переопределение имени типа данных
ii - пара из двух целых чисел
vii - вектор пар из целых чисел
vi - вектор целых чисел
UNVISITED - константа, которая обозначает, что вершина не посещена
VISITED - константа, которая обозначает, что вершина посещена
AL - список смежности графа, представленный вектором векторов пар (вектор пар: вершина, вес)
dfs_num - вектор, хранящий состояние каждой вершины (посещена или нет)
ts - вектор для хранения вершин в топологическом порядке
toposort - функция топологической сортировки
u - текущая вершина
V - количество вершин в графе
k - количество соседей текущей вершины
v - соседняя вершина
w - вес ребра между текущей и соседней вершинами

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

enum { UNVISITED = -1, VISITED = -2 };

vector<vii> AL;
vi dfs_num;
vi ts;

void toposort(int u) {
  dfs_num[u] = VISITED;
  for (auto &[v, w] : AL[u])
    if (dfs_num[v] == UNVISITED)
      toposort(v);
  ts.push_back(u);
}

int main() {

  freopen("toposort_in.txt", "r", stdin);

  int V; scanf("%d", &V);
  AL.assign(V, vii());
  for (int u = 0; u < V; ++u) {
    int k; scanf("%d", &k);
    while (k--) {
      int v, w; scanf("%d %d", &v, &w);
      AL[u].emplace_back(v, w);
    }
  }

  dfs_num.assign(V, UNVISITED);
  ts.clear();
  for (int u = 0; u < V; ++u)
    if (dfs_num[u] == UNVISITED)
      toposort(u);
  reverse(ts.begin(), ts.end());
  for (auto &u : ts)
    printf(" %d", u);
  printf("\n");

  return 0;
}

Продуктовая реализация на C++

Аннотация:
Graph - класс, представляющий граф
adjacencyList - приватное поле, которое хранит список смежности для графа, где ключ - вершина, а значение - список соседних вершин
inDegree - приватное поле, хранящее количество входящих рёбер для каждой вершины
addEdge - метод добавления ребра в граф
from - вершина, из которой исходит ребро
to - вершина, в которую направлено ребро
topologicalSort - метод топологической сортировки графа
result - вектор, который хранит вершины в топологическом порядке
q - очередь для хранения вершин с нулевой степенью входа
entry - переменная для итерации по элементам списка смежности
current - текущая вершина, которая извлечёна из очереди
neighbor - соседняя вершина для текущей вершины

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>

template <typename T>
class Graph {
private:
    std::unordered_map<T, std::vector<T>> adjacencyList;
    std::unordered_map<T, int> inDegree;

public:
    void addEdge(const T& from, const T& to) {
        adjacencyList[from].push_back(to);
        inDegree[to]++;
    }

    std::vector<T> topologicalSort() {
        std::vector<T> result;
        std::queue<T> q;

        for (const auto& entry : adjacencyList) {
            if (inDegree[entry.first] == 0) {
                q.push(entry.first);
            }
        }

        while (!q.empty()) {
            T current = q.front();
            q.pop();

            result.push_back(current);

            for (const T& neighbor : adjacencyList[current]) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }

        return result;
    }
}

OpenEd

24. Топологическая сортировка

Определение графа

Типы графов:

Ориентированные

Неориентированные

Методы хранения графов

Хранить граф в виде матрицы смежности

Пример:

Хранить граф в виде списка рёбер

Пример:

Хранить граф в виде списка смежности

Пример:

Характеристика графов

Определение

Принцип работы алгоритма

Схематическая работа алгоритма

Вычислительная сложность

Псевдокод

Реализация на Python

Олимпиадная реализация на C++

Продуктовая реализация на C++