svetasmirnova (![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
svetasmirnova) wrote2013-03-30 01:05 am
svetasmirnova) wrote2013-03-30 01:05 am
Entry tags:
Coursera: algs4partII-001. Неделя 1. Часть 2. Directed Graphs
Тут тоже имеет смысл сделать заметки только по тестам.
1. Breath-first search.
Аналогично предыдущему заданию.
2. Topological order.
Делаем depth-first search, но запоминаем nodes в порядке убывания из очереди. Затем этот список возвращаем в обратном порядке.
Так, для A->B->C D->E, сначала получим список C B A E D и правильным ответом будет D E A B C
3. Strongly-connected components.
Почти аналогично предыдущему, но components выбирать следующим образом: взять букву, пройти depth-first search-ем все слинкованные nodes; если остались неслинкованные - взять следующую букву из списка.
Reference: algs4.cs.princeton.edu/40graphs/
1. Breath-first search.
Аналогично предыдущему заданию.
2. Topological order.
Делаем depth-first search, но запоминаем nodes в порядке убывания из очереди. Затем этот список возвращаем в обратном порядке.
Так, для A->B->C D->E, сначала получим список C B A E D и правильным ответом будет D E A B C
3. Strongly-connected components.
Почти аналогично предыдущему, но components выбирать следующим образом: взять букву, пройти depth-first search-ем все слинкованные nodes; если остались неслинкованные - взять следующую букву из списка.
Reference: algs4.cs.princeton.edu/40graphs/