Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Delmellor
1 / 1 / 0
Регистрация: 18.11.2012
Сообщений: 37
#1

Граф на контейнерных классах - C++

28.11.2013, 17:50. Просмотров 329. Ответов 3
Метки нет (Все метки)

Здравствуйте.

Задача такова:
описать коллекцию "граф" с объектами опр. типа

С методами:
add(u) - добавляет висячую вершину u.
addEdge(u, v) - добавляет ребро, соединяющее u и v. Если таких вершин в графе нет, добавляет их.
deleteEdge(u, v) - удаляет ребро, оставляя вершины. Если такого ребра нет, ничего не происходит.
isEmpty() - проверка на пустоту.
getAdjacent(v) - возвращает список всех вершин, смежных с v.

посредством объектного кода и с работой с конструкторами/деструкторами (управление динам. памятью).

Накидайте, пожалуйста, как писать в общем (приветствуется и большее, буду очень благодарен). Проблема в том, что не совсем понимаю, как хранить и вершины, и ребра, и что использовать для этого.

Добавлено через 10 часов 18 минут
[up]
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.11.2013, 17:50     Граф на контейнерных классах
Посмотрите здесь:

Работа с одномерным массивом с использованием контейнерных классов и алгоритмов библиотеки - C++
вот задача В одномерном массиве из n элементов вычислить: 1) сумму элементов с нечетными индексами 1) сумму элементов между...

Наследование в классах - C++
Уважаемые пожскажите по теме Есть класс Автомобиль (например ВАЗ 2114) и класс ТО_Автомобиля (например ТО1 и ТО2) как должно...

функции в классах - C++
есть класс my_class, у него есть две функцииmy_class::X_definition(int k, long double t ) {... return x; }; ...

Fstream в классах - C++
Проблема заключается в том, что я не могу использовать fsream в классе, ибо выдаёт ошибку. Код и текст ошибки ниже. Помогите пожалуйста (мб...

Ошибка в классах - C++
Подскажите что нужно сделать, что бы конструктор видел класс Cex(Цех) Перепишите текст программы и сообщений об ошибках непосредственно в...

Перечисления в классах - C++
Не могу понять почему в классах работают перечисления? Я не могу в классе обьявить константу, но я могу ее за менить перечислением вроде...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
28.11.2013, 18:00     Граф на контейнерных классах #2
храните список смежности каждой вершины. если можно юзать STL, то все совсем просто.
Delmellor
1 / 1 / 0
Регистрация: 18.11.2012
Сообщений: 37
29.11.2013, 11:58  [ТС]     Граф на контейнерных классах #3
Цитата Сообщение от salam Посмотреть сообщение
если можно юзать STL, то все совсем просто.
Да, можно.

Опишите, пожалуйста, кто-нибудь общую структуру программы; мне нужно именно это..

Добавлено через 3 часа 11 минут
[up]

Добавлено через 1 час 17 минут
[up]
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.11.2013, 13:26     Граф на контейнерных классах
Еще ссылки по теме:

константы в классах - C++
в классе используется константа типа double. Как правильно задать ее? как static const double внутри класса или просто написать...

Исключения в классах - C++
Здравствуйте. Какими средствами правильней всего сделать обработку исключений в классах? /* например, эта функция */ int...

Функции в классах С++ - C++
Здравствуйте. Уже который час бьюсь над решением проблемы, связанной с классами в C++. Надо написать программу, которая бы складывала...

Protected в классах - C++
#include <iostream> using namespace std; class TPoint{ protected: int x,y; TPoint *t; ...

Ошибка в классах - C++
Пишет ошибку error C2259: Matrix: невозможно создать экземпляр абстрактного класса Что это значит? выкладываю код в котором...

Подробнее о классах - C++
Извините если я не туда зашел. Я например хочу освоить на хорошем уровне классы. Ну в дальнейшем для написания начальных уровней игр, ну то...


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

Или воспользуйтесь поиском по форуму:
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
29.11.2013, 13:26     Граф на контейнерных классах #4
список смежности многие делают так:
C++
1
2
3
4
vector<vector<int>> g(n); // сам граф. существует n векторов - каждый представляет собой 
                          // одну из вершин графа
                          // для каждой вершины в ее вектор будем складывать номера смежных
                          // вершин, т.е. номера вершин, в которые есть ребра из данной
тогда процедура добавления ребра в граф будет выглядеть так:

C++
1
2
3
4
5
int u, v;
cin >> u >> v;        // чтение концов ребра
g[u].push_back(v);    // запоминаем, что из u есть ребро в v
g[v].push_back(u);    // конечно, если граф неориентированный, то и в обратную сторону
                      // существует ребро
в вашей задаче вершины имеют произвольную нумерацию + надо по возможности быстро добавлять и удалять, поэтому будем хранить map<номер вершины, список смежности>

1. Хранение графа.
C++
1
map< int, set<int> > g;
2. Добавление вершины. Просто говорим структуре, что в ней будет элемент с таким ключом.
C++
1
2
cin >> index;
g[index];
3. Добавление ребра. Заносим в список смежности соответствующую вершину.
C++
1
2
cin >> u >> v;
g[u].insert(v);
Даже если u не существовало, структура создаст.

4. Удаление ребра. Удаляем
C++
1
2
cin >> u >> v;
g[u].erase(v);
5. Проверка на пустоту. Тут немного сложнее, потому что пустые записи не исчезают из нашего графа при такой реализации операций. Поэтому проверим явно.
C++
1
2
3
4
for(map<int, set<int>>::iterator it = g.begin(); it != g.end(); ++it)
   if(!it->second.empty())
      return false;
return true;
6. Вывести список всех вершин, смежных с v. Просто выводите содержимое g[v].

Мог ошибиться в обозначениях, проверьте. Разбирайтесь.
Yandex
Объявления
29.11.2013, 13:26     Граф на контейнерных классах
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru