Примите это или нет, но все, кто готовится к собеседованию по программированию, боятся графовых алгоритмов. Пока я тоже готовлюсь к интервью и оттачиваю свои навыки, я подумал поделиться одним из приложений графа; Топологическая сортировка. Это довольно просто, но большая часть объяснений в книгах или в Интернете довольно сложна, поэтому в этом блоге я объясню, как я понимаю топологическую сортировку. Я постараюсь сделать это как можно проще.
Я надеюсь, что все знают мастер обхода графа, да, вы правы, DFS или поиск в глубину, и вы попали бы в эту статью, потому что вы смотрите на одно из его приложений, но если вы не знаете, пожалуйста, проверьте эту связь, прежде чем двигаться вперед.
Для разминки все знают про DAG, как вы правильно догадались, направленные ациклические графы. Направленные графы — это графы, по которым вы можете перемещаться по направлениям стрелок, а ацикличность означает, что граф не образует цикл, хотя приведенный ниже пример образует его. Так что простите меня за этот пример. Просто помните золотое правило DAG: если мы начнем с узла, никакие последовательности ребер не позволят нам зациклиться, даже самозацикливание. DFS — один из лучших алгоритмов для поиска циклов, но это в другой раз. Я напишу пост, чтобы найти циклы как в ориентированных, так и в неориентированных графах.
DAG — это одна из наиболее важных концепций компьютерных наук и основа планирования обработки приложений для системы задач, которые необходимо обрабатывать в порядке, например, графиков зависимостей или планирования предварительных курсов, что означает, что вам нужно пройти конечно х до у.
Топологическая сортировка — обычная операция в DAG, она помогает упорядочить вершины в строке так, чтобы все направленные ребра шли слева направо. В каждом DAG есть такой порядок, а в графе с циклами его нет, потому что вы не можете продолжать идти правильно и все равно вернуться туда, откуда вы начали. Топологическая сортировка помогает найти узкие места в сети. Важность топологической сортировки заключается в том, что она дает нам порядок обработки каждой вершины перед любой из ее последователей. Если в графе существуют две вершины, x и y, и между ними существует направленное ребро (x, y), то топологическая сортировка упорядочит вершины в том порядке, в котором они встречаются на пути: x, за которым следует y.
На приведенном выше графике показано гораздо лучшее решение DAG и топологической сортировки. Следует иметь в виду одну вещь: для циклических графов не существует топологической сортировки, поскольку неясно, где должна начинаться сама сортировка, поскольку каждый узел зависит от другого.
Большой вопрос: как найти такой ЗАКАЗ?
Решение. Мы позвоним одному из наших лучших друзей, DFS. Ориентированный граф является DAG до тех пор, пока не встретится ни одно обратное ребро. Что такое задний край? Я сказал вам пройти по приведенной выше ссылке и узнать о DFS, пожалуйста, перейдите сейчас.
Итак, если вы все еще здесь, вы знаете, что такое обратная кромка, а если вы все еще не знаете, обратная кромка похожа на защитную кромку, которая соединяет, которая соединяет узел в графе с одним из его предков в его древовидном пути. , его родительский или прародительский узел, например, или даже обратно к себе!.
Алгоритм
Итак, если мы выполним DFS на графе, а затем пометим вершины в обратном порядке, то, что они помечены обработанными, находит топологический вид DAG. Почему это так, рассмотрим, что происходит с направленным ребром {x,y}.
- Если мы встречаем ребро y, а оно еще не обнаружено, то мы просто запускаем DFS для y, прежде чем мы сможем продолжить с x (надеюсь, вы прошли через эту DFS). Таким образом, y помечается завершенным (означает, что я обработал всех его соседей) до того, как x и x появляются перед y в топологическом порядке; так как это обязательно.
- Если y посещается, но не полностью обрабатывается, то {x,y} является обратным краем, поэтому нет топологического порядка.
- Если y завершено, то оно должно быть помечено до x. Следовательно, x стоит перед y в топологическом порядке.
Важные факты о топологической сортировке:
- Только DAG могут быть отсортированы топологически.
- Каждый DAG может быть отсортирован топологически.
- DAG можно топологически отсортировать разными способами. Когда есть n неограниченных заданий, то есть n! перестановки топологического порядка.
Шаги:для приведенного ниже примера
- Мы будем поддерживать два массива visited[0..n] и completed[0..n]. Посещенный[i] показывает, что мы столкнулись с этим узлом, а завершенный показывает, что мы обработали всех его соседей.
- Мы начнем с любого узла, пусть это будет 1.
- Отметить посещенным[1] = true. Затем выберите одного из его соседей 2, отметьте посещенный[2] = true.
- Посетите 3->4, так как это конец, помещенный в завершенный [4] = true, и вставьте его в один из выходных списков, затем вернитесь к 3, затем посетите другого его соседа 5, который является тупиком, добавьте к выходу list, снова вернуться к 3, все соседи 3 обрабатываются, поэтому добавьте 3 в выходной список и вернитесь к 2.
- Вернитесь назад, пометив узел как завершенный, как в DFS. Мы будем продолжать делать это, пока не доберемся до узла с непосещенным ребром. Каждый раз, когда мы это делаем, мы упорядочиваем вершину по мере необходимости.
- Наконец, вы окажетесь в начальном узле, и все готово.
- Просто переверните список и удивитесь, удивитесь, у вас есть топо-сорт DAG.
- Всякий раз, когда вы посещаете узел, просто проверяйте, был ли он посещен или завершен, если он посещен, то он должен быть завершен, если нет, то есть цикл, выйти из цикла и вывести «Цикл не найден».
- В том-то и дело, что вы хорошо разбираетесь во всех этих сложных вопросах по литкоду и проходите собеседования по программированию.
Пожалуйста, попробуйте реализовать самостоятельно, но вот пример кода, который вы можете изучить:
T = []
visited = []
topological_sort( cur_vert, N, adj[][] ){
visited[cur_vert] = true
for i = 0 to N
if adj[cur_vert][i] is true and visited[i] is false
topological_sort(i)
T.insert_in_beginning(cur_vert)
}Пример:
Вы скажете мне, что это плохой блог, просто теория и даже не один пример кодирования. Мохит! ты смеешься?
Хорошо, вот один из вопросов литкода, Расписание курса.
Всего вам нужно пройти n курсов, помеченных от 0 до n-1.
Некоторые курсы могут иметь предварительные условия, например, чтобы пройти курс 0, вы должны сначала пройти курс 1, который выражается парой: [0,1]
Учитывая общее количество курсов и список обязательных пар, сможете ли вы пройти все курсы? Это типичный вопрос топографической сортировки, здесь мы можем видеть курс [0,1] как две вершины 0 и 1, а для курса 0 вы должны выбрать курс 1, мы можем визуализировать это как направленное ребро от 0->1.
Пожалуйста, сделайте это сначала самостоятельно, не обманывайте себя
Надеюсь, вы хотя бы попытались. Я горжусь вами, ребята. Так держать.
Хорошо, вот мое решение, не самое оптимальное, но оно на 99% быстрее, чем другое решение, так что оно работает для меня.
public boolean canFinish(int numCourses, int[][] prerequisites) {
LinkedList<Integer>[] edges = new LinkedList[numCourses];
for(int i = 0;i<numCourses;i++){
edges[i] = new LinkedList<>();
}
for(int i = 0;i< prerequisites.length;i++){
edges[prerequisites[i][1]].add(prerequisites[i][0]);
}
boolean[] visited = new boolean[numCourses];
boolean[] completed = new boolean[numCourses];
//HashSet<Integer> completed = new HashSet<Integer>();
int i = 0;
boolean answer = true;
while(i<numCourses){
if(!visited[i]){
answer = dfs(edges,i,visited,completed);
}
if(!answer) return answer;
i++;
}
return answer;
}
public boolean dfs(LinkedList<Integer>[] edges, int vertex ,boolean[] visited, boolean[] completed){
//System.out.println(vertex);
if(visited[vertex] == true && completed[vertex] == false) return false;
if(visited[vertex] == true && completed[vertex] == true) return true;
visited[vertex] = true;
if(edges[vertex].isEmpty()){
completed[vertex] = true;
return true;
}
boolean result = true;
for(int edge : edges[vertex]){
result = dfs(edges,edge,visited,completed);
if(!result) return result;
}
completed[vertex] = true;
return result;
}
Я создал два массива, посещенный и завершенный, и я поддерживаю и обновляю массив по мере прохождения графика, как я только что объяснил выше. В этом вопросе мне нужно только найти, возможен ли такой тип заказа, чтобы не печатать заказ. Таким образом, вы можете работать сами, как вы будете печатать заказ, это просто небольшое изменение, или вы можете решить расписание курса2, которое специально запрашивает заказ. Тут и там всего несколько строк кода, вы поняли.
Теперь просто добавьте эту страницу в закладки, чтобы в следующий раз, когда вы почувствуете страх перед топологической сортировкой, вы могли быстро просмотреть ее.
Пожалуйста, оставьте свои искренние комментарии о том, как вам это нравится, это была моя первая статья, поэтому я знаю, что она немного запутана (много грамматических ошибок), но я буду продолжать ее улучшать, так как это цель жизни. А пока усердно практикуйтесь, продолжайте учиться, станьте лучшим программистом, и вскоре я придумаю новый алгоритм. А теперь иди и потренируйся с ответами на простые вопросы по литкоду (шучу, они довольно сложные, но мы справимся вместе).
Краткий обзор: в следующем посте я расскажу о алгоритме Кана для топологической сортировки. Да,есть еще один, и этот мой любимый. Так что следите за ним.
Некоторые ресурсы:
