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

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

Визначимо списки суміжності для кожної вершини графа 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 Загальна класифікація алгоритмів пошуку

2 Лінійний пошук

3 Двійковий (бінарний) пошук елемента в масиві

4 Пошук методом Фібоначчі