در این قسمت تیم کدگیت را با آموزش پیاده سازی گراف در سی شارپ همراهی کنید. شکل زیر یک گراف ساده هست که شامل 6 یال و 5 راس است.
در سی شارپ برای پیاده سازی گراف روش هایی مثل آرایه توصیه میشود. مثلا یک آرایه دو بعدی بسازیم که تعداد سطر و ستون آن برابر راس باشد. حال اگر راس 1 به راس 5 یالی داشته باشد خانه 1و5 (در آرایه میشود 0و4) را 1 میگذاریم بدین معنی که این دو خانه به هم یالی دارند.
روش بالا را ماتریس مجاورت میگویند. این روش توصیه نمیشود به دلیل فضای زیادی که از حافظه میگیرد.روش دوم استفاده لیستی است که فقط همسایه های یک راس در آن نگه داشته می شود(لیست همسایگی).همانند شکل زیر:
در این قسمت ما به پیاده سازی روش دوم میپردازیم.پیاده سازی روش اول نیز در آموزشهای بعدی گفته خواهد شد.
ایده پیاده سازی لیست همسایگی در سی شارپ به شکل زیر است
بدین صورت که ما یک آرایه از arraylist داریم!!! طول آرایه برابر با تعداد راسها است. به عنوان مثال اگر بخواهیم بگوییم راس های 1 و 2 یک یال متصل به هم دارند به خانه 1 آرایه رجوع میکنیم و به لیست آن عدد 2 اضافه و به خانه 2 آرایه رجوع و به لیست آن خانه عدد یک را اضافه میکنیم.(اگر کمی گیج کننده است مشکلی نیس داخل کد بهتر متوجه می شوید!!!)
گراف در سی شارپ
حال به پیاده سازی گراف در سی شارپ میپردازیم. ابتدا یک کلاس به نام گراف(Graph) میسازیم. در این کلاس سه فیلد میسازیم:
- V_counter(شمارنده تعداد یال های گراف)
- E(تعداد راسهای گراف)
- adjance_list(لیست همسایگی)
در constructor کلاس گراف تعداد راس ها را میگیریم و لیست همسایگی را میسازیم به صورت زیر:
public Graph (int E)
{
this.E = E;
adjance_list = new ArrayList[E + 1];
}
دلیل ساختن آرایه به طول E+1 آن است که آرایه از صفر شروع میشود.
حال متدی به نام add_vertex مینویسیم. کار این متد این است که دو خانه ای که همسایه هستند را به عنوان ورودی بگیرد و در لیست همسایگی قرار دهد.
public void add_vertex (int first_edge, int second_edge)
{
if (first_edge > E || first_edge < 0 || second_edge > E
|| second_edge < 0) {
return;
}
V_counter++;
if (adjance_list [first_edge] != null) {
adjance_list [first_edge].Add (second_edge);
} else {
adjance_list [first_edge] = new ArrayList ();
adjance_list [first_edge].Add (second_edge);
}
if (adjance_list [second_edge] != null) {
adjance_list [second_edge].Add (first_edge);
} else {
adjance_list [second_edge] = new ArrayList ();
adjance_list [second_edge].Add (first_edge);
}
}
در آخر هم متدی برای نمایش دادن گراف مینویسیم.
public void printGraph ()
{
for (int i = 0; i < adjance_list.Length; i++) {
if (adjance_list [i] != null) {
foreach (Object o in adjance_list[i]) {
int temp = (int)o;
Console.WriteLine (i + " --> " + temp);
}
}
}
}
در آخر برای برنامه main مینویسیم.
public static void Main (string[] args)
{
Graph g = new Graph (5);
g.add_vertex (1, 5);
g.add_vertex (1, 4);
g.add_vertex (1, 2);
g.add_vertex (2, 3);
g.add_vertex (3, 5);
g.add_vertex (4, 5);
g.printGraph ();
Console.ReadKey ();
}
