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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 50, средняя оценка - 4.74
Polikarpic
46 / 46 / 7
Регистрация: 29.06.2011
Сообщений: 174
#1

Список смежности для графа - C++

29.08.2012, 18:45. Просмотров 8309. Ответов 2
Метки нет (Все метки)

Доброго времени суток. Не могли бы вы мне подсказать, как построить список смежности для вершин графа. В интернете много примеров, но мало объяснений. Можете объяснить как строить или скинуть ссылки на полезные материалы? Граф неориентированный.

З.Ы: а, и ещё - как в таких списках считать степень вершины и перебирать смежные?

Заранее спасибо
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.08.2012, 18:45     Список смежности для графа
Посмотрите здесь:

Как передать в функцию список смежности графа? - C++
Как передать в функцию список смежности графа который представлений как вектор векторов - vector<vector<int>> adj

Матрица/связные_списки смежности для ориентированного графа - C++
Скажите, пожалуйста, когда я создаю матрицу смежности для ориентированного графа, то в матрице у меня должны присутствовать только 0 и 1?...

Определить планарность графа по матрице смежности - C++
в общем есть файлы с матрицами смежностей, формат файла прикладыва. (graph1.txt , graph2.txt) В первой строчке указывается количество...

Сгенерировать матрицу смежности полного графа - C++
1. Сгенерировать матрицу смежности полного графа (количество вершин n = 3) и найти минимальный гамильтонова цикла методом полного перебора....

Определение матрицы смежности графа по заданной матрице инцидентности - C++
Доброй ночи :) Изучаю графы, написал фукнцию для конвертации матрицы инцидентности в матрицу смежности, а наоборот не выходит. ...

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

По заданной квадратной матрице из нулей и единиц определите, может ли данная матрица быть матрицей смежности простого неориентированного графа - C++
помогите решить вот такую задачу пожалуйста(( По заданной квадратной матрице n*n из нулей и единиц определите, может ли данная матрица...

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

С матрицы смежности в матрицу инцидентности, список рёбер и вершин, диаграмма - C++
Помогите, пожалуйста. На C# или C++ нужна такая программа, что когда задается матрица смежности (5 на 5 можно) и выводились: 1) матрица...

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

Преобразование списка смежности в матрицу смежности - C++
Помогите пожалуйста, нужно разработать алгоритм преобразования списка смежности в матрицу смежности, для неорентированного графа. И все...

Для ориентированного графа определить полустепень захода и исхода для каждой из вершин - C++
Для ориентированного графа определить полустепень захода и исхода для каждой из вершин. Вывести списки вершин с нулевой полустепенью захода...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dani
1300 / 637 / 56
Регистрация: 11.08.2011
Сообщений: 2,280
Записей в блоге: 2
Завершенные тесты: 1
29.08.2012, 18:50     Список смежности для графа #2
Тут все просто. Списки смежности можно представить как массив списков.
C++
1
std::vector <std::list> v;
Здесь список v[i] хранит смежные вершины с v (к которым есть ребро). Строить его просто, если матрица смежности (например и 0 и 1, где 0 - отсутствие ребра, 1 - наличие) и в a[i,j] стоит 1, то добавляете j в список v[i].
Степень вершины - кол-во смежных вершин, считать просто. Степень вершины i - длина списка v[i].
Перебирать смежные для вершины i - просто проходите по всем элементам списка v[i]
Polikarpic
46 / 46 / 7
Регистрация: 29.06.2011
Сообщений: 174
29.08.2012, 18:54  [ТС]     Список смежности для графа #3
О! Спасибо большое - помогли
Ответ Создать тему
Опции темы

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