@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)){ не должно срабатывать и программа не должна получить доступ к списку друзей вершины
  • Вопрос задан
  • 212 просмотров
Решения вопроса 2
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Код вообще странно реализует поиск в ширину. Я уверен, что на каких-то тестах оно работать не будет. Зависит от порядка вершин в usersMap. Т.е. если вы их все переименуете, вы можете получить другой ответ.

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

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

На какой-то следующей итерации цикла он опять запустит обход в ширину от какой-то еще не посещенной вершины, если в графе несколько компонент связности. В итоге первый обход в ширину может затронуть одну или 2 компоненты связности, а все следующие обходы обойдут по одной компоненте.
Ответ написан
Комментировать
@Dementor
программист, архитектор, аналитик
Ведь данное условие if (!visited.contains(user.userId)){ не должно срабатывать

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

Войдите, чтобы написать ответ

Похожие вопросы