⚙️ Алгоритмы · 20 вопросов · ~40 мин · ⏱ Таймер 40:00 · Средний ·

Графы: обход в ширину и глубину

Графовый обход начинается ещё до очереди или рекурсии — с правильного представления рёбер. Затем важно вовремя помечать вершины, различать слои BFS и активный стек DFS и не забывать о частях графа, недостижимых из первого старта. Вопросы включают сетки, циклы, компоненты и двудольность.

Отвечено: 0 из 20

⏱ --:--

💡 Инструкция: Выбери один ответ из четырёх. В тесте 20 вопросов и 40 минут. После завершения откроются общий процент, четыре тематические шкалы, правильные ответы и пояснения.

Вопрос 1 из 20

Какой список смежности будет построен для вершины 2?

edges = [(0, 1), (0, 2), (1, 2), (2, 3)]
g = [[] for _ in range(4)]
for u, v in edges:
    g[u].append(v)
    g[v].append(u)
print(g[2])

[0,1,3] [0,3] [1,3] [0,1,2,3]

Вопрос 2 из 20

Сколько единиц в матрице смежности простого неориентированного графа с 5 рёбрами?

\sum_{v}\deg(v)=2E

# диагональ нулевая, каждое ребро (u,v) записывается как
# matrix[u][v] = matrix[v][u] = 1

25 15 5 10

Вопрос 3 из 20

Для графа с миллионом вершин и двумя миллионами рёбер что обычно экономнее?

O(V+E)\quad\text{и}\quad O(V^2)

Полный список всех пар вершин Список смежности Матрица смежности Матрица расстояний

Вопрос 4 из 20

Какова исходящая степень вершины 1?

edges = [(1, 0), (2, 1), (1, 3), (3, 1), (1, 2)]
out_degree = [0] * 4
for u, v in edges:
    out_degree[u] += 1
print(out_degree[1])

4 5 3 2

Вопрос 5 из 20

Когда матрица смежности может быть удобнее списка?

Когда требуется минимальный расход памяти даже ценой просмотра всех соседей вершины Когда граф является деревом и для каждой вершины достаточно хранить одного родителя Когда граф плотный и часто нужно за O(1) проверять наличие конкретного ребра Когда вершин очень много, рёбер около V, а память важнее постоянной проверки ребра

Вопрос 6 из 20

В каком порядке будут извлечены вершины?

from collections import deque
g = [[1,2], [3,4], [4], [5], [5], []]
q = deque([0])
seen = {0}
order = []
while q:
    v = q.popleft()
    order.append(v)
    for u in g[v]:
        if u not in seen:
            seen.add(u)
            q.append(u)
print(order)

[0,1,2,3,4,5] [0,2,4,5,1,3] [0,1,2,4,3,5] [0,1,3,5,4,2]

Вопрос 7 из 20

Какое расстояние до вершины 5?

from collections import deque
g = [[1,2], [3], [3,4], [5], [5], []]
dist = [-1] * 6
dist[0] = 0
q = deque([0])
while q:
    v = q.popleft()
    for u in g[v]:
        if dist[u] == -1:
            dist[u] = dist[v] + 1
            q.append(u)
print(dist[5])

5 3 4 2

Вопрос 8 из 20

Почему BFS даёт кратчайшее число рёбер в невзвешенном графе?

Очередь всегда извлекает вершину с минимальным номером, поэтому путь получается короче Вершины с меньшей степенью автоматически оказываются в очереди раньше остальных Первое обнаружение может произойти на любом уровне, а массив parent затем сокращает найденный путь Очередь обрабатывает вершины по неубыванию расстояния от источника

Вопрос 9 из 20

Какой дефект возможен, если seen.add(u) делать только при извлечении u?

for u in g[v]:
    if u not in seen:
        q.append(u)
# seen.add(v) выполняется после popleft

Обход станет глубинным, потому что повторная постановка вершины меняет дисциплину очереди Одна вершина может быть добавлена несколькими соседями до первого извлечения Расстояния могут стать отрицательными из-за нескольких копий одной вершины в очереди Очередь потеряет свойство FIFO, когда одна вершина встретится у двух обработанных соседей

Вопрос 10 из 20

Сколько клеток достижимо?

