Алгоритм проходження графу вшир

При проходженні вшир замість стека рекурсивних викликів зберігається черга, в яку записуються вершини в порядку віддалення від початкової.

Визначимо списки суміжності для кожної вершини графа 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) = {(w₁, x_n), (w₂, x_n),...,(w_k, x_n)}. Наступними елементами перестановки будуть ті елементи M(w₁), які відсутні у формованій перестановці t. Потім, беремо всі елементи з M(w₂), і т.ін. Проходження припиняється, коли всі вершини, досяжні з х_n, будуть утримуватися в

t (w_i Ο Х, 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. Елемент знайдений, тобто a_i = х.

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); // елемент не знайдений

}

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: