МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів Контакти
Тлумачний словник |
|
|||||||
М-блоковий пошукПлан Алгоритм проходження графу вшир
При проходженні вшир замість стека рекурсивних викликів зберігається черга, в яку записуються вершини в порядку віддалення від початкової. Визначимо списки суміжності для кожної вершини графа G (рисунок 7.3): 1:2,3, 52:1, 3, 4 3:1,2,4,5 4:2,35:1,3 t: 1, 2, 3, 4, 5 (для обраної вершини переписуємо весь список суміжності). Виберемо початкову вершину хn . Перші елементи шуканої перестановки t є елементами суміжного списку вершини хn, тобто М(хn). Позначимо список суміжності в такий спосіб: М(хn) = {(w1, xn), (w2, xn),...,(wk, xn)}. Наступними елементами перестановки будуть ті елементи M(w1), які відсутні у формованій перестановці t. Потім, беремо всі елементи з M(w2), і т.ін. Проходження припиняється, коли всі вершини, досяжні з хn, будуть утримуватися в t (wi Ο Х, i=1,2,...,k)... Знову ж таки, введемо масив used, а також створимо чергу для зберігання вершин (реалізуємо її у вигляді масиву queue; природно, можливі інші варіанти). У початок черги запишемо початкову вершину.
Star:=1; {початкова вершина - перша} queue[1] = start; used[start] = 1; r = 1 ,w = 2; {r - позиція черги, з якої читаємо дані, змінна w— позиція, куди дані будемо записувати} while (r < w) do begin curr:= queue[r]; {беремо перший елемент із черги} іnсl; for і: = 1 to N do begin if (used [i]:= true) and (a[curr][i]=1) then begin used[i] := 1; queue[w] := I; inc(w); end; end; end;
Контрольні питання
1. Способи подання графу. 2. Поясніть основні кроки алгоритму розташування позначок. 3. наведіть приклад застосування алгоритму Дейкстри. Тести для закріплення матеріалу 1. Визначити суміжні вершини до вершини В у графі, заданому матрицею суміжності: а) ACD; б) CD; в) АС; г) немає правильної відповіді.
2. Визначити суміжні вершини до вершини А у графі, заданому матрицею суміжності: а) BCD; б) CD; в) В; г) немає правильної відповіді.
3. Визначити суміжні вершини до вершини В у графі, заданому матрицею суміжності: а) ACD; б) CD; в) АС; г) немає правильної відповіді.
4. Визначити суміжні вершини до вершини С у графі, заданому матрицею суміжності: а) ACD; б) CD; в) BE; г) немає правильної відповіді.
5. Визначити суміжні вершини до вершини D у графі, заданому матрицею суміжності: а) ABD; б) CD; в) BE; г) немає правильної відповіді.
6. Визначити суміжні вершини до вершини Е у графі, заданому матрицею суміжності: а) ABD; б) CD; в) BE; г) немає правильної відповіді. ЛЕКЦІЯ № 6
Тема: Алгоритми пошуку
Ціль: розглянути алгоритми пошуку стрічок: прямий пошук, Ахо-Корасика, Кнута-Моріса-Прата, Рабіна-Карпа, Боуєра-Мура. Алгоритми пошуку у масивах та списках
1 Загальна класифікація алгоритмів пошуку 2 Лінійний пошук 3 Двійковий (бінарний) пошук елемента в масиві 4 Пошук методом Фібоначчі Читайте також:
|
||||||||
|