О numerOfSelfLoops (График G) стр.523 в Алгоритмах Седжвика и Уэйна, - PullRequest
Новая
       5

О numerOfSelfLoops (График G) стр.523 в Алгоритмах Седжвика и Уэйна,

0 голосов
/ 04 ноября 2018

Я читаю Алгоритмы Седжвика и Уэйна.

Следующий код вычисляет количество циклов в ненаправленном графе G.

Я не могу понять, почему этот код возвращает count / 2 вместо count .

Пожалуйста, объясните, почему.

p.523 

public static int numerOfSelfLoops(Graph G)
{
    int count = 0;
    for (int v = 0; v < G.V(); v++)
        for (int w : G.adj(v))
            if (v == w) count++;
    return count/2;
}

1 Ответ

0 голосов
/ 04 ноября 2018

Может ли быть так, что алгоритм находит один и тот же цикл дважды, так сказать. Грубо говоря, один раз по часовой стрелке и один раз против часовой стрелки. Комментарий к последней строке в книге: «Каждое ребро считается дважды».

...