mafulechka
mafulechkaМаусым 7, 2019, 4:34 Т.Ж.

График. Деректер құрылымы.

графиялық деректер құрылымы – деректері бар және басқа түйіндерге қосылған түйіндер жиынтығы.


Мұны мысалмен түсінуге тырысайық. Фейсбукта бәрі түйін болып табылады. Бұған пайдаланушы, фотосурет, альбом, оқиға, топ, бет, түсініктеме, оқиға, бейне, сілтеме, жазба... деректері бар кез келген нәрсе түйін болып табылады.

Әрбір қатынас бір түйіннен екіншісіне жиек болып табылады. Фотосуретті жариялап жатсаңыз да, бет сияқты топқа қосылсаңыз да, т.б. Бұл қатынастар үшін жаңа жиек жасалады.

Сонда бүкіл facebook түйіндер мен жиектер жиынтығы. Себебі facebook өз деректерін сақтау үшін графикалық деректер құрылымын пайдаланады.

Дәлірек айтқанда, граф – бұл деректер құрылымы (V, E) ол мыналардан тұрады:

  • Vertex жинағы V.
  • Төбелердің реттелген жұптары (u, v) ретінде ұсынылған E жиектерінің жиынтығы.

Санау енгізілді

V = {0, 1, 2, 3}
E = {(0,1), (0,2), (0,3), (1,2)}
G = {V, E}

Терминологиялық график

  • Көршілестік.
    Егер оларды қосатын жиек болса, төбе басқа төбеге іргелес деп аталады.
    2 және 3 шыңдар іргелес емес, өйткені олардың арасында жиек жоқ.

  • Жол.
    А шыңынан В шыңына өтуге мүмкіндік беретін жиектер тізбегі жол деп аталады.
    0-1, 1-2 және 0-2 - 0 түйінінен 2 түйініне дейінгі жолдар.

  • Бағдарланған график.
    Шеті (u, v) болатын граф міндетті түрде жиегі де (v, u) бар дегенді білдірмейді. Мұндай сюжеттегі жиектер жиектің бағытын көрсету үшін көрсеткілермен бейнеленген.

Графиктерді көрсету әдістері

Графиктер әдетте екі жолмен беріледі:

1. Көршілестік матрицасы

Іршілестік матрицасы – V x V төбелерінің екі өлшемді (2D) массиві. Әрбір жол мен баған шыңды білдіреді.

Егер a[i][j] кез келген элементінің мәні 1 болса, бұл i шыңы мен j төбесін қосатын жиек бар екенін білдіреді.

Жоғарыда біз жасаған график үшін көршілестік матрицасы.

Бұл бағытталмаған график болғандықтан, шеткі (0,2) үшін біз де жиекті (2,0) белгілеп, іргелес матрицаны диагональға қатысты симметриялы етуіміз керек.

Жиектерді іздеу (А шыңы мен В шыңы арасында жиек бар-жоғын тексеру) іргелес матрицаны көрсетуде өте жылдам, бірақ біз барлық шыңдар (V x V) арасындағы әрбір ықтимал байланыс үшін бос орынды сақтауымыз керек, сондықтан оған көбірек орын қажет.

2. іргелес тізім

Іршілес тізім – байланысқан тізім массиві түріндегі график.

Жиым индексі шыңды көрсетеді және оның байланыстырылған тізіміндегі әрбір элемент шыңымен жиекті құрайтын басқа шыңдарды көрсетеді.

Бірінші мысалда біз жасаған графиктің іргелестік тізімі келесідей көрінеді:

Іргелестік тізімі сақтауда тиімді, өйткені бізге тек жиектер үшін мәндерді сақтау керек. Миллиондаған шыңдары бар график үшін бұл көп кеңістікті үнемдейді.

Графиктердегі амалдар

Ең көп таралған графикалық операциялар:

  • Графикте элементтің бар-жоғын тексеріңіз.
  • Графикті айналдыру.
  • Графикке элементтерді (төбелер, жиектер) қосыңыз.
  • Бір шыңнан екіншісіне жол табу.
