Как лучше хранить структуру графа

@body90 · Регистрация: 26.05.2009

Студворк — интернет-сервис помощи студентам

Здравствуйте! Хочу написать класс для хранения графа. Есть две идеи:
1) хранить список вершин и отдельно список ребер (у каждого ребра будет информация о начальной и конечной вершине)
2) хранить список вершин и для каждой вершины хранить связанные с ней вершины.
Кто как считает, как лучше сделать?

Добавлено через 14 часов 30 минут
Неужели ни у кого нет никакого мнения?

@serg42 · 07.04.2012, 18:22

Я бы сделал связанные списки ребер. В классе ребро: точка1, точка2 (координаты), длина ребра, список смежный ребер по точке1, список смежный ребер по точке2. Помню делал лабы по теории графов на C++, там хранил данные в двумерном массиве.

@body90 · 07.04.2012, 18:55 **[ТС]**

Мне сейчас нужно хранить не графическое представление графа, а именно его структуру.

Добавлено через 3 минуты
Ребра у меня не имеют длины (в смысле структуры графа, а не графического отображения). просто думаю как лучше? Хранить отдельно список вершин и список ребер, которые их соединяют (у каждого ребра будет информация о вершинах, которые оно соединяет) или у каждой вершины хранить список соседних вершин, не храня информации о ребрах?

@serg42 · 07.04.2012, 19:03

Сообщение от body90

у каждой вершины хранить список соседних вершин, не храня информации о ребрах?

А какую информацию о ребрах хранить, когда о них получается и информации-то никакой нет. Длина не нужна, граф не направленный. Списка соседних точек будет достаточно, имхо.

@body90 · 07.04.2012, 23:50 **[ТС]**

Граф направлен. Просто потом, чувствую, захотят, чтоб я это всё визуализировал. Значит придется хранить координаты изгиба ребер.

@MiniMin · 09.04.2012, 09:16

если в графе не будут существовать несколько ребер, инцидентных одним и тем же вершинам, то можно матрицей смежности.
если граф достаточно разряженный с большим количеством вершин - то ООП с контейнерами смежных вершин для каждой вершины.
как вариант ещё матрица инцидентности.

в теории графов вершины не имеют координат в классическом понимании. так что если нужно будет их зарисовать - то координаты можно будет подобрать на ходу во время рисования.

@body90 · 09.04.2012, 12:54 **[ТС]**

Сообщение от MiniMin

так что если нужно будет их зарисовать - то координаты можно будет подобрать на ходу во время рисования

Как? Мне это и предстоит делать. Мне нужно будет сделать граф как можно более плоским.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@body90 467 / 344 / 19 Регистрация: 26.05.2009 Сообщений: 2,696

	Как лучше хранить структуру графа 07.04.2012, 16:57. Показов 7584. Ответов 6 Метки нет (Все метки) Здравствуйте! Хочу написать класс для хранения графа. Есть две идеи: 1) хранить список вершин и отдельно список ребер (у каждого ребра будет информация о начальной и конечной вершине) 2) хранить список вершин и для каждой вершины хранить связанные с ней вершины. Кто как считает, как лучше сделать? Добавлено через 14 часов 30 минут Неужели ни у кого нет никакого мнения? 0

@serg42 124 / 106 / 7 Регистрация: 14.02.2010 Сообщений: 263
	07.04.2012, 18:22
	Я бы сделал связанные списки ребер. В классе ребро: точка1, точка2 (координаты), длина ребра, список смежный ребер по точке1, список смежный ребер по точке2. Помню делал лабы по теории графов на C++, там хранил данные в двумерном массиве. 1

@body90 467 / 344 / 19 Регистрация: 26.05.2009 Сообщений: 2,696
	07.04.2012, 18:55 [ТС]
	Мне сейчас нужно хранить не графическое представление графа, а именно его структуру. Добавлено через 3 минуты Ребра у меня не имеют длины (в смысле структуры графа, а не графического отображения). просто думаю как лучше? Хранить отдельно список вершин и список ребер, которые их соединяют (у каждого ребра будет информация о вершинах, которые оно соединяет) или у каждой вершины хранить список соседних вершин, не храня информации о ребрах? 0

@body90 467 / 344 / 19 Регистрация: 26.05.2009 Сообщений: 2,696
	07.04.2012, 23:50 [ТС]
	Граф направлен. Просто потом, чувствую, захотят, чтоб я это всё визуализировал. Значит придется хранить координаты изгиба ребер. 0

@MiniMin 68 / 24 / 2 Регистрация: 16.05.2009 Сообщений: 73
	09.04.2012, 09:16
	если в графе не будут существовать несколько ребер, инцидентных одним и тем же вершинам, то можно матрицей смежности. если граф достаточно разряженный с большим количеством вершин - то ООП с контейнерами смежных вершин для каждой вершины. как вариант ещё матрица инцидентности. в теории графов вершины не имеют координат в классическом понимании. так что если нужно будет их зарисовать - то координаты можно будет подобрать на ходу во время рисования. 1