طراحی نرم افزار اندروید
طراحی اپلیکیشن موبایل
Graph چیست و این دیتا استراکچر چه کاربردهایی دارا است؟
به طور کلی، دیتا استراکچرها یکسری فرمت خاص به منظور سازماندهی و ذخیرهسازی دادهها هستند که هر یک در راستای نگهداری دادهها به منظور انجام پردازشهای مد نظر روی دیتای مربوطه طراحی شدهاند تا بتوان با روشهای مناسب و از آن مهمتر بهینه به دیتای مورد نظر دسترسی پیدا کرده و عملیات مربوطه را با بهکارگیری الگوریتمهای مختلف روی آنها انجام داد. دیتا استراکچرها انواع مختلفی دارند که از آن جمله میتوان به آرایه، گراف، پُشته و مواردی از این دست اشاره کرد که در ادامۀ این مقاله قصد داریم تا با دیتا استراکچر گراف آشنا شده و کاربردهای آن به منظور نگهداری دیتا را مورد بررسی قرار دهیم.
آشنایی با دیتا استراکچر گراف
Graph دیتا استراکچری است که به منظور مدلسازی مجموعهای از اشیاء و ارتباطات مابین آنها مورد استفاده قرار میگیرد و بر اساس نماد ریاضیاتیِ (G(V, E نمایش داده میشود که در آن V اشاره بر اصطلاحاً Vertices یا مجموعۀ رئوس گراف دارد و E سرواژۀ عبارت Edges بوده و مجموعه یالهای گراف مد نظر را شامل میشود. به عنوان یک مثال کاربردی از گرافها میتوان مدلسازی روابط مابین افراد در #شبکههای اجتماعی را نام برد که در آن تکتک افراد به منزلۀ رئوس گراف در نظر گرفته شده و ارتباطات مابین ایشان نیز توسط خطوطی نمایش داده میشوند که دو یا چند رأس از گراف مد نظر را به هم وصل کرده و تحت عنوان یال شناخته میشوند.
در واقع، وجود ارتباط مابین برخی از رئوس گرافِ شبکۀ اجتماعی بدین معنی است که افراد متناظر این رئوس یکدیگر را میشناسند و بالعکس؛ به عبارت دیگر، اگر یالی مابین رئوس گراف وجود نداشته باشد بدین معنی است که افراد مذکور با یکدیگر آشنایی ندارند که برای درک بهتر این موضوع، تصویر فوق را مد نظر قرار میدهیم.
این تصویر مثالی بسیار کوچک از گراف یک شبکۀ اجتماعی است که در آن هر یک از افراد با رئوس گراف و ارتباطات مابین ایشان نیز توسط یالهایی مدلسازی شده است که این یالها برخی از رئوس گراف را به هم متصل میکنند به طوری که ارتباط مابین دو رأس فرضی از گراف مد نظر تحت عناوین u و v را با نماد (u, v) نشان میدهیم که به منزلۀ وجود یالی از رأس u به v میباشد. به طور مثال، در گراف فوق یالی بین امیر و جواد وجود دارد که آن را به صورت (Amir, Javad) نشان میدهیم. به علاوه اینکه ارتباطات مابین رئوس شبکۀ فوق دوسویه بوده و بدین معنی است که چنانچه فردی همچون امیر با فرد دیگری مانند جواد ارتباط داشته باشد، امیر او را میشناسد و بدین ترتیب جواد نیز با امیر آشنایی دارد و به تعبیری میتوان گفت که این گراف بیجهت است.
به طور کلی، گرافها را میتوان در دو دستۀ به اصطلاح Directed (جهتدار) و Undirected (بیجهت) تقسیمبندی کرد که در گرافهای بیجهت ارتباطات مابین رئوس گراف دوسویه میباشد و در مورد مثال فوق نیز همانطور که پیشتر اشاره کردیم، ارتباطات از نوع بیجهت بوده و میتوان گفت که گراف مد نظر یک گراف بیجهت میباشد؛ بنابراین یال (u, v) مابین دو رأس u و v از گراف بیجهت را میتوان با رابطۀ (v, u) نیز نمایش داد به علاوه اینکه در گرافهای بیجهت دو رأسی که با یکدیگر ارتباط دارند و توسط یالی به هم متصل شدهاند، اصطلاحاً Adjacent یا رئوس مجاور و همسایۀ یکدیگر به شمار میروند. همچنین تعداد یالهای متصل به یک رأس در گراف بیجهت اصطلاحاً Degree یا درجۀ آن رأس نامیده میشود (در ادامۀ این مقاله با گرافهای جهتدار نیز آشنا خواهیم شد که در آنها ارتباطات مابین رئوس گراف لزوماً دوسویه نمیباشند.)
اکنون مجدداً مثال شبکۀ اجتماعی فوق را در نظر میگیریم. همانطور که میبینید، هیچ یال مستقیمی مابین رئوسی به نامهای آیدا و فرانک وجود ندارد بدین معنی که این دو فرد یکدیگر را نمیشناسند. حال فرض کنید آیدا قصد دارد تا با فرانک آشنا شود که چنین مواردی در دنیای واقعی نیز بسیار اتفاق میافتد به طوری که بسیاری از ما با برخی افراد از طریق دوستان مشترک خود آشنا میشویم؛ به عبارت دیگر، در شبکۀ اجتماعی فوق آیدا و فرانک میتوانند از طریق دوستان مشترک خود و آشنایی فرانک با المیرا و المیرا با بنیامین با یکدیگر آشنا شوند.
جمعبندی
در این مقاله به بررسی ديتا استراكچر گراف پرداخته و برخی از روشهای پرکاربرد به منظور نگهداری و ذخیرهسازی آن را تشریح کردیم و همچنین چند مثال از کاربردهای این دیتا استراکچر در دنیای واقعی را بیان کردیم که از آن جمله میتوان به مسئلۀ یافتن کوتاهترین مسیر مابین دو رأس گراف اشاره کرد.
طراحی اپلیکیشن اندروید | طراحی وب سایت | شرکت ایده پردازان پاراکس |