Рекомендуем хостинг TIMEWEB
Рекомендуем хостинг TIMEWEB
Стабильный хостинг, на котором располагается социальная сеть EVILEG. Для проектов на Django рекомендуем VDS хостинг.

Ол саған ұнайды ма? Әлеуметтік желілерде бөлісіңіз!

Пікірлер

Тек рұқсаты бар пайдаланушылар ғана пікір қалдыра алады.
Кіріңіз немесе Тіркеліңіз
AD

C++ - Тест 004. Указатели, Массивы и Циклы

  • Нәтиже:50ұпай,
  • Бағалау ұпайлары-4
m
  • molni99
  • Қаз. 26, 2024, 1:37 Т.Ж.

C++ - Тест 004. Указатели, Массивы и Циклы

  • Нәтиже:80ұпай,
  • Бағалау ұпайлары4
m
  • molni99
  • Қаз. 26, 2024, 1:29 Т.Ж.

C++ - Тест 004. Указатели, Массивы и Циклы

  • Нәтиже:20ұпай,
  • Бағалау ұпайлары-10
Соңғы пікірлер
ИМ
Игорь МаксимовҚар. 22, 2024, 11:51 Т.Ж.
Django - Оқулық 017. Теңшелген Django кіру беті Добрый вечер Евгений! Я сделал себе авторизацию аналогичную вашей, все работает, кроме возврата к предидущей странице. Редеректит всегда на главную, хотя в логах сервера вижу запросы на правильн…
Evgenii Legotckoi
Evgenii LegotckoiҚаз. 31, 2024, 2:37 Т.Қ.
Django - Сабақ 064. Python Markdown кеңейтімін қалай жазуға болады Добрый день. Да, можно. Либо через такие же плагины, либо с постобработкой через python библиотеку Beautiful Soup
A
ALO1ZEҚаз. 19, 2024, 8:19 Т.Ж.
Qt Creator көмегімен fb3 файл оқу құралы Подскажите как это запустить? Я не шарю в программировании и кодинге. Скачал и установаил Qt, но куча ошибок выдается и не запустить. А очень надо fb3 переконвертировать в html
ИМ
Игорь МаксимовҚаз. 5, 2024, 7:51 Т.Ж.
Django - Сабақ 064. Python Markdown кеңейтімін қалай жазуға болады Приветствую Евгений! У меня вопрос. Можно ли вставлять свои классы в разметку редактора markdown? Допустим имея стандартную разметку: <ul> <li></li> <li></l…
d
dblas5Шілде 5, 2024, 11:02 Т.Ж.
QML - Сабақ 016. SQLite деректер қоры және онымен QML Qt-та жұмыс істеу Здравствуйте, возникает такая проблема (я новичок): ApplicationWindow неизвестный элемент. (М300) для TextField и Button аналогично. Могу предположить, что из-за более новой верси…
Енді форумда талқылаңыз
m
moogoҚар. 22, 2024, 7:17 Т.Ж.
Mosquito Spray System Effective Mosquito Systems for Backyard | Eco-Friendly Misting Control Device & Repellent Spray - Moogo ; Upgrade your backyard with our mosquito-repellent device! Our misters conce…
Evgenii Legotckoi
Evgenii LegotckoiМаусым 24, 2024, 3:11 Т.Қ.
добавить qlineseries в функции Я тут. Работы оень много. Отправил его в бан.
t
tonypeachey1Қар. 15, 2024, 6:04 Т.Ж.
google domain [url=https://google.com/]domain[/url] domain [http://www.example.com link title]
NSProject
NSProjectМаусым 4, 2022, 3:49 Т.Ж.
Всё ещё разбираюсь с кешем. В следствии прочтения данной статьи. Я принял для себя решение сделать кеширование свойств менеджера модели LikeDislike. И так как установка evileg_core для меня не была возможна, ибо он писался…

Бізді әлеуметтік желілерде бақылаңыз