С Новым годом! Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.62/13: Рейтинг темы: голосов - 13, средняя оценка - 4.62
0 / 0 / 1
Регистрация: 31.08.2021
Сообщений: 30
1

Создание графов методом "Список смежности"

05.12.2021, 14:33. Показов 2312. Ответов 2

Author24 — интернет-сервис помощи студентам
Всем доброго времени суток. Я студент и сейчас изучаю тему "Графы" по дисциплине "Структуры и алгоритмы на C". Из всех представленных в курсе способов создания графов я решил реализовать список смежности, как самый эффективный. И у меня это без проблем получилось. Вот только я учусь на дистанте вообще в другом городе и, следовательно, не могу оперативно задать следующий вопрос своему преподавателю: правильно ли вообще я понял тему и верна ли концептуально моя реализация этого способа? Поэтому прошу Вас, уважаемые читатели, ответить на вопрос выше.
Почему я не уверен в своей реализации? Просто программное представление графа, как массив однонаправленных списков, мне кажется громоздким.

Вот прога:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <clocale>
#pragma warning (disable : 4703)
 
struct node {
    int data;
    node* next;
};
 
void outputGraph(node** m, int n) {
    node* p;
    for (int i = 0; i != n; i++) {
        p = m[i];
        while (p) {
            if (!p->next)
                std::cout << p->data;
            else
                std::cout << p->data << " --> ";
            p = p->next;
        }
        std::cout << std::endl;
    }
}
 
void createGraph(node** m, int n) {
    node* p, * p1;
    int k, j;
    for (int i = 0; i != n; i++) {
        m[i] = new node;
        m[i]->data = i + 1;
    }
    for (int i = 0; i != n; i++) {
        j = 0;
        k = 1;
        while (k && (j != n - 1)) {
            std::cout << "В какую вершину будет вести дуга из вершины " << i + 1 << "? Введите 0, если хотите прекратить 'связывание вершины'. Создание петель запрещено: ";
            std::cin >> k;
            std::cout << std::endl;
            if ((!std::cin.good()) || (k < 0) || (k - 1 == i) || (k > n)) {
                std::cout << "Вы ввели не корректное число. Завершение программы";
                exit(0);
            }
            if (!k) break;
            p = new node;
            p->data = m[k - 1]->data;
            if (!j)
                m[i]->next = p;
            else
                p1->next = p;
            p1 = p;
            j++;
        }
        if (j)
            p->next = nullptr;
    }
}
 
int main() {
    int n;
    node** m;
    std::setlocale(LC_CTYPE, "Russian");
    std::cout << "Введите кол-во вершин графа: ";
    std::cin >> n;
    if ((!std::cin.good()) || (n <= 0)) {
        std::cout << "Вы ввели не натуральное число. Завершение программы";
        exit(0);
    }
    m = new node*[n];
    std::cout << std::endl;
    createGraph(m, n);
    outputGraph(m, n);
    return 0;
}
Всем неравнодушным заранее спасибо.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
05.12.2021, 14:33
Ответы с готовыми решениями:

Задание графов матрицами смежности,инцидентности
1. задать граф матрицей смежности; 2. задать граф матрицей инцидентности; 3. задать граф списком...

Матрица Смежности в Список Смежности
Привет . Как можно конвертировать матрицу смежности в список смежности ? Я понимаю что код можно...

Составить матрицы инцидентности, смежности и список ребер для графов
Задание: составить матрицы инцидентности, смежности и список ребер для графов

Матрица смежности графов
Вообщем написал код, подсчитывает среднюю точку графов. Осталось только вывести матрицу...

Визуализатор графов по матрице смежности
Здравствуйте, можете помочь. Нужна программа написанная на C#, а именно визуализация графов по...

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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
06.12.2021, 07:10
Помогаю со студенческими работами здесь

Дан список смежности. Выполнить обход графа в глубину по списку смежности
нужно реализовать на c#: Дан список смежности. Выполнить обход графа в глубину по списку...

Из матрицы инцидентности в матрицу смежности или в список смежности
Граф неориентированный. Как из матрицы инцидентности можно получить матрицу смежности? Или еще...

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

Сформировать матрицу смежности и список смежности графа
Разработать программу, которая: - запрашивает о количестве вершин и ребер невзвешенного...

Вывести матрицу смежности и список смежности графа
Всем привет!! Уважаемые форумчане, помогите плиз с заданием! Я написала код в Си по которому...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru