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

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

Войти
Регистрация
Восстановить пароль
 
Qazan
211 / 59 / 9
Регистрация: 30.04.2013
Сообщений: 797
Записей в блоге: 10
#1

Правильно ли указано хранение графа в массиве списков? - C++

23.05.2014, 18:06. Просмотров 248. Ответов 5
Метки нет (Все метки)

Вобщем храни граф массиве -списков

1 2 3
2 3 4 1
3 2 1 2 4 5

В данном примере правильно ли я указал его хранение ?
т .е. к примеру должно быть и 1 3 и 3 1 ??

тогда как мне определить количество его ребер ?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.05.2014, 18:06
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Правильно ли указано хранение графа в массиве списков? (C++):

«Хранение и обработка данных с использованием линейных списков». - C++
Вот мне к курсовой работе дали задание.Я не могу его понять, что от меня требуется. Что за система n на прямой? Чем координата от точки...

Хранение и обработка данных с использованием линейных списков - C++
Люди, помогите пожалуйста!!! Дали задание к курсовой работе. Сделать надо любое из двух (какое легче) но сделать не могу ни 1, ни 2 ...

Хранение в массиве данных разного типа - C++
Доброго времени суток. Возникла задача: Имеем массив byte buffer, а также переменные char ch1,ch2; int x1,x2,y1,y2; Нужно записать в...

Хранение большого (15000) количества строк в строковом массиве - C++
Здравствуйте! Мне нужно создать генератор слов. Я решил пойти путем словаря + генератор псевдослучайных чисел. Файл сделал вложением,...

Краткое и индексное хранение списков! - Visual C++
ПОМОГИТЕ ПОЖАЛУСТА! На входе задано последовательность целых положительных чисел меньших 1000.Организуваты последовательно-звязвне...

Хранение маршрутов (путей графа) в БД - Алгоритмы
Что-то без поллитры не соображу как хранить маршруты в базе данных. Маршрут -динамическая структура, имеет переменное число промежуточных...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
newbie666
Заблокирован
23.05.2014, 18:08 #2
шта?
Qazan
211 / 59 / 9
Регистрация: 30.04.2013
Сообщений: 797
Записей в блоге: 10
24.05.2014, 19:12  [ТС] #3
Цитата Сообщение от newbie666 Посмотреть сообщение
шта?
Числа - это вершины ;
Первый столбец соответсвует массиву
указателей

т .е .

1 2 3 4 означет ребра (1,2) (1,3) (1,4)
2 3 4 1 означает ребра (2,3) (2,4) (2,1)

Вот у меня вопрос можно ли обоись, так ,чтобы не хранить

во второй строке 1
ребра (1,2) ~ (2,1) (Граф неориентированный)

Если хранить только единственный экземпляр ,то трудно определить связность , по крайней мере
я пока не понял как это сделать

Но во втором случае как туго стоит задача нахождения количества ребер
icpu
323 / 228 / 43
Регистрация: 10.03.2011
Сообщений: 1,091
Записей в блоге: 2
24.05.2014, 19:23 #4
Qazan, да, можно. В памяти программы нужно хранить рёбра в виде (меньшая, большая). И приводить к такому виду по поводу и без.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct pair
{
int a; 
int b;
};
 
void normpair(pair & p)
{
if (p.a > p.b)
{
int c = p.b; 
p.b = p.a; 
p.a=c;
}
}
Qazan
211 / 59 / 9
Регистрация: 30.04.2013
Сообщений: 797
Записей в блоге: 10
24.05.2014, 20:25  [ТС] #5
icpu, у меня в заданий матрица задается просто списком пар

Я заполнял ,как понимак ,так как вы рекомендуете
т.е.

C++
1
2
3
  std::cin >> a,b;
  std::map<int,set<int>> s;
  s[min(a,b)].insert(max(a,b));
Но с таким хранением , алгоритм DFSПоиск в глубину работает некорректно
icpu
323 / 228 / 43
Регистрация: 10.03.2011
Сообщений: 1,091
Записей в блоге: 2
24.05.2014, 22:18 #6
Qazan, он работает корректно, но усложняется поиск смежных вершин. Для одних мы просматриваем индексы map, для других ищем во всех индексах по set'ам. Можно рёбра хранить просто в виде структуры в одном set'е, а для поиска определить функцию, по которой отбирать из сета вершины.
C++
1
2
3
4
5
6
7
8
9
class mpair {
int a; int b; 
bool coll(int i) {return i==a||i==b;}
};
std::set <mpair> para;
 
for (auto i = para.begin(); i != para.end(); i++)
    if (i->coll(something))
        actions();
Не стоит заморачиваться, если не стоит задача снизить потребление памяти на 15%.

С другой стороны, если интересует чисто упрощение записи файла, можно при считывании запоминать симметричные позиции,
а для отсечения уже существующих и подсчёта общего их числа можно поставить предусловие
C++
1
2
3
4
5
6
7
if ( s.find(a) != s.end() )
{
n++;
s[min(a,b)].insert(max(a,b));
if (a != b)
s[max(a,b)].insert(min(a,b));
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.05.2014, 22:18
Привет! Вот еще темы с ответами:

Хранение и использование разных списков категорий и меню - PHP
Например на сайте есть несколько разделов с отдельным списоком категорий или банально несколько меню на странице сверху, снизу сбоку итд. ...

Как организовать хранение увеличивающихся данных - список списков? - C++ Qt
Хочу написать программу, решающую пятнашки. В сети нашёл исходники аж 2 шт, оба работают неудовлетворительно, а именно - виснут при...

Построение списков связности (графа) по данным из файлов - JavaScript
Добрый день. Необходимо построить список связности вершин графа по данным из текстовых файлов. Условия задачи следующие: пусть в некой...

Найти все циклы графа в виде списка списков вершин с точностью до начальной вершины - Lisp
Доброго времени суток. Есть неориентированный граф ((ab) (ad) (ah) (ag) (bc) (ch) (de) (ef) (fh) (gh)). Найти все циклы графа в виде...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
24.05.2014, 22:18
Ответ Создать тему
Опции темы

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