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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 28, средняя оценка - 4.61
MadMag
(Yellow_Duck)
1261 / 130 / 8
Регистрация: 16.10.2008
Сообщений: 735
#1

Представление графа в виде списка вершин. - C++

23.07.2011, 12:31. Просмотров 3815. Ответов 2
Метки нет (Все метки)

Стыдно спрашивать, просто хочется сделать чтобы все работало правильно и быстро.
Дело в том, что раньше я всегда хранил граф в виде списка ребер, если знаете(head, next, to). А теперь хочу сделать, чтобы было все четко со списком вершин(если это так называется), но не уверен в себе.

В общем, есть такое представление:
C++
1
vetor<vector<int>> graph;
Собственно, я хочу узнать, как инициализировать его, так, чтобы было какое-то определенное количество векторов, скажем n, то есть, когда я узнаю, что в графе n вершин, как сделать чтобы сразу память для n векторов освободилась.

Дальше, мне интересно, куда все-таки делать push_back?

Вот, к примеру, у меня есть такое описание графа: сначала идет количество вершин(n), дальше n строк, каждая из которых заканчивается нулем, а все числа до нуля - вершины, в которые есть ребро и вершины, номер которой совпадает с номером данной строки.
Типа такого:
Код
5
0
4 5 1 0
1 0
5 3 0
3 0
Спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.07.2011, 12:31
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Представление графа в виде списка вершин. (C++):

Реализовать представление графа в виде списка ребер в С++ - C++
Реализуйте представление графа в виде списка ребер (массива одно связанных списков) С режимами работы:1)Добавление элементов.2)Просмотр...

Реализуйте представление дерево в виде списка ребер в С++ - C++
Реализуйте представление дерево в виде списка ребер (массива одно связанных списков) С режимами работы: 1)Добавление элементов. ...

Графическое представление графа - C++
Помогите плз: Граф задаётся своей матрицей смежностей. Вывести на экран: • графическое представление графа. для меня она о4...

Максимальное множество вершин графа - C++
Алгоритм Брона-Кербоша на СИ. Нахождение максимального независимого множества вершин графа, через таблицу смежности. Не могу додуматься...

Обход всех вершин графа - C++
Нужно найти путь с наименьшим весом с вершины 0 в 0, 1 в 1 и т.д. Обязательно обойти каждую вершину не более 1 раза. Граф взвешенный. ...

Поиск вершин графа по их значению - C++
Сделать задачу поиска вершин графа по их значению. При этом граф должен сохраняться в виде матрицы смежности. Не могу понять саму структуру...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
ValeryLaptev
Эксперт С++
1040 / 819 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
23.07.2011, 13:20 #2
Но, несомненно, самым распространенным представлением графа является список смежных вершин. Вершины также должны быть пронумерованы. Список смежных вершин представляет собой контейнер, каждый элемент которого является списком list номеров вершин. Можно в качестве контейнера использовать любой последовательный контейнер, но давайте опять используем вектор:
C++
1
vector<list<unsigned int> > Graph;
Такое представление более компактно, чем матрица смежности, особенно для больших разреженных графов расстояний. Кроме того, это представление более экономично и при поиске [38]: поиск на матрице смежностей требует времени, пропорционального V2, а поиск на списках смежных вершин выполняется за время, пропорциональное V+E.
MadMag
(Yellow_Duck)
1261 / 130 / 8
Регистрация: 16.10.2008
Сообщений: 735
23.07.2011, 14:02  [ТС] #3
А хотя тамщемта легче сделать массив векторов. Всем спасибо. Тема себя исчерпала.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.07.2011, 14:02
Привет! Вот еще темы с ответами:

Обход вершин графа в глубину стеком - C++
Применить стек для обхода вершин графа, заданного с помощью матрицы смежности, в глубину. Есть код.. Но он не совсем правильно...

Неориентированный граф, вывести порядки вершин графа - C++
Доброго времени суток. Прошу помощи. С алгоритмами работал мало, решил взяться за сложную(для меня) задачу. Можете дать подсказку...

Быстрый поиск наиболее близких вершин графа - C++
Всем привет, у меня имеется некая задача и её суть состоит в том, что мне нужно найти расстояние между двумя наиболее близкими вершинами...

Вывести количество вершин неориентированного графа, смежных с данной - C++
Есть задание по с++ совершенно не понимаю как делать. Кому не сложно, напишите прогу: Создать граф, используя список смежности....


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

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