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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 28, средняя оценка - 4.61
MadMag
(Yellow_Duck)
 Аватар для MadMag
1260 / 129 / 8
Регистрация: 16.10.2008
Сообщений: 735
23.07.2011, 12:31     Представление графа в виде списка вершин. #1
Стыдно спрашивать, просто хочется сделать чтобы все работало правильно и быстро.
Дело в том, что раньше я всегда хранил граф в виде списка ребер, если знаете(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++ Максимальное множество вершин графа
C++ Определить степени вершин графа и если граф однородный - вывести степень однородности
C++ Обход вершин графа в глубину стеком
Нахождения кратчайших путей между всеми парами вершин графа C++
C++ Вычислить количество различных путей между всеми парами вершин графа
C++ Поиск вершин графа по их значению
Неориентированный граф, вывести порядки вершин графа C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ValeryLaptev
Эксперт C++
1005 / 784 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
23.07.2011, 13:20     Представление графа в виде списка вершин. #2
Но, несомненно, самым распространенным представлением графа является список смежных вершин. Вершины также должны быть пронумерованы. Список смежных вершин представляет собой контейнер, каждый элемент которого является списком list номеров вершин. Можно в качестве контейнера использовать любой последовательный контейнер, но давайте опять используем вектор:
C++
1
vector<list<unsigned int> > Graph;
Такое представление более компактно, чем матрица смежности, особенно для больших разреженных графов расстояний. Кроме того, это представление более экономично и при поиске [38]: поиск на матрице смежностей требует времени, пропорционального V2, а поиск на списках смежных вершин выполняется за время, пропорциональное V+E.
MadMag
(Yellow_Duck)
 Аватар для MadMag
1260 / 129 / 8
Регистрация: 16.10.2008
Сообщений: 735
23.07.2011, 14:02  [ТС]     Представление графа в виде списка вершин. #3
А хотя тамщемта легче сделать массив векторов. Всем спасибо. Тема себя исчерпала.
Yandex
Объявления
23.07.2011, 14:02     Представление графа в виде списка вершин.
Ответ Создать тему
Опции темы

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