ДЗ-3, ДЗ-4 (И. И. Супрунов)

ДЗ-3

Поиск в глубину

Исходный граф

a

b

d

f

c

e

h

0-й уровень

1-й уровень

2-й уровень

3-й уровень

g

4-й уровень

Преобразованный граф

Исходный граф

Поиск в ширину

v₀

v₅

v₄

v₃

v₂

v₁

v₆

v₁₁

v₁₀

v₁₄

v₁₅

v₁₈

v₉

v₈

v₇

v₁₃

v₁₂

v₁₆

v₁₇

Преобразованный граф

0-й уровень

1-й уровень

2-й уровень

3-й уровень

ДЗ-4

g=

a

b

d

c

e

2

(1)

3

(3)

3

(4)

4

(5)

4

(6)

5

(7)

Преобразованный граф

Алгоритм Краскала

f

(2)

h

2

Исходный граф

Преобразованный граф

a

d

c

e

h

f

g

b

(6)

4

2

(1)

3

(2)

4

(3)

2

(4)

3

(5)

5

(7)

Алгоритм Прима