Рекомендуемые источники

Обход в ширину

Набросок предполагаемой реализации

ArrayList<ArrayList<Integer>> edges;
// В этом списке списков хранятся ребра для каждой вершины следующим образом:
// edges.get(u) - это список смежных вершин v до которых есть ребро из u, т.е. ребро u<->v:
// - степень вершины u (т.е. число ребер из u) т.о. равна edges.get(u).size()
// - чтобы посмотреть в какую вершину v из вершины u ведет i-ое ребро достаточно взять edges.get(u).get(i) == v
int[] distances;
// В этом массиве на u-ом индексе будет храниться расстояние до u-ой вершины
// Изначально для начальной вершины значение расстояния должно быть 0, а для всех остальных вершин здесь должна быть бесконечность (например пусть -1)
ArrayList<Integer> wave = new ArrayList<>();
// В этом списке (волне) будет храниться список вершин на которые мы сейчас распространились
// это такой расширяющийся во все направления фронт, расходящаяся волна 
wave.add(startVertex);
// В начале в этой волне ровно одна вершина - вершина начала пути, поэтому добавляем ее в текущую волну

// Пока в волне есть хоть что-то (размер больше нуля) - мы будем находить следующую волну в которую надо перетечь:
while (wave.size() > 0) {
    ArrayList<Integer> nextWave = new ArrayList<Integer>();
    // В этом списке мы будем хранить вершины следующей волны, в которые мы распространились от текущей,
    // и от которых мы будем должны распространиться дальше. Пока что новая волна пустая ведь мы ее только создали.
    for (int i = 0; i < wave.size(); ++i()) { // Перебираем все вершины текущей волны чтобы перетечь в смежные вершины:
        int u = wave.get(i); // вытащили очередную вершину u из текущей волны, чтобы затем посмотреть куда мы перетечем из нее.

        // Нам надо посмотреть, в какие смежные вершины v ведут ребра из u:
        for (int j = 0; j < edges.get(u).size(); ++j) { // edges.get(u).size() - равно числу ребер из u
            int v = edges.get(u).get(j);                // вытащили очередную вершину v из текущей волны, т.е. мы сейчас смотрим на ребро u->v
            if (distances[v] == -1) {                   // Если вешина v еще не была посещена:
                nextWave.add(v);                        //  То эта вершина является частью следующей волны - поэтому добавляем ее в новую волну.
                                                        //  А так же мы теперь знаем расстояние до вершины v,
                                                        //  ведь раз мы в нее перешли из вершины u по ребру u->v,
                                                        //  то расстояние от начальной вершины до v
                distances[v] = distances[u] + 1;        //  длиннее расстояния от начальной вершины до u на одно ребро u->v, т.е. на 1, т.к. все ребра длины 1.
            }
        }
        // После этого for-а мы перебрали все ребра исходящие из u, а значит добавили все смежные с u вершины v в следующую волну.
    }
    // После этого for-а мы перебрали все вершины старой волны, а значит новая волна построена полностью, и достаточно теперь
    // так же распространиться из этой новой волны в сверхновую, поэтому мы считаем теперь текущей волной - ту новую волну которую только что перечислили:
    wave = nextWave;
}
// while закончит свое исполнение как только новая волна ставщая текущей волной окажется пустой
// т.е. как только не будет новой вершины в которую мы можем перетечь и в которой мы еще не были
// а это значит что мы дотекли до всего до чего было возможно, и все расстояния расставлены в массиве distances

Восстановление пути

Что если мы хотим не только найти кратчайшее расстояние, но и восстановить промежуточные вершины, т.е. найти кратчайший путь?

Тогда достаточно обновлять для каждой вершины не только расстояние, но и записывать из какой вершины предыдущей волны мы в эту вершину добрались в момент когда выставили это расстояние:

int[] previouses;
// Давайте в этом массиве изначально хранить -1
// а в конце концов мы хотим чтобы previouses[u]=v означало что на кратчайшем пути от начальной вершины до u предпоследней вершиной является v:
//   startVertex -> . -> . -> . -> v -> u
// (previous переводится как "предыдущий", т.е. здесь всмысле "предыдущая вершина")
ArrayList<ArrayList<Integer>> edges;
int[] distances;
ArrayList<Integer> wave = new ArrayList<>();
wave.add(startVertex);
while (wave.size() > 0) {
    ArrayList<Integer> nextWave = new ArrayList<Integer>();
    for (int i = 0; i < wave.size(); ++i()) {
        int u = wave.get(i);
        for (int j = 0; j < edges.get(u).size(); ++j) {
            int v = edges.get(u).get(j);
            if (distances[v] == -1) {
                nextWave.add(v); 
                distances[v] = distances[u] + 1; // т.е. раз мы впервые перешли в v по ребру u->v, т.е. перешли в нее из u
                previouses[v] = u;               // то достаточно запомнить что предыдущая вершина - u (на кратчайшем пути от начальной вершины до v)
            }
        }
    }
    wave = nextWave;
}
// Заметьте что теперь чтобы восстановить кратчайший путь до вершины endVertex мы уже можем сделать очень неплохой шажок:
int previous = previouses[endVertex];
// т.е. в этой переменной теперь хранится предпоследняя вершина на кратчайшем пути от начальной вершины до конечной:
//                                        startVertex ->     .     ->     .     ->     .     -> previous -> endVertex
// можно шагнуть дальше:
int previous2 = previouses[previous];  // startVertex ->     .     ->     .     -> previous2 -> previous -> endVertex
int previous3 = previouses[previous2]; // startVertex ->     .     -> previous3 -> previous2 -> previous -> endVertex
int previous4 = previouses[previous3]; // startVertex -> previous4 -> previous3 -> previous2 -> previous -> endVertex
// осталось обобщить это циклом сохраняющим все предыдущие вершины вплоть до начальной в ArrayList,
// и по сути этот список будет являться кратчайшим путем перевернутым задом наперед,
// который осталось всего лишь перевернуть для получения ответа