Почему поиск в ширину работает?

Question

[Glebster13]

Имеется список друзей, каждый из который является объектом типа User:

package Graph;
import java.util.List;
public class User {
    String userId;
    String firstName;
    String secondName;
    String surname;
    String job;
    List<String> friendListId;
}

Из данных объектов формируется хеш-таблица вида (идентификатор_юзера, соответствующий объект). Из данной хеш-таблицы формируется социальный граф друзей.

Имеется класс FriendGraph, который реализует поиск в ширину в графе. Идет поиск объектов, у которых атрибут job имеет значение "No info". Код класса:

package Graph;
import java.util.*;

public class FriendGraph {
    private Map<String, User> usersMap;
    public FriendGraph(){
        usersMap = new HashMap<>();
    }
    public void addUser(User user){
        usersMap.put(user.userId, user);
    }
    public User getUserById(String userId){
        return usersMap.get(userId);
    }
    public List<User> findUsersWithJob(String jobValue, String startUserId){
        List<User> result = new ArrayList<>();
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.add(startUserId);
        visited.add(startUserId);
        for (User user : usersMap.values()){
            if (!visited.contains(user.userId)){
                queue.add(user.userId);
                visited.add(user.userId);
                while (!queue.isEmpty()){
                    String currentUserId = queue.poll();
                    User currentUser = usersMap.get(currentUserId);
                    if(currentUser.job.contains(jobValue)){
                        result.add(currentUser);
                    }
                    for (String friendId : currentUser.friendListId){
                        if (!visited.contains(friendId)){
                            queue.add(friendId);
                            visited.add(friendId);
                        }
                    }
                }
            }
        }
        return result;
    }
}

Вопрос: почему данный код вообще работает, если стартовая вершина добавляется в множество уникальных значений visited. Ведь данное условие if (!visited.contains(user.userId)){ не должно срабатывать и программа не должна получить доступ к списку друзей вершины

Comments

[Kano]

Тут либо изначально была другая логика, которую в последствии кто то криво переработал, либо это чатгпт нагенерил, ну или не достаточно вводных данных.
Написана ерунда не имеющая смысла. Судя по сигнатуре метода надо найти всех пользователей связанных со стартовым у которых в поле job записано заданное значение.
Алгоритм игнорирует это условие и тупо сканирует всех пользователей, при чем делает это максимально не эффективно т.к. на каждом пользователе как минимум проверяет всех его друзей.

[Glebster13]

Kano,

это чатгпт нагенерил

абсолютно верно. Читаю "грокаем алгоритмы", там примеры на питоне. По возможности самостоятельно делаю те же примеры, но на джаве. В этот раз самому не получилось.

[Kano]

Glebster13, ответом на ваш вопрос, кстати, будет - потому что он обходит всех пользователей, причём даже стартового, т.к. его обход отложили в очередь

Answer 1

[Wataru]

Код вообще странно реализует поиск в ширину. Я уверен, что на каких-то тестах оно работать не будет. Зависит от порядка вершин в usersMap. Т.е. если вы их все переименуете, вы можете получить другой ответ.

Вообще тут не нужен обход в ширину, тут, кажется, достаточно цикла по всем вершинам.

А так ваш алгоритм зачем-то имеет внешний цикл по User user и если он натыкается на какую-то еще не посещенную вершину, то дальше уже перебирает все вершины в очереди и добавляет их соседей в очередь в цикле, фактически выполняя обход в ширину. Правда там в очереди будет лежать какая-то случайная вершина из цикла по user. Так что это будет обход вширину сразу из двух вершин.

На какой-то следующей итерации цикла он опять запустит обход в ширину от какой-то еще не посещенной вершины, если в графе несколько компонент связности. В итоге первый обход в ширину может затронуть одну или 2 компоненты связности, а все следующие обходы обойдут по одной компоненте.

Answer 2

[Дмитрий Кинаш]

Ведь данное условие if (!visited.contains(user.userId)){ не должно срабатывать

Почему? У тебя со старта в visited есть только startUserId - для остальных айдишников тут будет TRUE.

Comments

[Glebster13]

Почему? У тебя со старта в visited есть только startUserId

. Вот именно. Я, если честно, пока до конца не понимаю каким образом цикл работает. Включил отладку - почему-то для идентификатора стартовой вершины условие выполняется:


Буду очень благодарен, если объясните как алгоритм работает.

[Дмитрий Кинаш]

Glebster13, у вас был конкретный вопрос - "почему условие работает" и в отладке можете увидеть более чем понятный ответ:
1) У вас ID для пользователя = glebster
2) Есть некая непонятно где и кем запоняемая мапа usersMap, первый элемент которой @46 очевидно имеет другое ID (какое - нужно смотреть в отладке)
3) Выражение !visited.contains(user.userId) возвращает TRUE, так как выражение visited.contains(user.userId) возвращает FALSE, так как в visited изначально есть только startUserId

В целом угадывается алгоритм обхода дерева в ширину, но тут нет явного дерева/графа (хотя граф можно построить на базе объектов класса User, где объекты будут узлами, а данные из стрингового листа friendListId можно рассматривать как однонаправленные ребра). А конкретно этот класс с неиспользуемыми методами addUser() и getUserById() не имеет смысла, содержит неочевидные названия, которые не отражают суть и вообще нарушает принципы SOLID - получение друзей и мест работ нужно было делать там, где они хранятся, а обход дерева там, где это дерево создано - т.е. в рамках класса User с помощью статического метода.