Транспонирование графа

У многих графов есть еще одно условие, то что их можно транспонировать. Давайте сначала разберемся с тем, что же такое транспонирование.

Транспонированый ориентированный граф G - это другой ориентированный граф на том же множестве вершин со всеми ребрами, перевернутыми по сравнению с ориентацией соответствующих ребер в G. То есть, если G содержит ребро (u, v), то обратное (transpose / reverse) G содержит ребро (v, u) и наоборот.

Алгоритм транспонирования графа

Мы проходим по списку смежности, и когда мы находим вершину v в списке смежности вершины u, которая указывает на ребро от u до v в основном графе, мы просто добавляем ребро от v до u в транспонированный граф, т.е. добавляем u в смежность список вершины v нового графа. Таким образом, обходя списки всех вершин основного графа, мы можем получить транспонированный граф. Таким образом, общая временная сложность алгоритма составляет O (V + E), где V - количество вершин графа, а E - количество ребер графа.

Data Science: Алгоритмы и Структуры данных

Как определить зацикливание в ориентированном графе

Проблема: дан ориентированный граф. Необходимо проверить содержит ли граф цикл или нет

Алгоритм

1. Создайте граф, используя заданное количество ребер и вершин (условно, если граф еще не создан)

2. Создайте рекурсивную функцию, которая инициализирует текущий индекс или вершину, а также создает стек рекурсии

3. Отметьте текущий узел как посещенный, а также отметьте индекс в стеке рекурсии

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

5. Если рекурсивный вызов вернет - true - значит это и есть истина и ваш финальный ответ. Кстати, если соседние вершины уже присутствуют в стеке рекурсии - вы можете сразу вернуть true

Data Science: Алгоритмы и Структуры данных

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

Топологическая сортировка для ориентированного ациклического графа (DAG) - это линейное упорядочение вершин таким образом, что для каждого направленного ребра u-v: вершина u идет перед v в порядке. Топологическая сортировка для графа невозможна, если граф не является DAG.

Завтра мы рассмотрим саму сортировку!

Data Science: Алгоритмы и Структуры данных

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

Самый простой вариант данной сортировки - это изменение DFS обхода. В DFS мы начинаем с вершины, сначала выводим ее на печать, а зачем рекурсивно вызываем DFS для смежных вершин. В топологической сортировке - мы будем использовать стек!

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

Самое важное, что вершина помещается только тогда, когда все ее смежные вершины находятся в стеке.

Data Science: Алгоритмы и Структуры данных

Структура данных - строки

Строки определяются как массив символов. Разница между символьным массивом и строкой заключается в том, что строка заканчивается специальным символом "\0"

Объвить строку так же просто как объявить одномерный массив. Обращаю особое ваше внимание, что каждый символ строки хранится отдельно в ячейке. И как одномерный массив - строки имеют всё те же свойства.

Data Science: Алгоритмы и Структуры данных

Разница между 2мя большими числами

Даны два числа в виде строк. Числа могут быть очень большими (не помещаться в long long int), задача - найти разницу этих двух чисел.

Data Science: Алгоритмы и Структуры данных

Разница между 2мя большими числами


1. Поверните обе строки (чтобы конец стал началом) - reverse string operation. Создайте пустую строку для результата

2. Продолжайте вычитать цифры одну за одной из 0го индекса(в повернутых строка) - до конца меньшей строки, добавьте разницу, если она положительна в конец результата. Если разница отрицательна, то прибавьте 10 и отслеживайте перенос как +1, если положительный, то перенос равен 0

3. Снова переверните результативную строку


Как видите: чтобы посчтитать разницу между 2мя строками - мы используем обычную математику(якобы в столбик)

Data Science: Алгоритмы и Структуры данных

Задача на бинарные строки

Давайте сначала разберемся что такое бинарные строки! На самом деле тут ничего сложного: это строки которые могут содержать только 2 различных символа. К примеру a и b: abbbbaaa

А теперь после теории, перейдем к задаче.

Преобразуйте данную строку в строку, в которой не будет содержаться значение подстроки "ab". Чтобы убрать "ab", мы можем пользоваться операциями, в которой мы заменим эту подстроку на "bba". Основная цель данной задачи, найти общее количество операций, которые необходимы для преобразование данной строки.

Input : s = 'abbaa'
Output : 2
Объяснение:
Тут, 'ab'baa заменяется на s = bbabaa
bb'ab'aa а тут на s = bbbbaaa
Нам потребовалось 2 операции на это.

Попробуйте решить данную задачу.

Data Science: Алгоритмы и Структуры данных

Z - алгоритм

Задача данного алгоритма найти все вхождения шаблона в текст за линейное время. Пусть для текста равна n, а длина шаблона - m, тогда общее затраченное время составит O(m+n) с линейной пространственной сложностью. Для этого мы строим специальный Z-массив.

Что такое Z массив?

Для строки str0..n-1 массив Z имеет ту же длину, что и строка. Элемент Zi массива Z хранит длину самой длинной подстроки, начиная с Zi, которая таке является префиксом str0..n-1

Пример:

str = "aaaaaa"
Z = {x, 5, 4, 3, 2, 1}

Data Science: Алгоритмы и Структуры данных | Чат 💬