Если у меня есть график с не менее чем 4 узлами, какова будет минимальная временная сложность для этого?Сложность времени для: все пути между узлом A и узлом B пересекаются либо с узлом X, либо с узлом Y?
Примечание: Я не ученый-компьютер, я философ по философии, поэтому заранее извиняюсь за свое невежество.
Алгоритм: удалите узлы X и Y из графика, а затем посмотрите, все ли подключены A и B. Вы можете увидеть, все ли подключены узлы, используя поиск по ширине с A, и посмотрите, доходите ли вы до B. Временная сложность удаления X и Y постоянна O (1), а временная сложность поиска по ширине - это O (E + V), который считается «линейным» для графов. Таким образом, общая сложность будет «линейной» для общих графиков.