-1

Вопросы и своё понимание алгоритмы я оставлю в комментариях к строкам. Код взят с авторитетного алгоритмического сайта. `

vector < vector<int> > g; // граф, почему вектор, а не массив ?
int n; // число вершин
int s; // стартовая вершина (вершины везде нумеруются с нуля)

// чтение графа
queue<int> q; // очередь для помещения туда узлов
q.push (s); // вставляю стартовую вершину в очередь
vector<bool> used (n); // булевый вектор для узлов, по которым прошёл ?
vector<int> d (n), p (n); // для чего еще два вектора ?
used[s] = true; // помещаю в вектор элемент с пометкой посещенная
p[s] = -1; // ??? для чего это ???
while (!q.empty()) { // выполнять цикл пока очередь не пуста
    int v = q.front(); // присвоить первый элем. очереди
    q.pop(); // удалить первый элемент из очереди
    for (size_t i=0; i<g[v].size(); ++i) { // цикл выполняется пока итератор меньше чем граф
        int to = g[v][i]; // что мы здесь извлекаем из графа ? там же нет значения
        if (!used[to]) { // если to еще непосещенная, то ...
            used[to] = true; // ... отметить посещенной ...
            q.push (to); // ... вставить её в стек
            d[to] = d[v] + 1; // ???
            p[to] = v; // ???
        }
    }
}`
1
  • В дополнение к ответу @MBo. почему вектор, а не массив, а вектор это не массив? что мы здесь извлекаем из графа ? там же нет значения вы видимо немного неправильно поняли как хранится граф. g[v] это список смежных вершин. Например, если g[3] равно {0, 4, 10}, значит третья вершина смежна с вершинам 0, 4 и 10. 14 июн 2019 в 12:11

1 ответ 1

3

Это обход в ширину (BFS). Понятие "по строкам" к графам не подходит.

Вектор используется, потому что удобно ;) (Списки смежности имеют разную длину)

p[] - предшественники (predecessor) - в p[i] записано, из какой вершины пришли в i-ю при данном обходе

d[] - расстояние (distance) от стартовой вершины

for (size_t i=0; i<g[v].size(); ++i) { // цикл выполняется пока итератор меньше чем граф
здесь обходятся вершины, смежные с данной

int to = g[v][i]; // что мы здесь извлекаем из графа ? там же нет значения
индекс i-й вершины из списка смежности v-й вершины

2
  • для чего p[s] = -1; ?
    – Aleksey
    14 июн 2019 в 14:17
  • Это означает, что у начальной вершины нет предшественника
    – MBo
    14 июн 2019 в 16:19

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.