Типове графики в структурата на данните с примери

Графът е нелинейна структура от данни, която се състои от върхове и ръбове. Върховете съдържат информация или данни, а ръбовете работят като връзка между двойка върхове.

Графиките могат да бъдат от няколко типа в зависимост от позицията на възлите и ръбовете. Ето някои важни типове графики:

Насочена графика

Ръбовете на Directed Graph съдържат стрелки, които означават посоката. Стрелката определя къде сочи или завършва ръбът.

Ето пример за насочена графика.

• Можем да преминем от възел A до D.
• Въпреки това не можем да преминем от възел D към възел A, тъй като ръбът сочи от A към D.
• Тъй като графиката няма тегла, пътуването от връх A до D ще струва същото като пътуването от D до F.

Неориентирана графика

Неориентираната графика съдържа ръбове без указатели. Това означава, че можем да пътуваме обратно между два върха.

Ето прост пример за неориентираната графика.

В горната графика,

• Можем да преминем от А към Б
• Можем също да преминем от B към A
• Ръбовете не съдържат посоки.

Това е пример за неориентиран граф с краен брой върхове и ръбове без тежести.

Претеглена графика

Графика, която съдържа тегла или разходи по краищата, се нарича претеглена графика. Числената стойност обикновено представлява цената на преместване от един връх до друг връх. Както насоченият, така и ненасоченият граф могат да имат тежести по ръбовете си.

Ето пример за претеглена графика (насочена).

• A до B, има предимство и теглото е 5, което означава, че преминаването от A до B ще ни струва 5.
• A сочи към B, но в тази графика B няма пряк ръб над A. Така че не можем да пътуваме от B до A.
• Въпреки това, ако искаме да преминем от A към F, има много пътища. Пътеките са ADF, ABF. ADF ще струва (10+11) или 21.
• Тук пътят ABF ще струва (5+15) или 20. Тук добавяме теглото на всеки ръб в пътя.

Ето пример за неориентирана графика с тегла:

Тук ръбът има тежест, но няма посока. Така че това означава, че пътуването от връх A до D ще струва 10 и обратно.

Двупосочна графика

Двупосочните и неориентираните графи имат общо свойство. това е

• Обикновено неориентираният граф може да има едно ребро между два върха.

Например:

• Тук преминаването от A към D или D към A ще струва 10.
• В двупосочен график можем да имаме две ребра между два върха.

Ето един пример:

Пътуването от A до D ще ни струва 17, но пътуването от D до A ще ни струва 12. Така че не можем да присвоим две различни тегла, ако графиката е неориентирана.

Безкрайна графика

Графиката ще съдържа безкраен брой ръбове и възли. Ако една графа е Infinite и освен това е свързана графа, тогава тя също ще съдържа безкраен брой ребра. Тук разширените ръбове означават, че повече ръбове могат да бъдат свързани към тези възли чрез ръбове.

Ето пример за безкрайната графика:

Нулева графика

Нулевата графика съдържа само възли или върхове, но без ръбове. Ако е даден график G = (V, E), където V са върхове и E са ръбове, той ще бъде нула, ако броят на ръбовете E е нула.

Ето пример за нулева графика:

Тривиална графика

Графична структура от данни се счита за тривиална, ако присъства само един връх или възел без ръбове.

Ето пример за тривиална графика:

Мулти графика

Графът се нарича мултиграф, когато има множество ребра между два върха или върхът има цикъл. Терминът „Кръг“ в Graph Data Structure означава ръб, сочещ към същия възел или връх. Мултиграфът може да бъде насочен или ненасочен.

Ето пример за Multi Graph:

Има две ребра от B до A. Освен това връх E има самообръщение. Горната графика е насочена графа без тежести по ръбовете.

Пълна графика

Графът е пълен, ако всеки връх има насочени или ненасочени ръбове с всички останали върхове.

Да предположим, че има общ V брой върхове и всеки връх има точно V-1 ребра. Тогава тази графика ще се нарича Пълна графика. В този тип графика всеки връх е свързан с всички останали върхове чрез ръбове.

Ето пример за пълна графика с пет върха:

Можете да видите на изображението, че общият брой възли е пет и всички възли имат точно четири ръба.

Свързана графика

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

Ето пример за свързана графика:

Ето малко обяснение на горния „пример за пълна графика“ Graph:

• Ако приемем, че няма ръб между C и F, не можем да пътуваме от A до G. Но ръбът C към F ни позволява да пътуваме до всеки възел от даден възел.
• Пълната графика е свързана графика, защото можем да се преместим от възел към всеки друг възел в дадена графика.

Циклична графика

Една графика се нарича циклична, ако в нея има един или повече цикъла.

Ето пример за циклична графика:

Тук върха A, B и C образуват цикъл.

Една графика може да има множество цикъла вътре в себе си.

Насочена ациклична графика (DAG)

Графът се нарича насочен ацикличен график или DAG, ако няма цикли в графиката. DAG е важен, докато правите Топологично сортиране или намиране на заповедта за изпълнение. DAG също е важен за създаване на системи за планиране или сканиране на зависимост от ресурси и т.н. Горната графика по-горе обаче не съдържа никакъв цикъл вътре.

Ето прост пример за насочен ацикличен график (DAG):

Графика на цикъла

Цикличната графика не е същата като цикличната графика. В Cycle Graph всеки възел ще има точно два свързани ръба, което означава, че всеки възел ще има точно две степени.

Ето пример за циклична графика:

Двустранна графика

Тези видове Графики са специални видове графики, където върховете са присвоени на две групи.

Двустранната графика трябва да следва правилото:

• Два набора от върхове трябва да са различни, което означава, че всички върхове трябва да бъдат разделени на две групи или набори.
• Същият набор Върховете не трябва да образуват ръбове.

Графика на Ойлер

Графичните структури от данни се считат за графика на Ойлер, ако всички върхове имат четна степен. Терминът степен на върховете означава броя на ръбовете, сочещи към или сочещи от определен връх.

Ето пример за графика на Ойлер:

Всички върхове имат четни степени. Връх A, D, E и H имат две степени. Тук възел C има четири степени, което е четно.

Графика на Хамилтън

Hamilton Graph е Connect Graph, където можете да посетите всички върхове от даден връх, без да преглеждате отново същия възел или да използвате същия ръб. Този вид свързана графика е известна като „графа на Хамилтън“. Пътят, който посещавате, за да проверите дали дадената графика е графика на Хамилтън или не, е известен като Хамилтонов път.

Ето прост пример за графика на Хамилтън:

В това изображение можем да посетим всички върхове от всеки възел в горната графика. Един от пътищата може да бъде АДЧБЕ. Също така е възможно да се намери цикъл на Хамилтън. Цикълът на Хамилтън започва и завършва в един и същи връх. И така, цикълът на Хамилтън ще бъде ADCHBEA.