Простите за обязательно банальное и штампованное название ...
Но как еще я мог привлечь ваше внимание?
Здесь может быть много людей, не занимающихся компьютерными науками, которые читают это сейчас. Не хочу вас разочаровывать, но эта не будет интересной темой. Хорошо - можешь уехать через 3, 2, 1… Ушли? Хорошо.
Итак, для остальных из вас, классные ребята, которые остались, я здесь, чтобы поговорить о том, что вы можете легко найти в Википедии, если захотите. Или на дюжине других сообщений Medium (я не удосужился проверить). Если вы предпочитаете посмотреть, как какой-нибудь другой плодовитый инженер-программист занимается этой часто обсуждаемой темой среди новичков C.S 2XX, то, во что бы то ни стало, не стесняйтесь уходить через 3, 2, 1…
Все еще здесь? Большой!
вступление
Я считаю, что алгоритм Кана - это простой для понимания метод выполнения топологической сортировки. Итак, если вы не знаете, что это такое, вам действительно следует идти. Шу. Шу.
Шучу, пожалуйста, останься ...
Также алгоритм Кана был изобретен компьютерным ученым по имени Артур Кан (не я). Оригинал статьи здесь: https://dl.acm.org/citation.cfm?doid=368996.369025.
Уф ... теперь это не мешает ...
Обзор: DAG
Чтобы согреться, давайте немного освежимся. Помните, что такое DAG? Подсказка: это не просто выражение удивления или разочарования 90-х годов.
DAG - это аббревиатура от направленного ациклического графа, и в дальнейшем я буду называть их так для целей этой статьи.
В информатике они представляют собой просто наборы узлов и ребер, которые используются для представления отношений между ними. Пропустив всю бессвязную речь Discrete Math о классах эквивалентности и тому подобном, просто думайте об узлах как о пунктах назначения, а о ребрах как о путях между пунктами назначения.
Есть два типа графиков, о которых вам нужно знать здесь и сейчас:
А также…
Ненаправленный граф инкапсулирует базовую концепцию межузловых отношений, а ориентированный граф - это шаг вперед. В ориентированном графе стрелки просто означают, например, что A будет относиться к C, но не наоборот, а B будет относиться к A, но не наоборот, и так далее.
Возвращаясь к аналогии с путем, представьте, что стрелки означают, что на графике вы можете двигаться только в направлении стрелок. Думаю, это настолько просто, насколько я могу это сделать, не спев песню «Wheels on the Bus».
Топологическая сортировка
Топо-что-сейчас?
Небольшое напоминание: топологическая сортировка в смысле «псевдострогой теории графов» - это просто способ взять несколько задач и линейно упорядочить их в завершаемой последовательности.
Вы меня потеряли при линейном заказе?
Хорошо, я покажу вам (плохо нарисованную картинку):
Сказанное выше означает только то, что я беру DAG и помещаю все узлы в строку. Затем найдите путь через все ребра, чтобы каждый узел мог быть достигнут из предыдущего узла по порядку.
По сути, вы сортируете узлы в строке.
Небольшой изящный фактоид - ЛЮБОЙ DAG имеет связанную топологическую сортировку.
Попробуйте устроить вечеринку - наблюдайте, как люди стекаются к вам! (Отказ от ответственности: не совсем).
Зачем вам нужна топологическая сортировка для конкретного графа? Что ж, есть множество причин, но одна из них, которую может понять каждый, заключается в том, что всегда полезно знать последовательность шагов для завершения конкретного процесса.
Канонический пример: если вы студент и записываетесь на занятия в начале года, вам, вероятно, был представлен список классов, которые вы можете посещать, и предварительные требования к ним. Вы, вероятно, захотите знать порядок, в котором вы можете посещать занятия, чтобы вы могли составить план того, как вы закончите свои семестры. Получите степень. Получить работу. Если тебе нравятся подобные вещи.
Расписание занятий можно представить в виде группы доступности базы данных, поскольку некоторые классы связаны друг с другом, а некоторые - нет. Но все они необходимы для достижения конечной цели в определенном порядке. Окончательное упорядочение можно преобразовать в топологическую сортировку.
Другой пример - рецепт приготовления вашего любимого блюда (тофурки для аргументации). Определенные шаги (например, предварительный разогрев духовки) должны быть выполнены перед тем, как запечь «гуся». Так же, как мыть посуду, нарезать тофурки и т.д. Но не все задачи зависят друг от друга. Таким образом, топосортировка дает вам четкий порядок действий, которые вы можете сделать для достижения конечной конечной цели.
Алгоритм Кана
Кто угодно, если вы знакомы с печально известной техникой поиска в ширину (BFS), то Khan's - всего лишь ее применение. Мы все еще смотрим на соседние узлы, мы все еще отправляем их и опрашиваем из очереди. Ничего странного или чуждого, кроме…. ХАН - муахаха…
Кхм. Вот быстрая ссылка на BFS, если вы забыли. И если да, как вам не стыдно! Просто шучу. Без осуждения - но, вероятно, вам следует напомнить себе, прежде чем двигаться вперед.
Еще одна быстрая вещь. Вы знаете, какова внутренняя степень вершины? Еще один термин «закатите глаза на затылок»? Может быть, но это также просто количество ребер, поступающих на конкретный узел в вашей группе DAG.
Пример: B → C → A имеет входящую степень для B = 0, C = 1 и A = 1. 0 стрелок в B, одна стрелка в C и одна стрелка в A. Очень просто? Мне так кажется.
Это важно знать, потому что алгоритм Хана r требует, чтобы ваш граф имел хотя бы один узел с входной степенью 0 для работы. У вас может быть больше одного, но вам понадобится как минимум 1. В противном случае подумайте об этом - без этого ограничения не было бы четкой отправной точки для вашей топологической сортировки. Вы можете начать с любого узла и закончить на любом другом узле. Бесконечный цикл - СТРАШНО!
Объединив вышеупомянутые идеи - DAG, BFS и ин-степень, мы теперь можем составить стратегию. Интуиция этого алгоритма состоит в том, что мы будем итеративно удалять части графа (узлы), которые не зависят от каких-либо других узлов, чтобы найти топосортировку, последовательно уменьшая их степени. Подумайте, отсоединив узел от графа и записав порядок, в котором он был отсоединен. Примерно так, как поступил бы хирург, если бы он извлекал органы 1 к 1 и каталогизировал их!
А вот быстрые шаги к алгоритму ...
Ключевые ингредиенты (структуры данных):
- DAG
- Очередь
- Массив "в градусах"
- Немного TLC (ну, если вы ненавидите C.S., но тогда вам не должно быть здесь ...)
Этапы приготовления (псевдокод):
- Постройте свой график, используя свою любимую структуру данных графа. (Я предпочитаю Списки смежности для этой задачи)
- Создать экземпляр очереди
- Прокрутите список узлов графа и поставьте в очередь все узлы, у которых in-degree = 0, в очередь, которую вы только что создали.
- Внешний цикл: начните цикл через вашу очередь, выскакивая сверху. Верхний узел - это «текущий» узел.
- Внутренний цикл: для каждого соседа «текущего» узла уменьшите степень этого соседа 1. Почему мы это делаем? Потому что мы удаляем «текущий» узел из графа. Да !! В то же время в том же внутреннем цикле поставить в очередь любого «соседа» со степенью входа 0. Это означает, что «соседний» узел больше ни от кого не зависит - и, таким образом, является кандидатом на место в топологической сортировке.
6. Промыть, промыть, повторить. Пока у вас не будет окончательной топологической сортировки.
И вот, теперь у вас есть линейная последовательность шагов, которую вы можете выполнить, чтобы добраться от одного «исходного» узла на графике к другому месту назначения. Теперь как ты крут!
На заметку -
В графе может быть несколько топологических сортов. В зависимости от того, как вы все инициализировали, вы можете получить что-то вроде A B Y Z E F или Y Z E F A B. Причина в том, что есть много потенциальных мест, с которых вы можете начать (узлы, не зависящие от них). Нетрудно изменить приведенный выше алгоритм, чтобы начать с определенного узла и построить топологическую сортировку относительно этого узла. Единственное требование - чтобы начальный узел имел входную степень 0.
Алгоритм Кана дает возможность закончить раньше. Почему? Потому что это не только топологическая сортировка, но и удобный способ обнаружения циклов в графе. Благодаря части алгоритма BFS вы отслеживаете посещенных соседей. Если вы снова видите другого соседа (как указано стрелками), значит, вы знаете, что у вас циклическая зависимость.
Топологическая сортировка НЕ определена для циклической зависимости. Это не может быть правдой? Вы никогда не сможете выполнить шаги, если где-то на вашем графике есть цикл шагов, который вам нужно выполнить.
Еще одна полезная вещь, которую следует знать: обнаружение цикла / топосортировка - очень важная задача в теории сетей, для обнаружения избыточностей, неисправных узлов и других вещей, которыми вы, вероятно, хотите произвести впечатление на собеседника. ;)
Код:
/**
* We the inputs to the algorithm assume pre-computation of the
* indegree, but it's easy enough to do and just depends on the data
* structure you're using to represent the graph
*/
public void khan(List<List<Integer>> graph, List<Integer> indegree) {
Queue<Integer> queue = new LinkedList<>();
List<Integer> sortedList = new ArrayList<>();
// The initial state of the algorithm requires the addition of
// indegree = 0 nodes */
for(int i = 0; i < indegree.length; i++) {
if(indegree[i] == 0)
queue.add(i);
}
// Loop through the entire list until the indegrees of all nodes
// become zero
while(!queue.isEmpty()) {
int current = queue.poll();
sortedList.add(current);
List<Integer> neighbors = graph.get(current);
for(Integer i : neighbors) {
indegree.get(i)--;
if(indegree.get(i) == 0) {
queue.add(i);
}
}
}
// print the final sorted list
for(int i = 0; i < sortedList.size(); i++)
System.out.print(sortedList.get(i) + " ");
}
Для получения дополнительной информации об этом:
GOOGLE IT СЫН / ДОЧЬ!
Or —
