ساختمان داده گراف Graph

گراف، مجموعه ای از نقاط است که بعضی از آن نقاط توسط خطوطی به هم وصل میشوند. هر نقطه را یک رأس یا گره، و هر اتصال را یک یال می نامیم. نقشه راههای استان را میتوان یک گراف در نظر گرفت، بطوریکه نقاط برخورد جاده بعنوان راس و خود جاده ها بعنوان یال محسوب میشوند.

ساختمان داده گراف Graph

امروزه با گسترش علم کامپیوتر، مطالعه شبکه ها کانون توجه است. مخصوصا گسترش اینترنت توجه به این موضوع را اهمیت بیشتری بخشیده است. شبکه ها را میتوان با استفاده از گراف ها مدلسازی کرد.

تعریف گراف

گراف، مجموعه ای از نقاط است که بعضی از آن نقاط توسط خطوطی به هم وصل میشوند. هر نقطه را یک رأس یا گره، و هر اتصال را یک یال می نامیم. نقشه ی راهای یک استان را در نظربگیرید. در ین نقشه، هر شهر از طریق نوعی جاده به شهر دیگر متصل میشود و ممکن است از شهری به شهر دیگر، چند جاده وجود داشته باشد. نقشه راههای استان را میتوان یک گراف در نظر گرفت، بطوریکه نقاط برخورد جاده بعنوان راس و خود جاده ها بعنوان یال محسوب میشوند.

انواع گراف ها

تمام گرافهایی که برای نمایش شبکه ها مورد استفاده قرار میگیرند، یکسان نیستند. گراف بطور کلی به دودسته تقسیم میشوند:

• گرافهای جهتدار

• گرافهای بدون جهت

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

گراف بدون جهت گرافی است که در آن یالی بین v₁ و v₂ فاقد جهت است. چنین یالی را بصورت (v₁, v₂) نمایش میدهیم که زوج مرتب نیست. یعنی یال (v₁, v₂) همان یال (v₂, v₁) است.

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

اصطلاحات مربوط به ساختمان داده گراف

• گره های همجوار : اگر در گراف از گره x به گره y یالی وجود داشته باشد، آن دو گره همجوارند.

• حلقه : اگر یالی وجود داشته باشد که گره های شروع و پایان آن یکسان باشد، حلقه بوجود می آید.

• مولفه : هر گراف میتواند از چند تکه تشکیل شده باشد که هر تکه از آنرا یک مولفه گویند.

• مسیر : دنباله ای از گره هاست که در آن هر گره، همجوار گره دیگری است. طول مسیر برابر با تعداد یالهای موجود در آن مسیر است.

• چرخه : مسیری با طول بیش از یک است که از یک گره شروع و به همان گره ختم میشود.

• یالهای موازی : اگر بیش از یک یال بین دو گره وجود داشته باشد، آنها را یالهای موازی گویند.

• درجه گره : در گراف بدون جهت، درجه ی گره ای مثل x برابر با تعداد یالهایی است که در آن گره تلاقی میکنند. اگر گراف جهتدار باشد، درجه ورودی گره ای مثل x برابر با تعدا یالهایی است که به آن وارد میشوند و درجه خروجی گرهی مثل x برابر با تعدا یالهایی است که از آن خارج میشوند.

• گراف متصل : در گراف، دو گره x و y درصورتی متصل هستند که مسیری از یکی از گره ها به دیگری وجود داشته باشد. گراف بدون جهت در صورتی متصل است که به ازای هر گره x و y در آن مسیری وجود داشته باشد. گراف جهتدار در صورتی متصل است که به ازای هر دو گره x و y در آن مسیری از x به y و از y به x وجود داشته باشد.

پیاده سازی یا نمایش گراف

گراف را به شکل های مختلفی میتوان نمایش داد که متداولترین آنها به شرح زیر می باشد:

پیاده سازی گراف با مجموعه ها
پیاده سازی گراف با ماتریس های همجواری
پیاده سازی گراف با لیست همجواری
پیاده سازی گراف با لیست یال ها

هر کدام از این روشهای نمایش، مزایا و معایب خاص خودشان را دارند. در نمایش گراف بصورت مجموعه، عملیات های مربوط به گراف، دشوار و نا کارآمد خواهد بود. علاوه براین، چون در مجموعه، عناصر نمیتوانند تکراری باشند، نمایش یالهای موازی در این روش غیر ممکن است. بنابراین نمایشش گراف با مجموعه فقط از نظر تئوری جذاب است.

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