[golang] Breadth-First Search

graph := map[int][]int{
    0: {1, 5},  // Из вершины 0 можно перейти в вершины 1 и 5
    1: {2, 6},  // Из вершины 1 можно перейти в вершины 2 и 6
    2: {3, 7},  // Из вершины 2 можно перейти в вершины 3 и 7
    3: {4, 8},  // Из вершины 3 можно перейти в вершины 4 и 8
    4: {0, 9},  // Из вершины 4 можно перейти в вершины 0 и 9
    5: {7},     // Из вершины 5 можно перейти в вершину 7
    7: {9},     // Из вершины 7 можно перейти в вершину 9
    9: {6},     // Из вершины 9 можно перейти в вершину 6
    6: {8},     // Из вершины 6 можно перейти в вершину 8
    8: {5},     // Из вершины 8 можно перейти в вершину 5
}

// breadthFirstSearch выполняет обход графа в ширину (BFS), начиная с указанной вершины.
//
// Параметры:
//   - graph: граф, представленный в виде map[int][]int, где ключ — вершина,
//     а значение — срез смежных вершин (направленные или ненаправленные рёбра).
//   - start: начальная вершина, с которой начинается обход.
//
// Возвращаемое значение:
//   - []int: порядок обхода вершин в ширину.
//
// Особенности:
//   - Функция использует множество visited (map[int]struct{}{}) для отслеживания
//     уже посещённых вершин, что предотвращает зацикливание и повторный обход.
//   - Обход выполняется итеративно с использованием очереди (queue).
//   - Если граф содержит недостижимые из start вершины, они не будут включены в результат.
//   - Функция корректно работает как с направленными, так и с ненаправленными графами
//     (при условии корректного задания смежных вершин).
func breadthFirstSearch(graph map[int][]int, start int) []int {
 
    // visited — Heshset посещённых вершин.
    // Используем map[int]struct{}{}, а не map[int]bool, потому что:
    // - struct{}{} занимает 0 байт (экономия памяти)
    // - это идиоматичный способ реализации set в Go
    // - явно показывает, что значение не имеет смысла, важен только ключ
    visited := map[int]struct{}{}
 
    // queue — очередь для обхода в ширину (BFS).
    // Используем срез []int как очередь FIFO (First-In-First-Out):
    // - добавление в конец: queue = append(queue, node)
    // - извлечение из начала: currentNode := queue[0]; queue = queue[1:]
    queue := []int{start}
 
    // visited[start] = struct{}{} — отмечаем начальную вершину как посещённую.
    // Добавляем в множество (hash set) до помещения в очередь, чтобы избежать повторного добавления.
    // struct{}{} — пустая структура, занимающая 0 байт (экономия памяти).
    // Альтернатива с true была бы visited[start] = true, но struct{}{} — идиоматичный способ для set в Go.
    visited[start] = struct{}{}
 
    // path — результирующий срез для хранения вершин в порядке обхода BFS.
    // Nil-срез (нулевое значение), память выделится динамически при первом append.
    var path []int
 
    // Продолжаем обход, пока очередь не опустеет.
    // Условие len(queue) > 0 — идиоматичный способ проверить, есть ли элементы в очереди на основе среза.
    // Пустая очередь означает, что все достижимые вершины обработаны.
    for len(queue) > 0 {
 
        // Берём вершину из начала очереди (принцип FIFO для BFS).
        currentNode := queue[0]
 
        // Удаляем первый элемент из очереди (сдвигаем начало среза).
        // queue[1:] создаёт новый срез, указывающий на те же данные, но без первого элемента.
        // Это эквивалент операции "dequeue" в очереди FIFO.
        queue = queue[1:]
 
        // Добавляем текущую вершину в результат обхода.
        // Порядок добавления соответствует порядку посещения вершин (BFS order).
        // append автоматически расширит срез при необходимости.
        path = append(path, currentNode)
 
        // Перебираем всех соседей (смежные вершины) текущей вершины.
        // graph[currentNode] возвращает срез всех вершин, в которые можно перейти из currentNode.
        // _ — игнорируем индекс, используем только значение (саму вершину-соседа).
        for _, childNode := range graph[currentNode] {
 
            // Проверяем, не посещали ли мы уже эту вершину.
            // _, ok — comma ok идиома для проверки существования ключа в map.
            // ok == true — вершина уже в множестве (посещена).
            // !ok — вершина ещё не посещена, значит можно добавить в очередь.
            if _, ok := visited[childNode]; !ok {
 
                // Отмечаем соседнюю вершину как посещённую.
                // Делаем это ДО добавления в очередь, чтобы избежать дублирования.
                // Если отметить после добавления, вершина может попасть в очередь несколько раз.
                visited[childNode] = struct{}{}
 
                // Добавляем не посещённого соседа в конец очереди.
                // Теперь он будет обработан после всех текущих вершин (FIFO).
                // Это и есть суть BFS — сначала обрабатываем вершины на текущем уровне, потом на следующем.
                queue = append(queue, childNode)
            }
        }
    }
    return path
}

