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

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

Восстановить пароль Регистрация
 
Delmellor
1 / 1 / 0
Регистрация: 18.11.2012
Сообщений: 37
28.11.2013, 17:50     Граф на контейнерных классах #1
Здравствуйте.

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

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

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

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

Добавлено через 10 часов 18 минут
[up]
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
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]
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
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     Граф на контейнерных классах
Ответ Создать тему
Опции темы

Текущее время: 12:47. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru