چه جوری می شه یه گراف رو با لیست پیوندی نشون داد؟ [بایگانی]

MOHSEN8000

چهارشنبه 10 بهمن 1386, 19:56 عصر

من چند تا مشکل دارم برای نمایش گراف و گرفتن اون به شکل link list. هر چی هم برنامشو خودم می نویسم به مشکل بر می خورم. چون هر راس به تعداد درجه اون داخل لیست ظاهر می شه. یعنی باید هر کپی تهیه کنم از هر راس؟!!! کسی می تونه مشکلم رو برطرف کنه؟ ضمنا براس search کردن داخل لیست هم چه طور می شه از هر گره به گره بعدی بریم؟ با تشکر.

MRHagh

سه شنبه 16 بهمن 1386, 21:33 عصر

میتونی خیلی راحت از روش ماتریس مجاورت استفاده کنی . تو این روش اول یک آرایه از نوع اشاره گر به لیست ، که عناصری به تعداد رئوس گراف داره ، تعریف میشه . در مرحله بعد هر عنصر از این آرایه به لیستی اشاره خواهد کرد که هر گره از آن ، حاوی شماره راسی هست که با راس متناظر با شماره آن عنصر از آرایه مجاور است .
در این روش درست مجموع تعداد گره ها در کل لیست ها، دو برابر یالها خواهد شد و براحتی میشه سایر عملیات های دیگر را روی گراف پیاده سازی کرد . مثل یافتن مسیر همیلتنی یا چیز های دیگه .

MOHSEN8000

پنج شنبه 18 بهمن 1386, 09:57 صبح

میتونی خیلی راحت از روش ماتریس مجاورت استفاده کنی . تو این روش اول یک آرایه از نوع اشاره گر به لیست ، که عناصری به تعداد رئوس گراف داره ، تعریف میشه . در مرحله بعد هر عنصر از این آرایه به لیستی اشاره خواهد کرد که هر گره از آن ، حاوی شماره راسی هست که با راس متناظر با شماره آن عنصر از آرایه مجاور است .
در این روش درست مجموع تعداد گره ها در کل لیست ها، دو برابر یالها خواهد شد و براحتی میشه سایر عملیات های دیگر را روی گراف پیاده سازی کرد . مثل یافتن مسیر همیلتنی یا چیز های دیگه .

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