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

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

Восстановить пароль Регистрация
 
Qazan
211 / 59 / 9
Регистрация: 30.04.2013
Сообщений: 778
Записей в блоге: 10
23.05.2014, 18:06     Правильно ли указано хранение графа в массиве списков? #1
Вобщем храни граф массиве -списков

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++
Хранение и обработка данных с использованием линейных списков C++
Организовать ввод, хранение в массиве, вывод на экран данных о сту¬дентах: фамилия, имя, отчество, рост, вес. Вычислить средний вес студентов. Определ C++
Создание файла с именем, которое указано в переменной C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
newbie666
Заблокирован
23.05.2014, 18:08     Правильно ли указано хранение графа в массиве списков? #2
шта?
Qazan
211 / 59 / 9
Регистрация: 30.04.2013
Сообщений: 778
Записей в блоге: 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
 Аватар для icpu
276 / 181 / 36
Регистрация: 10.03.2011
Сообщений: 863
Записей в блоге: 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
Сообщений: 778
Записей в блоге: 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
 Аватар для icpu
276 / 181 / 36
Регистрация: 10.03.2011
Сообщений: 863
Записей в блоге: 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));
}
Yandex
Объявления
24.05.2014, 22:18     Правильно ли указано хранение графа в массиве списков?
Ответ Создать тему
Опции темы

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