Program Algo — Введение в графики

В этой статье я объясню концепции BFS, DFS и других важных алгоритмов в компьютерном программировании.

Это обязательные навыки для каждого студента, изучающего информатику.

Узлы и ребра

Для любого графа G = (V, E), где:

• V: набор узлов (вершин). Иногда также обозначается n.
• E: набор ребер между парами узлов. Иногда также обозначается m.

Для неориентированных графов:

• deg(v) = Количество ребер в v
• ∑v∈V град(v) = 2E

Для ориентированных графов:

• deg_in(v) = количество ребер, входящих в v
• deg_out(v) = Количество ребер, выходящих из v
• ∑v∈V deg_out(v) = ∑v∈V deg_in(v) = E

Путь, связность, цикл, расстояние и дерево

Определение: Путь — это последовательность узлов от v1 до vn, такая, что каждый (vi, v(i+1)) является ребром. Количество ребер пути называется длиной.

По определению: путь называется простым, если все узлы различны.

По определению: неориентированный граф связен, если для любых узлов u и v между ними существует путь.

По определению: цикл — это путь, где v1 и vn — одни и те же узлы. Если все узлы от v1 до v(n-1) различны, такой цикл простой.

По определению: Длина кратчайшего простого пути между двумя узлами называется расстоянием между двумя узлами.

Определение: неориентированный граф является лесом, если он не содержит цикла. Кроме того, если такой граф связен, то это дерево.

BFS — поиск в ширину

Сценарий: предположим, что есть связный неориентированный граф, и для данного узла s мы хотим обозначить расстояние между s и каждым из остальных узлов в графе.

Следовательно, мы можем обозначить расстояние «слой за слоем». Мы бы обозначили расстояние 1 для первого слоя, 2 для второго слоя и так далее. Это называется «поиск в ширину».

См. псевдокод ниже:

BFS(G,s):
# Setting up the initial value for each node
for each vertex u∈V - {s}
    # White for undiscovered
    # gray for discovered but neighbors not fully processed
    # black for discovered and neighbors fully processed
    u.color <- white 
    u.d <- ∞ # d for distance
    u.p <- nil # p for parent node
# Below function can be wrapped up as "BFS-Visit(G,s)"
s. color <- gray
s.d <- 0
initialize an empty queue Q
Enqueue(Q,s) #Q.append(s) in Python
while Q ≠ ∅ do
    u <- u = Dequeue(Q) # Q.pop() in Python
    for each v ∈ Adj(u) # Adj for all the neighboring nodes of u
        if v.color == white then
            v.color <- grey
            v.d <- u.d + 1
            v.p <- u
            Enqueue(Q,v)
    u.color <- black # This part is for noting purpose from my perspective

DFS — поиск в глубину

Вместо того, чтобы исследовать граф «послойно», DFS будет начинать с одного узла и исследовать путь до конца, а затем делать шаги назад. Но каждый шаг назад, к предыдущему узлу, он будет исследовать, есть ли другие пути, которые он может расширить.

Вам станет намного понятнее, если вы увидите псевдокод ниже:

DFS(G):
for each vertex u ∈ V do
    u.color <- white
    u.p <- nil
for each vertex u ∈ V do
    if u.color == white then
        DFS_Visit(u) # Defined below

DFS_Visit(u):
    u.color <- grey
    for each v ∈ Adj(u) do
        v.p <- u
        DFS_Visit(v)
    u.color <- black

Алгоритм топологической сортировки

Если у нас есть ориентированный ациклический граф (DAG), состоящий из k узлов. Топологическое упорядочение графа означает, что мы произвольно выбираем две вершины (u, v) в графе, и u должен стоять перед v.

Псевдокод:

Topological Sort (G):
Initialize Q to be an empty queue
Initialize O to be an empty queue #Store the topological order
for each u in V do
    If in-degree(u) == 0 then
        # Find all starting vertices
        Enqueue(Q,v)
while Q is not empty do
    u = Dequeue(Q)
    Enqueue(O,u)
    for each v in Adj(u) do
        # remove u's outgoing edges
        in-degree(v) = in-degree(v) - 1
        if in-degree(v) = 0 then
            Enqueue(Q,v)

Советы для меня и потенциальных будущих читателей:

• Попрактикуйтесь в написании кодов для DFS, BFS и топологической сортировки без посторонней помощи.

Головоломка в конце

В: [Лемма о рукопожатии] Представьте себе группу людей, которые произвольно пожали друг другу руки. Возможно ли, чтобы количество людей, которые пожали друг другу руки нечетное количество раз, также было бы нечетным?

A: Используйте противоречие. Количество рукопожатий для каждого человека равно deg(v). Если есть нечетное количество людей, пожимающих друг другу руки нечетное число, то суммирование степеней также даст нечетное число.

нечетное + нечетное + … + нечетное + четное + четное + …+ четное = нечетное, если существует нечетное количество коэффициентов