Типове графики в структурата на данните с примери
Сара Чен
⚡ Умно обобщение
Графите в структурата на данните са нелинейни колекции от върхове и ребра, класифицирани в семейства като насочени, ненасочени, претеглени, циклични, ациклични, пълни, свързани, двуделни, Ойлерови и Хамилтънови графи, базирани на структура.
Графът е нелинейна структура от данни, която се състои от върхове и ребра. Върховете съдържат информацията или данните, а ребрата действат като връзка между двойка върхове.
Графите могат да бъдат от няколко вида, в зависимост от позицията на възлите и ръбовете. Ето някои важни видове графи:
Насочена графика
Ръбовете на насочената графа съдържат стрелки, които показват посоката. Стрелката определя къде сочи или свършва ръбът. Ето пример за насочена графа.
Насочена графика
- Можем да преминем от възел A до D.
- Не можем обаче да преминем от възел D към възел A, тъй като ръбът сочи от A към D.
- Тъй като графиката няма тегла, пътуването от връх A до D ще струва същото като пътуването от D до F.
Неориентирана графика
Неориентираният граф съдържа ръбове без указатели. Това означава, че можем да се движим обратно между два върха. Ето един прост пример за неориентиран граф.
Неориентирана графика
В горната графика,
- Можем да се преместим от А до Б.
- Можем също да се преместим от Б към А.
- Ръбовете не съдържат посоки.
Това е пример за неориентиран граф с краен брой върхове и ребра без тегла.
Претеглена графика
Граф, който съдържа тегла или разходи по ръбовете, се нарича претеглен граф. Числовата стойност обикновено представлява разходите за преместване от един връх към друг. Както насочените, така и ненасочените графове могат да имат тегла по ръбовете си. Ето пример за претеглен граф (насочен).
Насочена графика с тегло
- От А до Б има предимство и теглото е 5, което означава, че преместването от А до Б ще ни струва 5.
- А сочи към Б, но в тази графика Б няма пряко предимство над А. Така че не можем да пътуваме от Б до А.
- Ако обаче искаме да се придвижим от 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. Така че, не можем да присвоим две различни тегла, ако е неориентиран граф.
Безкрайна графика
Графът ще съдържа безкраен брой ребра и възли. Ако един граф е безкраен и същевременно е свързан граф, тогава той ще съдържа и безкраен брой ребра. Тук разширените ребра означават, че повече ребра могат да бъдат свързани с тези възли чрез ребра. Ето пример за безкраен граф:
Безкрайна графика
Нулева графика
Нулевият граф съдържа само възли или върхове, но без ръбове. Ако е даден граф G = (V, E), където V са върховете, а E са ръбовете, той ще бъде нулев, ако броят на ръбовете E е нула. Ето пример за нулев граф:
Нулева графика
Тривиална графика
Графовата структура от данни се счита за тривиална, ако е наличен само един връх или възел без ръбове. Ето пример за тривиален граф:
Мулти графика
Графът се нарича мултиграф, когато между два върха има множество ребра или върхът има цикъл. Терминът „цикъл“ в структурата на графовите данни означава ръб, сочещ към един и същ възел или връх. Мултиграфът може да бъде насочен или ненасочен. Ето пример за мултиграф:
Има два ръба от B до A. Освен това, върхът E има самоциклична структура. Горният график е насочен граф без тегла върху ръба.
Пълна графика
Графът е завършен, ако всеки връх има насочени или ненасочени ребра с всички останали върхове. Да предположим, че има общо V брой върхове и всеки връх има точно V-1 ребра. Тогава този граф ще се нарича пълен граф. В този тип граф всеки връх е свързан с всички останали върхове чрез ребра. Ето пример за пълен граф с пет върха:
Можете да видите на изображението, че общият брой на възлите е пет и всички възли имат точно четири ръба.
Свързана графика
Графът се нарича свързан граф, ако започваме от възел или връх и можем да стигнем до всички възли от началния възел. За тази цел трябва да има поне едно ребро между всяка двойка възли или върхове. Ето пример за свързан граф:
Ето някои обяснения на горния свързан граф:
- Ако приемем, че няма ръб между C и F, не можем да пътуваме от A до G. Ръбът от C до F обаче ни позволява да пътуваме до всеки възел от даден възел.
- Пълната графика е свързана графика, защото можем да се преместим от възел към всеки друг възел в дадена графика.
Циклична графика
Графът се нарича цикличен, ако в него има един или повече цикли. Ето пример за цикличен граф:
Тук върховете A, B и C образуват цикъл. Графът може да има множество цикли вътре в него.
Насочена ациклична графика (DAG)
Графът се нарича насочен ацикличен граф или DAG, ако в него няма цикли. DAG е важен при извършване на Топологично сортиране или намиране на реда на изпълнение. DAG е важен и за създаване на системи за планиране или сканиране на зависимостта на ресурсите и т.н. Графиката по-горе обаче не съдържа никакъв цикъл вътре. Ето един прост пример за насочен ацикличен граф (DAG):
Графика на цикъла
Цикличният граф не е същият като цикличния граф. В цикличния граф всеки възел ще има точно два свързани ръба, което означава, че всеки възел ще има точно две степени. Ето пример за цикличен граф:
Двустранна графика
Тези видове Графики са специални видове графове, където върховете са присвоени на две множества. Двуделният граф трябва да следва правилото:
- Двата комплекта върхове трябва да са различни, което означава, че всички върхове трябва да бъдат разделени на две групи или комплекта.
- Върховете от един и същи набор не трябва да образуват ръбове.
Графика на Ойлер
Структурата от данни тип „граф“ се счита за граф на Ойлер, ако всички върхове имат четна степен. Терминът „степен на върховете“ означава броя на ръбовете, сочещи към или сочещи от определен връх. Ето пример за граф на Ойлер:
Всички върхове имат четни степени. Върховете A, D, E и H имат по две степени. Тук възел C има четири степени, което е четно.
Графика на Хамилтън
Графът на Хамилтън е свързан граф, където можете да посетите всички върхове от даден връх, без да посещавате отново същия възел или да използвате същото ребро. Този вид свързан граф е известен като „граф на Хамилтън“. Пътят, който посещавате, за да проверите дали даден граф е граф на Хамилтън или не, е известен като Хамилтонов път. Ето един прост пример за граф на Хамилтън:
В това изображение можем да посетим всички върхове от всеки възел в горната графика. Един от пътищата може да бъде АДЧБЕВъзможно е също да се намери цикъл на Хамилтън. Цикълът на Хамилтън започва и завършва в един и същ връх. Следователно, цикълът на Хамилтън ще бъде ADCHBEA.
