Время работы DFS при проверке тесно связанных компонентов
Рассмотрим группу из k человек. Я хочу проверить, дружит ли каждый человек в группе со всеми остальными людьми в группе.
Чтобы проверить, все ли люди дружат друг с другом, я бы запустил DFS для каждого человека, проверяя, дружат ли они с k-1 людьми. Если да, то можно сделать вывод, что все они дружат друг с другом.
DFS имеет время работы O(V+E). Остается ли время выполнения O(V+E), если я выполняю DFS для каждого человека?
Вы говорите: «запустите DFS для каждого человека, проверяя, дружат ли они с k-1 людьми», но это не то, что вы могли бы сделать с DFS.
Ответы 1
A DFS has the running time O(V+E). Is the running time still O(V+E), if I do a DFS for each person?
Нет, так как вы выполняете поиск V раз, у вас будет O(V * (V+E))
Вероятно, хотя это и не нужно вам, вы можете сделать это в O(V), используя свойства полного графа, т. е.) граф является полным, если каждый узел имеет степень V-1. Обратите внимание, что график также должен быть простым, но он должен быть в вашем случае.
Что вы подразумеваете под использованием свойств полного графа? И не могли бы вы уточнить, как я буду проверять, имеет ли узел степень k-1? Извините, я очень новичок в алгоритмах
@Selanim, это больше о теории графов, чем об алгоритмах. Посмотрите "свойства полных графов". В этом случае, если все дружат со всеми, ваш граф будет полным, что упрощает задачу.
Хорошо, я посмотрю. Большое спасибо за Вашу помощь
Я недавно начал курс алгоритмов, так что я не особо разбираюсь во времени выполнения, но мне кажется, что это должно быть что-то вроде O(k*(k+E)), потому что я выполняю поиск в глубину k раз