پیاده سازی گراف با لیست پیوندی

[AliReza Vafakhah]

سلام دوستان

قبلا چنین سوالی در بخش دلفی پرسیدم و تا حدود زیادی اطلاعات کسب کردم اما هنوز تو یه مبحث موندم.

قبلا توسط لیست پیوندی دو طرفه راحت یه درخت رو پیاده سازی می کردم اما الآن پیاده سازی یه گراف توسط لیست پیوندی یه خرده برام گنگه. چه طوری ؟ آخه یه گراف که حلقه (دور) هم داره ، پس با لیست پیوندی چه طوری پیاده سازی بشه.

جستجوهای زیادی هم کردم ولی نتیجه نگرفتم ، درضمن هدف از پیادسازی گراف اعمال الگوریتم های BFS و DFS در گراف است.

دوستان من فقط نیاز به راهنمایی دارم تا بتونم خودم پروژم رو بنویسم. لطفا فقط راهنمایی کنید که چگونه ابتدا گراف رو پیاده سازی کنم؟

تشکر

[مصطفی ساتکی]

سلام
شما برای پیاده سازی یک رکورد برای vertices تعریف کنید و یک رکورد برای edge تعریف کنید وقتی کاربر هر vertex رو اضافه کی کنید شما لیست پیوندی یک طرفه در نظر بگیر و آن vertex ها را بهش اضافه کن. حالا می مونه edges که باز هم زمانی که کاربر یک edge اضافه می کنه شما یک لیست پیوندی دیگه داشته باش که هر edge رو به لیست پیوندی اضافه کنی.
یک رکورد vertex Info بساز که شامل یک اشاره گر و یک فلگ هستش(برای مشخص ساختن اینکه نود جاری به رو کدام طرف vertex قرار داره) حالا یک لیست پیوندی از این vertex info هم در ساختار رکورد vertices داشته باش تا از هر vertex بتونی مجموعه edge ها را پردازش کنی یعنی با این پیاده سازی می تونی کل گراف را پیمایش کنی اگر دوست داشته باشی مثلاً فلگ پیمایش هم می تونی هم به vertices و هم به edge اضافه کنی.

در ضمن وب پر از منابع هستش مخصوصاً برای گراف که جز مباحث قدیمی هستش مثلا اینجا (http://www.mathcove.net/petersen/lessons/get-lesson?les=2)