Расчет временной сложности алгоритма DFS

Question

Мне было поручено задание, в котором я должен проверить, есть ли у группы людей «близкая дружба». Это определяется как группа людей, где все люди в группе являются друзьями со всеми другими людьми в группе. Пока у меня есть этот алгоритм:

1) Инициализировать вершины как не посещенные

2) Выполнить обход DFS графа, начиная с любой произвольной вершины v, отмечая посещенные вершины как посещенные

3) Если обход DFS посещает все вершины, верните true

4) Если это не так, вернуть false.

Теперь мне нужно вычислить сложность времени. Тем не менее, мне трудно из-за сложности времени в целом, и я не совсем уверен, как это сделать. Я вижу это так, что я прохожу все вершины в моем наборе, что было бы ... O (v)? Это правильно? И если это так, что мне делать отсюда?

Answer 1

Поскольку в DFS вы посещаете все вершины только один раз, но вы путешествуете по каждому ребру, чтобы увидеть, переносит ли это ребро вас в новую вершину или уже виденную вершину, очень точным показателем сложности DFS является O (#ребра).

Но O (#vertices) обычно является приемлемым ответом и на сложность вопроса DFS, потому что, когда вы видите, что ребро не переносит вас в новую вершину, вы не исследуете егодалее.

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

---

Но это не может быть ответом наактуальный вопрос, который вы пытаетесь решить.Вы пытаетесь найти тесно связанную группу.

В терминологии графа тесно связанная группа друзей - это группа, в которой каждый узел друзей разделяет ребро с каждым другим узлом друга.(Перечитайте ваш вопрос - на самом деле это буквально говорит об этом.)

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