Alqoritm

DFS alqoritminin real proyekt üzərində tətbiqi

Birbaşa mətləbə keçəcəm. Deməli, iş yoldaşıma proyektdə belə bir şey lazım oldu; web səhifəsi var idi, həmin  web səhifənin menusunu admin panelində aydın və anlaşıqlı şəkildə göstərmək lazım idi ki, yeni menu/alt-menu əlavə etmək, mövcud menunu silmək yaxud menularda dəyişikliklər etmək daha rahat olsun. Və bu məsələ üçün optimal həll variantı fikirləşmək lazım idi.

Bu məsələni, həmin web səhifə əvəzinə öz blogumdan nümunə verməklə göstərəcəm və kodlaşdırılmasına da bu nümunə üzərindən davam edəcəyik.

Deməli mənim blogumun menusu təxminən belədir:

Blog Menu

Və indi bizə lazımdır ki, menu admin paneldə aşağıdakı formada görünsün:

Menu ilə bağlı məlumatlar verilənlər bazasında aşağıdakı formada saxlanılır:

id parent_id name
0 -1 MENU
1 0 Home
2 0 Certification Exam
3 0 Sample questions
4 0 My Books
5 0 Articles
6 0 News
7 0 Mix
8 0 Feedbacks
9 0 About
10 2 Exam preparation: step by step
11 2 Exam Topics
12 2 Exam Experience
13 3 Oracle
14 13 1Z0-803 (OCA 7)
15 13 1Z0-804 (OCP 7)
16 13 1Z0-805 (Upgrade to Java SE 7)
17 13 1Z0-808 (OCA 8)
18 13 1Z0-809 (OCP 8)
19 13 1Z0-810 (Upgrade SE 7 to 8 OCP)
20 13 1Z0-813 (Upgrade to SE 8 OCP)
21 4 My Certification Notes

Menu və alt-menuların sayı dəyişkəndir, hər vaxt artıb-azala bilər. Hər yeni alt-menu əlavə edildikcə, parent_id kimi həmin alt-menunun aid olduğu menunun id dəyəri əlavə edilir. id dəyəri isə hər menu üçün unikaldır, təkrarlanmır. Ona görə də dinamik bir həll üsulu tapmaq lazım idi. Biz buna DFS alqoritmini tətbiq etdik (“Preorder Tree Walk” versiyası da ağlıma gəldi, amma onu araşdırmadım, kimin başqa maraqlı həll variantı olsa qeyd edə bilər). DFS alqoritmi ilə bağlı detallara çox getməyəcəm, sadəcə kod üzərində tətbiqini göstərməyə çalışacam. Qısaca DFS (Depth-First-Search) alqoritmi qraflar üzərində ən çox istifadə edilən axtarış alqoritmlərindən biridir:

DFS

Biz bu alqoritm vasitəsilə menunun alt menularını axtaracağıq.

Sual yarana bilər ki, bəs bu menunun qrafla nə əlaqəsi var yaxud necə əlaqələndirəcəyik? Biz əgər məlumat bazasında mövcud olan menumuzu qraf üzərində təsvir etsək aşağıdakı mənzərə alınacaq:

Blog Menu Graph

Amma problemi qraf şəklinə salıb həll etmək istəyiriksə, dəyərləri saxlamaq üçün qraflara uyğun data strukturlardan istifadə etməliyik. Adətən iki cür data struktur istifadə edilir:

  • Adjacency Matrix
  • Adjacency List

Biz “adjacency list” istifadə edəcəyik, amma bir az daha optimallaşdırılmış formada. Adjacency list üçün adətən massiv istifadə edilir, massivin elementləri LinkedList`lərdən ibarət olur. Amma bizdə məlumat daha dinamikdir, məlumat bazasında id sütununun dəyəri ardıcıl artmaya da bilər yaxud hər hansı id silindikdə fərqli mənzərə yarana bilər. Yəni, qısaca desək id`nin dəyəri menunun sayından bir neçə dəfə böyük bir ədəd də ola bilər. Bu baxımdan massiv istifadə etmək optimal deyil, əvəzində Map`lərdən istifadə edəcəyik. Kod üzərindən baxdıqda daha aydın olacaq.

Proyektin strukturu:

project structure - display website menu

 

Main.java

 

DBConnection.java

 

Submenu.java

 

create.sql

 

pom.xml

 

Proyektin github linki:

https://github.com/mmushfiq/display-website-menu-using-dfs-algorithm

About the author

Mushfiq Mammadov

Leave a Comment

 

This site uses Akismet to reduce spam. Learn how your comment data is processed.