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

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

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

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

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

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

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

Заранее спасибо
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.08.2012, 18:45
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Список смежности для графа (C++):

список смежности и проход графа в ширину - C++
нужно создать список смежности и пройти граф в ширину. как с помощью struct{}; создать список смежности? список смежности: 0: 5 ...

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

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

заданно матрицу смежности простого графа. Построить каркас этого графа с использованием поиска вширь - C++
Задание: заданно матрицу смежности простого графа. Построить каркас этого графа с использованием поиска вширь. Помогите написать...

Матрица смежности графа - поиск в глубину - C++
Здравствуйте дорогие форумчане. У меня тут небольшая ошибка. Никак не могу понять что к чему. Объясните пожалуйста. #include <iostream> ...

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 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]
1
Polikarpic
46 / 46 / 7
Регистрация: 29.06.2011
Сообщений: 174
29.08.2012, 18:54  [ТС] #3
О! Спасибо большое - помогли
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.08.2012, 18:54
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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