func TestBreadthFirstSearch(t *testing.T) {
    testCases := []struct {
        desc     string
        graph    map[int][]int
        start    int
        expected []int
    }{
        {
            desc: "binary tree",
            graph: map[int][]int{
                0: {1, 2},
                1: {3, 4},
                2: {5, 6},
                3: {},
                4: {},
                5: {},
                6: {},
            },
            start:    0,
            expected: []int{0, 1, 2, 3, 4, 5, 6},
        },
        {
            desc: "peterson graph",
            graph: map[int][]int{
                0: {1, 5},
                1: {2, 6},
                2: {3, 7},
                3: {4, 8},
                4: {0, 9},
                5: {7},
                7: {9},
                9: {6},
                6: {8},
                8: {5},
            },
            start:    0,
            expected: []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
        },
        {
            desc: "single node",
            graph: map[int][]int{
                0: {},
            },
            start:    0,
            expected: []int{0},
        },
        {
            desc: "linear chain",
            graph: map[int][]int{
                0: {1},
                1: {2},
                2: {3},
                3: {},
            },
            start:    0,
            expected: []int{0, 1, 2, 3},
        },
    }
    for _, tC := range testCases {
        t.Run(tC.desc, func(t *testing.T) {
            result := breadthFirstSearch(tC.graph, tC.start)
 
            got := make([]int, len(result))
            copy(got, result)
            exp := make([]int, len(tC.expected))
            copy(exp, tC.expected)
 
            slices.Sort(got)
            slices.Sort(exp)
 
            if !reflect.DeepEqual(got, exp) {
                t.Errorf("breadthFirstSearch (%v, start=%d): expected %v, got %v", tC.graph, tC.start, tC.expected, result)
            }
        })
    }
}

// ConcurrentBFSQueries обходит граф конкурентно из нескольких вершин queries
func ConcurrentBFSQueries(graph map[int][]int, queries []int, numWorkers int) map[int][]int {
 
    // К заданию был тест с нулевым количеством воркунов который должен вернуть map[int][]int{}
    // поэтому просто оставлю это тут
    if numWorkers == 0 {
        return map[int][]int{}
    }
 
    // Приметив синхронизации WaitGroup
    // используется для того чтобы дождаться выполнения всех параллельных
    // горутин и двигаться дальше
    var wg sync.WaitGroup
 
    // Приметив синхронизации Mutex, реализация дефолтного map потоко не безопасна
    // использую Mutex для безлопастной конкурентной работы с map 
    var mu sync.Mutex
    
    // Map для результатов
    result := make(map[int][]int)
 
    // Шаблон семафор реализуется в go через канал буферизированный канал в который пишется
    // пустая структура для экономии памяти, когда буфер заполнен следующая горутина
    // пытающаяся записать в канал выхватывает блокировку до момента пока кто то не вычитает из канала
    semaphore := make(chan struct{}, numWorkers)
 
    // Цикл по узлам с которых начинается поиск в ширину
    for _, query := range queries {
 
        // занимаем один слот в WaitGroup
        wg.Add(1)
 
        // занимаем слот в семафоре
        semaphore <- struct{}{}
 
        // конкурентно запускаем функцию
        go func(q int) {
 
            // это выполнится в конце функции независимо от того где из нее вышли
            // высвобождаем слот в WaitGroup
            defer wg.Done()
 
            // это выполнится в конце функции независимо от того где из нее вышли
            // высвобождаем слот в семафоре
            defer func() { <-semaphore }()
 
            // получаем результат поиска 
            bfsResult := breadthFirstSearch(graph, q)
 
            // вешаем блокировку
            mu.Lock()
 
            // безопасно добавляем результат
            result[q] = bfsResult
 
            // снимаем блокировку
            mu.Unlock()
        }(query)
    }
 
    // тут ждем пока все слоты в WaitGroup высвободятся 
    wg.Wait()
 
    // возвращаем result
    return result
}