یکسری تعریف : (تعریف های زیر تعریف دقیق ریاضیاتی نیستن و بیشتر مفهومی هستن )
گراف :ساختاری هست که برای نمایش رابطه بین اشیا مختلف استفاده میشه .
راس : به اشیا موجود داخل گراف راس میگیم
یال : به رابطه بین ۲ راس یال گفته میشه.
مسیر : به محوعه ای از یال ها که ۲ راس را به هم وصل می کنه مسیر میگیم .
گراف همبند : گرافی که از هر راس مسیری به راس های دیگه داشته باشه .
دور: اگر یک راس از گراف مسیر غیر تهی به خودش داشته باشه به این مسیردور می گیم .
درخت : به گراف همبندی که دور نداشته باشه درخت میگیم .
مثال :
شکل بالا یک گراف هست
به هر کدوم از دایره های شکل بالا که این جا نشون دهنده یک کلمه خاص هستن راس گفته میشه .
به فلش ها که نشون دهنده رابطه بین راس ها هستند یال میگیم (این جا رابطه اینه که چه حرفی اضافه یا کم بشه تا کلمه متصل بوجود بیاد)
گراف بالا چون بین هر ۲ راس دلخواه مسیر وجود داره همبند هست .
و چون این گراف همبند هست و دور نداره درخت حساب میشه .
درخت یک ساختار برای ذخیره اطلاعات هستش و کاربرد های خیلی زیادی داره .
چند نمونه از کاربرد ها :
-
۱ـ ساختارهایی که ما داخلشون هم به جست و جو و اضافه کردن و حذف عنصر بصورت سریع نیاز داریم اکثرا با درخت نوشته شدن مثلا red and black tree یا binary search tree یا درخت هافمن یا ساختار هایی مثل Trie و...
-
مثلا سیستم ورود و عضویت یک بازی آنلاین پر طرفدار رو در نظر بگیرید شاید مثلا هر ثانیه قرار باشه از بین چند صد تا هزار تا اکانت موجود چند هزار تا جست و جو انجام بشه یا هر ثانیه چند تا اکانت جدید به اکانت های موجود اضافه بشه خب طبیعتا اگر عملیات جست و جویی که انجام میدیم به اندازه کافی سریع نباشه سیستم عملا غیر قابل استفاده میشه ! این جور جاها مثلا یکی از ساختار هایی که برای ذخیره و جست و جوی اطلاعات استفاده میشه binary search tree یا red and black tree هستش .
-
از red and black tree برای نوشتن std::map داخل c++ استفاده شده .
-
از Trie برای پیدا کردن edit distance دو تا کلمه استفاده میشه (یعنی تعداد تغییرات لارم برای این که از یک کلمه به کلمه دیگه برسیم مثلا مرد _ مردی فاصله بینشون ۱ هست ) که برای تصحیح خودکار متون کاربرد داره . (شکل بالا هم مربوط به همین ساختار هست )
-
یا مثلادر پردازش تصویر از ساختاری مثل kdtree برای جست و جو در فضا های چند بعدی استفاده میشه.
-
از tree برای نوشتن الگوریتم های تکاملی هم استفاده میشه(http://en.wikipedia.org/wiki/Gene_expression_programming)
-
decision tree ها هم که کاربرد زیادی در AI دارند از همین ساختار استفاده می کنند.
و خیلی چیز های دیگه ....
در مورد پیاده سازی و مطالب دیگه هم بعدا داخل همین پست توضیح میدم .