graph implementation c using adjacency list
Този урок обяснява прилагането на графики в C ++. Също така ще научите за различните типове, представяния и приложения на графики:
Графиката е нелинейна структура от данни. Графиката може да бъде дефинирана като колекция от възли, които също се наричат „върхове“ и „ръбове“, които свързват два или повече върха.
Графика може да се разглежда и като циклично дърво, където върховете нямат връзка родител-дете, но поддържат сложна връзка между тях.
как изглежда ключът за мрежова сигурност
=> Щракнете тук за абсолютната серия за обучение на C ++.
Какво ще научите:
Какво е графика в C ++?
Както беше посочено по-горе, графика в C ++ е нелинейна структура от данни, дефинирана като колекция от върхове и ребра.
Следва пример за структура на графични данни.
Дадено по-горе е примерна графика G. Графика G е набор от върхове {A, B, C, D, E} и набор от ребра {(A, B), (B, C), (A, D), (D, E), (E, C), (B, E), (B, D)}.
Видове графики - насочена и ненасочена графика
Графика, в която ръбовете нямат посоки, се нарича Ненасочена графика. Графиката, показана по-горе, е ненасочена графика.
Графика, в която ръбовете имат посоки, свързани с тях, се нарича Направена графика.
Даден по-долу е пример за насочена графика.
В посочената графика, показана по-горе, ръбовете образуват подредена двойка, при която всеки ръб представлява определен път от един връх към друг връх. Вершината, от която пътят се инициира, се нарича „ Първоначален възел ”, Докато върхът, в който пътят завършва, се нарича„ Терминален възел ”.
По този начин в горната графика множеството върхове е {A, B, C, D, E}, а реброто е {(A, B), (A, D), (B, C), (B, E ), (D, E) (E, C)}.
Ще обсъдим терминологията на графиката или общите термини, използвани във връзка с графиката по-долу.
Графична терминология
- Върх: Всеки възел на графиката се нарича връх. В горната графика A, B, C и D са върховете на графиката.
- Ръб, край: Връзката или пътеката между два върха се нарича ръб. Той свързва два или повече върха. Различните ръбове в горната графика са AB, BC, AD и DC.
- Съседен възел: В графика, ако два възела са свързани с ръб, те се наричат съседни възли или съседи. В горната графика върховете A и B са свързани с ръб AB. По този начин A и B са съседни възли.
- Степен на възела: Броят на ръбовете, които са свързани към определен възел, се нарича степента на възела. В горната графика възел A има степен 2.
- Път: Последователността на възлите, която трябва да следваме, когато трябва да пътуваме от един връх към друг в графика, се нарича път. В нашата примерна графика, ако трябва да преминем от възел A към C, тогава пътят ще бъде A-> B-> C.
- Затворен път: Ако началният възел е същият като терминален възел, тогава този път се нарича затворен път.
- Прост път: Затворен път, в който всички останали възли са различни се нарича прост път.
- Цикъл: Път, в който няма повтарящи се ръбове или върхове, а първият и последният върхове са еднакви, се нарича цикъл. В горната графика A-> B-> C-> D-> A е цикъл.
- Свързана графика: Свързана графика е тази, в която има път между всеки от върховете. Това означава, че няма нито един връх, който да е изолиран или без свързващ ръб. Графиката, показана по-горе, е свързана графика.
- Пълна графика: Графика, в която всеки възел е свързан с друг, се нарича Пълна графика. Ако N е общият брой възли в графика, тогава пълната графика съдържа N (N-1) / 2 броя ръбове.
- Претеглена графика: Положителна стойност, присвоена на всеки ръб, показваща неговата дължина (разстояние между върховете, свързани с ръб), се нарича тегло. Графиката, съдържаща претеглени ръбове, се нарича претеглена графика. Теглото на ребро e се обозначава с w (e) и показва цената на пресичане на ребро.
- Диаграма: Диграфът е графика, в която всеки ръб е свързан с определена посока и обхождането може да се извърши само в определена посока.
Представяне на графика
Начинът, по който структурата на данните за графика се съхранява в паметта, се нарича „представяне”. Графиката може да се съхранява като последователно представяне или като свързано представяне.
И двата вида са описани по-долу.
Последователно представяне
В последователното представяне на графики използваме матрицата на съседство. Матрицата за съседство е матрица с размер n x n, където n е броят на върховете в графиката.
Редовете и колоните на матрицата на съседство представляват върховете в графика. Матричният елемент е зададен на 1, когато между върховете има ръб. Ако ръбът не присъства, тогава елементът е зададен на 0.
Дадено по-долу е примерна графика, която показва нейната матрица на съседство.
Видяхме матрицата на съседство за горната графика. Имайте предвид, че тъй като това е ненасочена графика, и можем да кажем, че ръбът присъства и в двете посоки. Например, тъй като реброто AB е налице, можем да заключим, че ръб BA също присъства.
В матрицата на съседство можем да видим взаимодействията на върховете, които са елементи на матрицата, които са зададени на 1, когато ръбът присъства и на 0, когато ръбът отсъства.
Сега нека видим матрицата на съседство на насочена графика.
Както е показано по-горе, пресечната точка в матрицата на съседство ще бъде 1, ако и само ако има ръб, насочен от един връх към друг.
В горната графика имаме два ръба от връх А. Един ръб завършва във връх В, докато вторият завършва във връх С. По този начин в матрицата на съседство пресичането на A & B е зададено на 1 като пресичане на A & C.
След това ще видим последователното представяне на претеглената графика.
По-долу е дадена претеглената графика и съответната матрица за съседство.
Можем да видим, че последователното представяне на претеглена графика е различно от другите видове графики. Тук ненулевите стойности в матрицата на съседство се заменят с действителното тегло на ръба.
Ръбът AB има тегло = 4, като по този начин в матрицата на съседство задаваме пресечната точка на A и B на 4. По същия начин всички останали ненулеви стойности се променят до съответните им тегла.
Списъкът за съседство е по-лесен за изпълнение и следване. Обръщането, т.е.за да се провери дали има ръб от един връх към друг, отнема време O (1), а премахването на ръб също отнема O (1).
Независимо дали графиката е оскъдна (по-малко ръбове) или плътна, тя винаги отнема повече пространство.
Свързано представителство
Използваме списъка на съседствата за свързаното представяне на графиката. Представянето на списъка за съседство поддържа всеки възел на графиката и връзка към възлите, които са в съседство с този възел. Когато прекосим всички съседни възли, задаваме следващия указател на null в края на списъка.
Нека първо разгледаме ненасочена графика и нейния списък на съседство.
Както е показано по-горе, имаме свързан списък (списък на съседство) за всеки възел. От връх A имаме ръбове до върхове B, C и D. По този начин тези възли са свързани с възел A в съответния списък за съседство.
След това изграждаме списък за съседство за насочената графика.
В посочената по-горе графика виждаме, че няма ръбове, произхождащи от връх Е. Следователно списъкът за съседство за връх Е е празен.
Сега нека изградим списъка на съседствата за претеглената графика.
За претеглена графика добавяме допълнително поле във възела на списъка за съседство, за да обозначим теглото на ръба, както е показано по-горе.
Добавянето на връх в списъка за съседство е по-лесно. Освен това спестява място поради изпълнението на свързания списък. Когато трябва да разберем дали има ръб между един връх към друг, операцията не е ефективна.
Основни операции за графики
Следват основните операции, които можем да извършим върху структурата на данните на графиката:
- Добавяне на връх: Добавя връх към графиката.
- Добавете ръб: Добавя ръб между двата върха на графика.
- Показване на върховете на графиката: Показване на върховете на графика.
Внедряване на графика C ++, използвайки списък за съседство
Сега представяме реализация на C ++, за да демонстрираме проста графика, използвайки списъка за съседство.
Тук ще покажем списъка за съседство за претеглена насочена графика. Използвали сме две структури, за да задържим списъка за съседство и ръбовете на графиката. Списъкът за съседство се показва като (start_vertex, end_vertex, тегло).
Програмата C ++ е както следва:
#include using namespace std; // stores adjacency list items struct adjNode { int val, cost; adjNode* next; }; // structure to store edges struct graphEdge { int start_ver, end_ver, weight; }; class DiaGraph{ // insert new nodes into adjacency list from given graph adjNode* getAdjListNode(int value, int weight, adjNode* head) { adjNode* newNode = new adjNode; newNode->val = value; newNode->cost = weight; newNode->next = head; // point new node to current head return newNode; } int N; // number of nodes in the graph public: adjNode **head; //adjacency list as array of pointers // Constructor DiaGraph(graphEdge edges(), int n, int N) { // allocate new node head = new adjNode*(N)(); this->N = N; // initialize head pointer for all vertices for (int i = 0; i Изход:
Изход:
Графичен списък за съседство
(start_vertex, end_vertex, тегло):
(0, 2, 4) (0, 1, 2)
(1, 4, 3)
(2, 3, 2)
(3, 1, 4)
(4, 3, 3)
Приложения на графики
Нека обсъдим някои от приложенията на графиките.
въпроси и отговори за поведенчески интервюта за бизнес анализатор
- Графиките се използват широко в компютърните науки за изобразяване на мрежови графики или семантични графики или дори за изобразяване на потока от изчисления.
- Графиките се използват широко в компилаторите, за да изобразят разпределението на ресурси за процеси или да посочат анализ на потока от данни и т.н.
- Графиките се използват и за оптимизиране на заявки в езици на бази данни в някои специализирани компилатори.
- В сайтовете за социални мрежи графиките са основните структури за изобразяване на мрежата от хора.
- Графиките се използват широко за изграждане на транспортната система, особено пътната мрежа. Популярен пример са картите на Google, които широко използват графики за посочване на упътвания по целия свят.
Заключение
Графиката е популярна и широко използвана структура от данни, която има много приложения в самата област на компютърните науки, освен другите области. Графиките се състоят от върхове и ръбове, свързващи два или повече върха.
Графиката може да бъде насочена или насочена. Можем да представим графики, използвайки матрица на съседство, която е линейно представяне, както и използвайки списък със свързани съседства. Също така обсъдихме изпълнението на графиката в този урок.
=> Вижте тук, за да разгледате пълния списък с уроци за C ++.
Препоръчително четене
- Урок за разширени списъци на Python (Сортиране по списък, обръщане, индекс, копиране, присъединяване, сума)
- Python List - Създаване, достъп, нарязване, добавяне или изтриване на елементи
- Списък на IP адресите по подразбиране за обичайните марки безжични рутери
- 12 най-добри инструмента за създаване на линейни графики за създаване на зашеметяващи линейни графики (2021 РЕЙТИНГИ)
- Парола за вход за рутер по подразбиране за най-добрите модели рутери (Списък 2021)
- Свързана структура на списъка с данни в C ++ с илюстрация
- Структура на данните от циркулярно свързан списък в C ++ с илюстрация
- Структура на данните от двойно свързан списък в C ++ с илюстрация
