0 / 0 / 1
Регистрация: 31.08.2021
Сообщений: 30
|
||||||
1 | ||||||
Создание графов методом "Список смежности"05.12.2021, 14:33. Показов 2312. Ответов 2
Метки c++, граф, графы, динамические массивы, динамические списки, динамические структуры, списки, список, студент (Все метки)
Всем доброго времени суток. Я студент и сейчас изучаю тему "Графы" по дисциплине "Структуры и алгоритмы на C". Из всех представленных в курсе способов создания графов я решил реализовать список смежности, как самый эффективный. И у меня это без проблем получилось. Вот только я учусь на дистанте вообще в другом городе и, следовательно, не могу оперативно задать следующий вопрос своему преподавателю: правильно ли вообще я понял тему и верна ли концептуально моя реализация этого способа? Поэтому прошу Вас, уважаемые читатели, ответить на вопрос выше.
Почему я не уверен в своей реализации? Просто программное представление графа, как массив однонаправленных списков, мне кажется громоздким. Вот прога:
0
|
05.12.2021, 14:33 | |
Ответы с готовыми решениями:
2
Задание графов матрицами смежности,инцидентности Матрица Смежности в Список Смежности Составить матрицы инцидентности, смежности и список ребер для графов Матрица смежности графов Визуализатор графов по матрице смежности |
4 / 3 / 1
Регистрация: 04.12.2021
Сообщений: 28
|
|
05.12.2021, 15:04 | 2 |
Сообщение было отмечено One290 как решение
Решение
One290,
1) утечка памяти, ресурсы нужно чистить с помощью оператора delete 2) доступ у списка к элементам за O(n) - это может быть критично для алгоритмов (BFS, DFS и др.), которые работают со списком смежности, лучше использовать двумерные массив доступ к элементам за О(1), но добавление будет О(n), можно сделать матрицу изначально большую
1
|
0 / 0 / 1
Регистрация: 31.08.2021
Сообщений: 30
|
|
06.12.2021, 07:10 [ТС] | 3 |
Насчет чистки памяти: конечно же я об этом знаю. Просто программа выше реализует пока только создание и вывод графа, и, очевидно, нуждается в огромном насыщении различными функциями (поиска вершины, удаления вершины, добавления вершины, удаления графа и т. д.).
0
|
06.12.2021, 07:10 | |
06.12.2021, 07:10 | |
Помогаю со студенческими работами здесь
3
Дан список смежности. Выполнить обход графа в глубину по списку смежности Из матрицы инцидентности в матрицу смежности или в список смежности Представление графов через списки смежности Сформировать матрицу смежности и список смежности графа Вывести матрицу смежности и список смежности графа Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |