Сложность времени / Теория графов

Question

Для домашней задачи мне был задан вопрос о заданном наборе из n узлов и m ребер, где граф был представлен списком смежности, почему insertVertex будет принимать O (1), а deleteVertex - O (m).

Я не совсем уверен в своем ответе, но я добавил, что insertVertex равен O (1), потому что при первой вставке все, что вы добавляете в массив, это один узел и набор смежных вершин (то есть вершин)на что указывает ваш новый узел).Таким образом, сложность этого времени постоянна.Однако, когда вы удаляете узел, вам нужно не только удалить узел и смежные ребра, которые идут с узлом, вы также должны пройти через остальные ребра m, чтобы убедиться, что вы удаляете те, которые указывают наузел, который вы пытаетесь удалить (поскольку вы не можете иметь ребро, которое ни на что не указывает.

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

Спасибо

Answer 1

Объяснение O (m) верно.

Ваше объяснение будет лучше, если вы объясните действия в терминах манипуляций со связанным списком. Требуется O (1) время, чтобы добавить узел в связанный список. И для удаления элемента требуется O (n) время.

а) Почему insertVertex - это O (1)?

Вставка вершины - это просто добавление узла в связанный список (O (1)) или 2, если график не направлен.

б) Почему deleteVertex - это O (m)?

Удаление вершины означает:

1) Удалить связанный список (O (1))

2) В худшем случае вам придется удалить вершину из всех связанных списков: O (m). Это O (m), потому что число узлов во всех связанных списках равно m, или 2 * m, если график ненаправленный.

Answer 2

insertVertex принимает O (1), потому что вы добавляете только новый элемент в конец вашей структуры данных.

deleteVertex принимает O (m), потому что для каждого ребра вы должны проверить, указывает ли ребро или указывает ли оно (если направлено G) от вершины.у меня есть идея, хотя, читая ваш ОП.