Така че сте нов в структурите от данни и сте научили за свързани списъци и двоични дървета, но какво, по дяволите, са графиките?!

Здравейте Графики

За да не се бъркате с графиките, за които сте научили в часовете по математика в началното училище, графиките са гъвкава структура от данни, която представлява колекция от възли, носещи данни, и връзките между възлите. Всъщност дърветата са просто специален тип графики, които имат минимални връзки, без цикли и корен. Чудесно за представяне на сложни мрежи (независимо дали социални или физически), възлите на графиката могат да сочат към произволен брой други възли в графиката (включително себе си, наречен цикъл) и връзките между тях могат да съдържат информация за посоката и тежестта (повече за това по-долу).

Графиките се състоят от две основни части:
1. Върхове — където се съхраняват действителните данни (известни също като възли)
2. Ръбове — линиите, свързващи върховете

Графиките могат да бъдат насочени или ненасочени:
Насочени— краищата показват посоката, в която сочи връзката, независимо дали е еднопосочна (мислете за несподелена любов) или в двете посоки
Ненасочени — ръбовете винаги представляват връзки, които съществуват и в двете посоки

Освен посока, ръбовете могат да имат и стегло. Обикновено (макар и не непременно) число между 0 и 1, теглото на ребро просто обозначава стойност или цена, свързана с връзката на тези два върха.

Представете си мрежа от 4 души:Алис и Бет са най-добри приятелки — те постоянно чатят и общуват ежедневно. Бет и Клои са приятелки, но не са толкова близки и си взаимодействат само от време на време. Даяна е онова момиче, което Бет и Клоуи срещнаха онзи път на парти и след това никога повече не ги видяха. Можем да си представим, че една претеглена графика на тяхната мрежа ще изглежда като тази графика по-долу:

Чудесен пример за използване на претеглена графика за представяне на физическа мрежа е Google Maps. Когато картографирате упътвания между две местоположения (върхове), Google Maps често предлага повече от една опция за маршрут. Тези маршрути са ръбове, които имат различна стойност (тегло), свързана с всеки от тях, въз основа на редица фактори, включително разстояние и време за пътуване. Като се има предвид теглото, Google Maps ще подчертае и предложи най-бързия маршрут в синьо.

Нуждаете се от друго реално приложение на графика? Е, вие гледате един в момента. Цялата мрежа е графика! Това е огромна, сложна мрежа от страници, които сочат една към друга. Когато навигираме между URL адреси, ние наистина просто отиваме към и от върхове. Някои краища са насочени (можете да преминавате само от една страница към друга, но не и обратното), а някои не са (можете да се движите свободно напред и назад между тях). Умопомрачително, нали?

Списък на съседство Vs. Матрица на съседство

Два често срещани начина за представяне на графика са 1) списък на съседство и 2) матрица на съседство. Има плюсове и минуси и на двете, но като цяло матриците на съседство се използват за плътни графики (графи с много ребра), а списъците на съседство се използват за разредени графи (графи с малко ребра).

Един списък със съседство ще има списък на всички възли в графиката отляво, като всеки сочи към друг списък с всички възли, към които е свързан. За редки графики списъкът със съседство би бил по-ефективен, тъй като няма да се губи място за представяне на връзки, които не съществуват.

Реализацията на матрица на съседство представлява всички ръбове между всички възли, независимо дали съществуват или не. 0 означава, че няма връзка, а 1 означава, че съществува връзка между тези два възела. Елементите в матрицата също могат да показват посока - например в графиката по-долу ръбът между A и B съществува само в една посока и следователно в матрицата на съседство (A, B) е 0, но (B, A) е 1.

За големи, плътни графики матрицата на съседство може компактно да съхранява връзките, тъй като всеки запис в матрицата изисква само един бит за съхранение. Има и алтернативни форми на матрици, където числото представлява претеглената стойност, се съхраняват в елементите на самата матрица или където елементите сочат към крайни обекти (или нула, ако няма край), въпреки че това би увеличило необходимото количество памет за матрицата.

Big O: List vs Matrix

И така, как да разберете кой да използвате? Е, зависи какво е най-важно за вашия случай на употреба. Вашата графика голяма или малка ще бъде? Дали пространството е по-голям проблем или бихте предпочели по-бързо време за преминаване?

За повечето приложения на графики обаче списъкът със съседство е достатъчен и най-подходящ.

Основни изводи

  1. Графите са колекция от върхове и ръбове, които представляват данни и техните връзки.
  2. Графиките могат да се използват за всички видове мрежи (социални, физически и т.н.) — реалните приложения включват Facebook и Google Maps.
  3. В повечето случаи списъкът със съседство е по-добър.

Надяваме се, че вече разбирате по-добре графиките, но имайте предвид, че това е само върхът на айсберга. Има причина, поради която големи компании като LinkedIn, Google и Facebook разчитат в голяма степен на графики – прочетете за мотивите зад прехода на Facebook през 2007 г. от релационни бази данни към бази данни с графики „тук“ или за мащабирането на базите данни на LinkedIn „тук“.

Нататък!

  1. freeCodeCamp има „страхотно въведение“ към действителното имплементиране на графична структура от данни с Javascript.
  2. Получете бърза практика с „урока за графично представяне“ на Khan Academy.
  3. Искате повече подробности за списъци и матрици за съседство? Прочетете статията на Vaidehi Joshi относно графичното представяне, което върши невероятна работа при разбиването на концепциите!
  4. Все още жадувате за повече? Преминете към дълбоките неща тук.