from collections import deque
grid = [
  "..#",
  ".#.",
  "..."
]
q = deque([(0,0)])
seen = {(0,0)}
while q:
    r,c = q.popleft()
    for dr,dc in [(1,0),(-1,0),(0,1),(0,-1)]:
        nr,nc = r+dr,c+dc
        if 0 <= nr < 3 and 0 <= nc < 3 and grid[nr][nc]=='.' and (nr,nc) not in seen:
            seen.add((nr,nc)); q.append((nr,nc))
print(len(seen))

7 8 5 6

Вопрос 11 из 20

Какой порядок даст рекурсивный DFS?

g = [[1,2], [3,4], [4], [], []]
seen = set()
order = []
def dfs(v):
    seen.add(v)
    order.append(v)
    for u in g[v]:
        if u not in seen:
            dfs(u)
dfs(0)
print(order)

[0,1,3,4,2] [3,1,4,2,0] [0,2,4,1,3] [0,1,2,3,4]

Вопрос 12 из 20

Как положить соседей, чтобы итеративный DFS повторил рекурсивный порядок слева направо?

stack = [start]
while stack:
    v = stack.pop()
    ...

Добавлять только первого соседа Добавлять соседей в прямом порядке Добавлять соседей в обратном порядке Использовать popleft вместо pop

Вопрос 13 из 20

Что означает ребро в серую вершину при DFS ориентированного графа с цветами белый—серый—чёрный?

Ребро ведёт в ещё не посещённую вершину, которую теперь нужно окрасить серым Найден направленный цикл через вершину текущего стека вызовов Найдено ребро между двумя уже завершёнными поддеревьями Найдена новая компонента, которую нужно обходить отдельным запуском DFS

Вопрос 14 из 20

Какие времена входа и выхода возможны для предка u и потомка v?

# tin записывается при входе, tout — после обработки детей

tout[u] < tin[v] tin[v] < tin[u] < tout[v] < tout[u] tin[u] = tin[v] tin[u] < tin[v] < tout[v] < tout[u]

Вопрос 15 из 20

Что напечатает проверка цикла?

g = [[1], [2], [3], [1]]
color = [0] * 4
def dfs(v):
    color[v] = 1
    for u in g[v]:
        if color[u] == 1:
            return True
        if color[u] == 0 and dfs(u):
            return True
    color[v] = 2
    return False
print(dfs(0))

False 1 Возникнет ошибка True

Вопрос 16 из 20

Сколько компонент связности?

g = [[1], [0], [3], [2], []]
seen = set()
count = 0
def dfs(v):
    seen.add(v)
    for u in g[v]:
        if u not in seen:
            dfs(u)
for v in range(len(g)):
    if v not in seen:
        count += 1
        dfs(v)
print(count)

2 3 4 5

Вопрос 17 из 20

Сколько островов найдёт заливка?

grid = [
  "1100",
  "0101",
  "0011"
]
# соседство только по сторонам

4 1 3 2

Вопрос 18 из 20

Как проверить двудольность графа обходом?

Красить соседние вершины в противоположные цвета и искать ребро между одинаковыми цветами Разделить вершины по чётности степени и проверить, что каждое ребро соединяет разные группы Жадно выбирать цвет, отличный хотя бы от одного соседа, не проверяя остальных уже окрашенных соседей Раскрасить только компоненту первой вершины и считать отсутствие конфликта достаточным для всего графа

Вопрос 19 из 20

Что вернёт проверка для треугольника?

g = [[1,2], [0,2], [0,1]]
color = [-1] * 3
# BFS красит старт 0, соседей 1 и 2 — цветом 1
# затем видит ребро 1-2

Граф не двудольный Есть две компоненты Граф двудольный Есть изолированная вершина

Вопрос 20 из 20

Почему изолированная вершина считается отдельной компонентой связности?

v\leadsto v\text{ путём длины }0

Она не является частью графа Её нужно удалить перед обходом Она достижима сама из себя путём длины 0 и не связана с другими Компоненты должны содержать минимум два узла

Ответьте на все 20 вопросов, чтобы получить результат

🔗 Встроить тест на свой сайт (iframe) ▼

Скопируйте код и вставьте в любое место на вашем сайте:

Также доступна прямая ссылка на embed-страницу