|
|
Алгоритм проходження графу вшир
При проходженні вшир замість стека рекурсивних викликів зберігається черга, в яку записуються вершини в порядку віддалення від початкової. Визначимо списки суміжності для кожної вершини графа G (рисунок 7.3): 1:2 ,3, 5 2:1, 3, 4 3:1 ,2,4,5 4:2 ,3 5: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. Елемент знайдений, тобто ai = х. 2. Весь масив проглинутий і збігу не знайдено. 3. Це дає нам лінійний алгоритм. Звертаємо увагу, що якщо елемент знайдений, то він знайдений разом із мінімально можливим індексом, тобто це перший з таких елементів. Очевидно, що закінчення циклу здійсниться, оскільки на кожному кроці значення i збільшується, і, отже, воно досягне за скінченну кількість кроків межі N; фактично ж, якщо збігу не було, це відбудеться після N кроків.
Int LinearSearch (int[] a, int N, int L, int R, int Key) { for (int I = L;i<=R; i++) if(a[i] = = Key) return (i); return (-1); // елемент не знайдений }
  ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...  ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...  Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот...  Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
