Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Отобрать в массив числа с числом десятков 0 http://www.cyberforum.ru/cpp-beginners/thread1021527.html
Заполнить массив случайными числами и отобрать в другой массив все числа, у которых вторая с конца цифра (число десятков) – ноль. Пример: Исходный массив: 40 105 203 1 14 Результат:...
C++ Из C# в C++ Привет, Кто нибудь может переделать код из C# в C++? Нам задали задание. На форуме оно уже было написано на C# - мне надо C++. Кто нибудь может помочь, а то я в C# не разбираюсь. Если не тяжело... http://www.cyberforum.ru/cpp-beginners/thread1021508.html
C++ Обработка данных в виде массива структур средствами языка С++
Количество строк: 4. Столбцы: Марка машины, Мощность двигателя, Объем бака, Цвет кузова . Вычислить машину с самым мощным двигателем. #include<cstdlib> #include<iostream> #include<string.h>...
C++ покжите пример Turbo c++
покжите пример Turbo c++ Структура "Команда": - Название; - Столица; - город - чемпион мир год
C++ Найти с какой стороны цикл будет находить 0 скорее и на какой позиции он стоит http://www.cyberforum.ru/cpp-beginners/thread1021466.html
Дан целочисленный массив а, который состоит из десяти чисел(от 0 до 9) и заполняется рандомно. Нужно найти с какой стороны цикл будет находить 0 скорее и на какой позиции он стоит(например 8 4 0 5 5...
C++ Ошибки в фрагменте кода вот кусок кода: int ques (char *s1, char *s2) { while (*s1 && *s2 && *s1++ == *s2++); return *--s1 - *--s2; } напишите пару предложений, допустимый ли он в коде :boredom: подробнее

Показать сообщение отдельно
salam
170 / 151 / 16
Регистрация: 10.07.2012
Сообщений: 748
29.11.2013, 13:26
список смежности многие делают так:
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].

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