java graph tutorial how implement graph data structure
Този изчерпателен урок за графики на Java обяснява подробно структурата на графичните данни. Включва как да създавате, внедрявате, представяте и обхождате графики в Java:
Графичната структура на данните представлява основно мрежа, свързваща различни точки. Тези точки се наричат върхове, а връзките, свързващи тези върхове, се наричат „Edges“. Така че графика g се дефинира като набор от върхове V и ребра E, които свързват тези върхове.
Графиките се използват най-вече за представяне на различни мрежи като компютърни мрежи, социални мрежи и др. Те също могат да се използват за представяне на различни зависимости в софтуера или архитектурите. Тези графики на зависимостите са много полезни при анализирането на софтуера, а понякога и при отстраняването на грешки.
=> Проверете ВСИЧКИ уроци за Java тук.
Какво ще научите:
- Структура на данните за графика Java
- Как да създам графика?
- Внедряване на графики в Java
- Java Graph Library
- Заключение
Структура на данните за графика на Java
По-долу е дадена графика с пет върха {A, B, C, D, E} и ръбове, дадени от {{AB}, {AC}, {AD}, {BD}, {CE}, {ED}}. Тъй като ръбовете не показват никакви посоки, тази графика е известна като „неориентирана графика“.
Освен неориентираната графика, показана по-горе, има няколко варианта на графиката в Java.
Нека обсъдим подробно тези варианти.
Различни варианти на графика
Следват някои от вариантите на графиката.
# 1) Насочена графика
Насочена графика или диграф е структура от данни на графика, в която ръбовете имат определена посока. Те произхождат от един връх и завършват в друг връх.
Следващата диаграма показва примера на насочена графика.
В горната диаграма има ръб от връх A до връх B. Но имайте предвид, че A до B не е същото като B до A, както в ненасочена графика, освен ако няма ръб, посочен от B до A.
Насочената графика е циклична, ако има поне един път, който има първия и последния връх еднакви. В горната диаграма път A-> B-> C-> D-> E-> A образува насочен цикъл или циклична графика.
Обратно, насочена ациклична графика е графика, в която няма насочен цикъл, т.е. няма път, който образува цикъл.
# 2) Претеглена графика
В претеглена графика, тежесте свързано с всеки ръб на графиката. Тежестта обикновено показва разстоянието между двата върха. Следващата диаграма показва претеглената графика. Тъй като не са показани упътвания, това е неориентираната графика.
Обърнете внимание, че претеглената графика може да бъде насочена или ненасочена.
Как да създам графика?
Java не осигурява пълноценно изпълнение на структурата на графичните данни. Въпреки това, можем да представим графиката програмно, като използваме Колекции в Java. Също така можем да реализираме графика, използвайки динамични масиви като вектори.
Обикновено ние прилагаме графики в Java, използвайки колекцията HashMap. Елементите на HashMap са под формата на двойки ключ-стойност. Можем да представим списъка за съседство на графики в HashMap.
Най-често срещаният начин за създаване на графика е чрез използване на едно от представянията на графики като матрица на съседство или списък на съседство. След това ще обсъдим тези представяния и след това ще внедрим графиката в Java, като използваме списъка за съседство, за който ще използваме ArrayList.
Представяне на графики в Java
Представянето на графика означава подход или техника, при които данните на графиките се съхраняват в паметта на компютъра.
Имаме две основни изображения на графики, както е показано по-долу.
Матрица на съседство
Матрицата на съседство е линейно представяне на графики. Тази матрица съхранява картографирането на върховете и ръбовете на графиката. В матрицата на съседство върховете на графиката представляват редове и колони. Това означава, че ако графиката има N върха, тогава матрицата на съседство ще има размер NxN.
Ако V е набор от върхове на графиката, пресечната точка Mijв списъка за съседство = 1 означава, че съществува ръб между върховете i и j.
За да разберем по-добре тази концепция ясно, нека подготвим матрица за съседство за неориентирана графика.
въпрос за интервю за тестване на софтуер за по-свеж
Както се вижда от горната диаграма, виждаме, че за връх A пресичанията AB и AE са настроени на 1, тъй като има ръб от A до B и A до E. По същия начин пресичането BA е зададено на 1, тъй като това е ненасочено графика и AB = BA. По същия начин сме задали всички останали пресичания, за които има ръб на 1.
В случай, че графиката е насочена, пресечната точка Mijще бъде зададено на 1 само ако има ясен ръб, насочен от Vi към Vj.
Това е показано на следващата илюстрация.
Както можем да видим от горната диаграма, има ръб от A до B. Така че пресечната точка AB е зададена на 1, но пресечната точка BA е зададена на 0. Това е така, защото няма ръб, насочен от B към A.
Помислете за върховете E и D. Виждаме, че има ръбове от E до D, както и D до E. Следователно сме задали и двете пресичания на 1 в матрицата на съседство.
Сега преминаваме към претеглени графики. Както знаем за претеглената графика, цяло число, известно още като тегло, е свързано с всеки ръб. Представяме това тегло в матрицата на съседство за съществуващия ръб. Това тегло се посочва винаги, когато има ръб от един връх към друг, вместо „1“.
Това представяне е показано по-долу.
Списък на съседство
Вместо да представяме графика като матрица на съседство, която е последователна по своята същност, можем също да използваме свързано представяне. Това свързано представяне е известно като списък за съседство. Списъкът за съседство не е нищо друго освен свързан списък и всеки възел в списъка представлява връх.
Наличието на ръб между два върха се обозначава с указател от първия връх към втория. Този списък на съседство се поддържа за всеки връх в графиката.
Когато сме обходили всички съседни възли за определен възел, ние съхраняваме NULL в следващото поле на показалеца на последния възел от списъка на съседство.
Сега ще използваме горните графики, които използвахме за представяне на матрицата на съседство, за да демонстрираме списъка на съседствата.
Горната фигура показва списъка на съседство за недиректираната графика. Виждаме, че всеки връх или възел има своя списък за съседство.
В случай на неориентирана графика, общата дължина на списъците за съседство обикновено е два пъти броя на ръбовете. В горната графика общият брой на ръбовете е 6, а общият или сумата от дължината на целия списък за съседство е 12.
Сега нека подготвим списък за съседство за насочената графика.
Както се вижда от горната фигура, в насочената графика общата дължина на списъците за съседство на графиката е равна на броя на ръбовете в графиката. В горната графика има 9 ръба и сума от дължините на съседните списъци за тази графика = 9.
Сега нека разгледаме следната претеглена насочена графика. Имайте предвид, че всеки ръб на претеглената графика има свързана с нея тежест. Така че, когато представяме тази графика със списъка за съседство, трябва да добавим ново поле към всеки възел на списъка, което ще означава тежестта на ръба.
Списъкът на съседство за претеглената графика е показан по-долу.
Горната диаграма показва претеглената графика и нейния списък за съседство. Имайте предвид, че в списъка за съседство има ново пространство, което обозначава теглото на всеки възел.
Внедряване на графики в Java
Следващата програма показва изпълнението на графика в Java. Тук използвахме списъка за съседство, за да представим графиката.
import java.util.*; //class to store edges of the weighted graph class Edge { int src, dest, weight; Edge(int src, int dest, int weight) { this.src = src; this.dest = dest; this.weight = weight; } } // Graph class class Graph { // node of adjacency list static class Node { int value, weight; Node(int value, int weight) { this.value = value; this.weight = weight; } }; // define adjacency list List adj_list = new ArrayList(); //Graph Constructor public Graph(List edges) { // adjacency list memory allocation for (int i = 0; i Изход:
Графика за обръщане на Java
За да извършим някакво смислено действие като търсене на наличието на каквито и да е данни, трябва да прекосим графиката така, че всеки връх и ръбът на графиката да бъдат посетени поне веднъж. Това се прави с помощта на графични алгоритми, които не са нищо друго освен набор от инструкции, които ни помагат да преминем през графиката.
Поддържат се два алгоритма за пресичане на графиката в Java .
- Дълбочина първо обхождане
- Обхождане първо по широчина
Дълбочина първо обхождане
Търсене с дълбочина първо (DFS) е техника, която се използва за пресичане на дърво или графика. Техниката DFS започва с корен възел и след това преминава през съседните възли на корен възел, като навлиза по-дълбоко в графиката. В техниката DFS възлите се обхождат в дълбочина, докато няма повече деца за изследване.
След като достигнем листния възел (няма повече дъщерни възли), DFS се връща назад и започва с други възли и извършва обход по подобен начин. Техниката DFS използва структура на данни от стека, за да съхранява възлите, които се обхождат.
Следва алгоритъмът за техниката DFS.
Алгоритъм
Стъпка 1: Започнете с коренния възел и го поставете в стека
Стъпка 2: Изпратете елемента от стека и го вмъкнете в списъка „посетени“
Стъпка 3: За възел, маркиран като „посетен“ (или в посетен списък), добавете съседните възли на този възел, които все още не са маркирани като посетени, в стека.
Стъпка 4: Повторете стъпки 2 и 3, докато стекът се изпразни.
Илюстрация на DFS техниката
Сега ще илюстрираме техниката DFS, използвайки подходящ пример за графика.
Дадено по-долу е примерна графика. Поддържаме стека, за да съхраняваме проучени възли и списък за съхраняване на посетени възли.
Ще започнем с А, за да започнем, маркираме го като посетено и го добавяме към посетения списък. След това ще разгледаме всички съседни възли на A и ще ги избутаме в стека, както е показано по-долу.
пример за тестване на бяла кутия
След това изваждаме възел от стека, т.е.В, и го маркираме като посетен. След това го добавяме към списъка „посетени“. Това е представено по-долу.
Сега разглеждаме съседните възли на B, които са A и C. От това A вече е посетен. Така че ние го игнорираме. След това изваждаме C от стека. Марка C като посетена. Съседният възел на C, т.е.E се добавя към стека.
След това изваждаме следващия възел E от стека и го маркираме като посетен. Съседният възел на възел Е е C, който вече е посетен. Така че ние го игнорираме.
Сега в стека остава само възел D. Затова го отбелязваме като посетен. Съседният му възел е A, който вече е посетен. Така че не го добавяме към стека.
В този момент стекът е празен. Това означава, че сме завършили обхождането с първа дълбочина за дадената графика.
Посетеният списък дава последната последователност на траверса, използвайки техниката на дълбочина първо. Крайната DFS последователност за горната графика е A-> B-> C-> E-> D.
Внедряване на DFS
import java.io.*; import java.util.*; //DFS Technique for undirected graph class Graph { private int Vertices; // No. of vertices // adjacency list declaration private LinkedList adj_list(); // graph Constructor: to initialize adjacency lists as per no of vertices Graph(int v) { Vertices = v; adj_list = new LinkedList(v); for (int i=0; i Изход:
Приложения на DFS
# 1) Откриване на цикъл в графика: DFS улеснява откриването на цикъл в графика, когато можем да се върнем към ръба.
# 2) Намиране на път: Както вече видяхме на илюстрацията DFS, като се имат предвид всеки два върха, можем да намерим пътя между тези два върха.
# 3) Минимум обхващащо дърво и най-кратък път: Ако изпълним техниката DFS на нетеглена графика, тя ни дава минималното обхващащо дърво и късата пътека.
# 4) Топологично сортиране: Топологичното сортиране се използва, когато трябва да планираме заданията. Имаме зависимости между различни работни места. Можем да използваме и топологично сортиране за разрешаване на зависимости между линкери, планиращи инструкции, сериализация на данни и др.
Обхождане първо по широчина
Техниката „Ширина на първо място” (BFS) използва опашка за съхраняване на възлите на графиката. За разлика от DFS техниката, в BFS ние обхождаме графиката по ширина. Това означава, че разумно прекосяваме нивото на графиката. Когато изследваме всички върхове или възли на едно ниво, ние преминаваме към следващото ниво.
По-долу е даден алгоритъм за техниката на обхождане първо в ширина .
Алгоритъм
Нека да видим алгоритъма за техниката BFS.
Дадена графика G, за която трябва да изпълним BFS техниката.
- Етап 1: Започнете с основния възел и го вмъкнете в опашката.
- Стъпка 2: Повторете стъпки 3 и 4 за всички възли в графиката.
- Стъпка 3: Премахнете основния възел от опашката и го добавете към списъка Посетени.
- Стъпка 4: Сега добавете всички съседни възли на кореновия възел към опашката и повторете стъпки от 2 до 4 за всеки възел. (END OF LOOP)
- Стъпка 6: ИЗХОД
Илюстрация на BFS
Нека илюстрираме BFS техниката, като използваме примерна графика, показана по-долу. Имайте предвид, че сме поддържали списък с име „Посетен“ и опашка. Използваме същата графика, която използвахме в примера за DFS за целите на яснотата.
Първо започваме с root, т.е. възел A и го добавяме към посетения списък. Всички съседни възли на възел A, т.е. B, C и D, се добавят към опашката.
След това премахваме възела B от опашката. Ние го добавяме към списъка Посетени и го маркираме като посетен. След това изследваме съседните възли на B в опашката (C вече е в опашката). Друг съседен възел A вече е посетен, така че ние го игнорираме.
След това премахваме възел C от опашката и го маркираме като посетен. Добавяме C към посетения списък и прилежащият му възел E се добавя към опашката.
След това изтриваме D от опашката и я маркираме като посетена. Съседният възел A на възел D вече е посетен, затова го игнорираме.
Така че сега само възелът E е на опашката. Маркираме го като посетен и го добавяме към посетения списък. Съседният възел на E е C, който вече е посетен. Затова го игнорирайте.
В този момент опашката е празна и посетеният списък има последователността, която получихме в резултат на обръщане на BFS. Последователността е A-> B-> C-> D-> E.
Прилагане на BFS
Следващата програма Java показва изпълнението на техниката BFS.
import java.io.*; import java.util.*; //undirected graph represented using adjacency list. class Graph { private int Vertices; // No. of vertices private LinkedList adj_list(); //Adjacency Lists // graph Constructor:number of vertices in graph are passed Graph(int v) { Vertices = v; adj_list = new LinkedList(v); for (int i=0; i Изход:
Приложения на BFS Traversal
# 1) Събиране на боклук: Един от алгоритмите, използвани от техниката за събиране на боклука за копиране на събирането на боклук, е „алгоритъм на Чейни“. Този алгоритъм използва техника за обхождане първо в ширина.
# 2) Излъчване в мрежи: Излъчването на пакети от една точка до друга в мрежа се извършва с помощта на BFS техниката.
# 3) GPS навигация: Можем да използваме техниката BFS, за да намерим съседни възли, докато навигираме с GPS.
# 4) Уебсайтове за социални мрежи: Техниката BFS се използва и в уебсайтовете за социални мрежи, за да се намери мрежата от хора, заобикалящи определен човек.
# 5) Най-кратък път и минимално обхващащо дърво в нетеглена графика: В непретеглената графика техниката BFS може да се използва за намиране на минимално обхващащо дърво и най-краткия път между възлите.
Java Graph Library
Java не прави задължително програмистите винаги да прилагат графиките в програмата. Java предоставя много готови библиотеки, които могат да се използват директно за използване на графики в програмата. Тези библиотеки разполагат с цялата функционалност на API на графиката, необходима за пълноценно използване на графиката и различните й функции.
По-долу е дадено кратко въведение в някои от графичните библиотеки в Java.
# 1) Google Гуава: Google Guava предоставя богата библиотека, която поддържа графики и алгоритми, включително прости графики, мрежи, графики за стойности и т.н.
# 2) Apache Commons: Apache Commons е проект на Apache, който предоставя компоненти на структурата на данните на Graph и API, които имат алгоритми, които работят с тази структура на данни на графиката. Тези компоненти са за многократна употреба.
# 3) JGraphT: JGraphT е една от широко използваните библиотеки на графики Java. Той предоставя функционалност на структурата на данните за графики, съдържаща проста графика, насочена графика, претеглена графика и т.н., както и алгоритми и API, които работят върху структурата на данните на графиката.
# 4) SourceForge JUNG: JUNG означава „Java Universal Network / Graph“ и е Java рамка. JUNG предоставя разширяващ се език за анализ, визуализация и моделиране на данните, които искаме да бъдат представени като графика.
JUNG също така предоставя различни алгоритми и рутинни процедури за декомпозиция, клъстериране, оптимизиране и др.
често задавани въпроси
В # 1) Какво представлява графика в Java?
Отговор: Графичната структура на данните съхранява главно свързани данни, например, мрежа от хора или мрежа от градове. Структурата на графичните данни обикновено се състои от възли или точки, наречени върхове. Всеки връх е свързан с друг връх с помощта на връзки, наречени ръбове.
Q # 2) Какви са видовете графики?
Отговор: Различни видове графики са изброени по-долу.
- Линейна графика: Линейна графика се използва за нанасяне на промените в дадено свойство спрямо времето.
- Стълбовидна графика: Стълбовидните графики сравняват числените стойности на обекти като населението в различни градове, процента на грамотност в страната и т.н.
Освен тези основни типове имаме и други видове като пиктограма, хистограма, графика на площ, разпръснат парцел и др.
В # 3) Какво е свързана графика?
Отговор: Свързана графика е графика, в която всеки връх е свързан с друг връх. Следователно в свързаната графика можем да стигнем до всеки връх от всеки друг връх.
Q # 4) Какви са приложенията на графиката?
как да направя .jar файлове отворени с
Отговор: Графиките се използват в различни приложения. Графиката може да се използва за представяне на сложна мрежа. Графиките се използват и в приложения за социални мрежи, за да обозначат мрежата от хора, както и за приложения като намиране на съседни хора или връзки.
Графиките се използват за обозначаване на потока от изчисления в компютърните науки.
Q # 5) Как съхранявате графика?
Отговор: Има три начина за съхраняване на графика в паметта:
# 1) Можем да съхраняваме възли или върхове като обекти и ръбове като указатели.
# две) Също така можем да съхраняваме графики като матрица на съседство, чиито редове и колони са еднакви с броя на върховете. Пресичането на всеки ред и колона означава наличие или отсъствие на ръб. В нетеглената графика присъствието на ръб се обозначава с 1, докато в претеглената графика то се заменя с тежестта на ръба.
# 3) Последният подход за съхраняване на графика е чрез използване на списък със съседство на ръбове между върховете или възлите на графика. Всеки възел или връх има своя списък за съседство.
Заключение
В този урок обсъдихме подробно графики в Java. Проучихме различните видове графики, внедряване на графики и техники за обхождане. Графиките могат да се използват за намиране на най-краткия път между възлите.
В предстоящите ни уроци ще продължим да изследваме графики, като обсъждаме няколко начина за намиране на най-краткия път.
=> Внимавайте тук за простите учебни серии за Java.
Препоръчително четене
- Урок за отражение на Java с примери
- Как да приложим алгоритъма на Dijkstra в Java
- Java SWING Урок: Контейнер, компоненти и обработка на събития
- Урок за JAVA за начинаещи: 100+ практически ръководства за Java видео
- TreeMap в Java - Урок с примери за TreeMap на Java
- Модификатори на достъп в Java - Урок с примери
- Java String с String Buffer и String Builder Tutorial
- Java String съдържа () Урок за метод с примери
