گراف در سی پلاس پلاس (Graph In Cpp)

در این قسمت تیم کدگیت را با آموزش پیاده سازی گراف در سی پلاس پلاس همراهی کنید. همانند آموزش‌‌های گذشته ابتدا گراف را معرفی کرده و سپس به پیاده سازی آن در زبان برنامه‌نویسی سی پلاس پلاس می‌پردازیم. پیشنهاد می‌کنیم قبل از مطالعه این جلسه، آموزش‌های زیر را بررسی کنید:

1. شی گرایی در سی پلاس پلاس
2. Constructor در سی پلاس پلاس
3. توابع در سی پلاس پلاس

گراف

شکل زیر یک گراف ساده هست که شامل 6 یال و 5 راس است.

یک گراف شامل یک مجموعه ی از رئوس(گره) و یک مجموعه از یال هاست . در تصویر فوق راس‌های ما با اعداد 1 و 2 و 3 و 4 و 5 نمایش داده شده است. یال‌ها رئوس را به یکدیگر متصل می‌کند.

نمایش گراف

در سی پلاس پلاس برای پیاده سازی گراف روش هایی مثل آرایه توصیه می‌شود. مثلا یک آرایه دو بعدی بسازیم که تعداد سطر و ستون آن برابر با راس‌ها باشد. حال اگر راس 1 به راس 5 یالی داشته باشد خانه 1و5 (در آرایه میشود 0و4) را 1 قرار می‌دهیم بدین معنی که این دو خانه به هم یالی دارند.

روش بالا را ماتریس مجاورت میگویند. این روش توصیه  نمیشود به دلیل فضای زیادی که از حافظه میگیرد.روش دوم استفاده لیستی است که فقط همسایه های یک راس در آن نگه داشته می شود(لیست همسایگی).همانند شکل زیر:

در این قسمت ما به پیاده سازی روش دوم میپردازیم. ایده پیاده سازی لیست همسایگی در سی پلاس پلاس به شکل زیر است:

در سی پلاس پلاس ما از Vector برای پیاده سازی ماتریس مجاورت استفاده می‌کنیم. Vector مانند آرایه‌ای پویا عمل کرده و طول آن  مانند آرایه ثابت نیست ما از این ویژگی برای ساخت لیست همسایگی استفاده می‌کنیم. بدین صورت که ما یک Vector از Vector داریم!!! Vector از Vector را مانند آرایه ای دو بعدی فرض کنید که طول آن ثابت نیست و در هر قدم می‌توان طول آن (از دو بعد) تغییر داد. Vector اول (یا ابعاد اول) برای تعداد راس بوده و Vector دوم برای تعداد یال‌ها می‌باشد. (اگر کمی گیج کننده است مشکلی نیس داخل کد بهتر متوجه می شوید!!!)

پیاده سازی گراف در سی پلاس پلاس

حال به پیاده سازی گراف در سی پلاس پلاس میپردازیم. ابتدا یک کلاس به نام گراف(Graph) میسازیم. در این کلاس دو فیلد به نام

• adj( لیست همسایگی)
• V (تعداد راس‌ها)

در constructor کلاس گراف تعداد راس ها را میگیریم و لیست همسایگی را میسازیم به صورت زیر:

Graph::Graph(int v) {
	this->V = v;
	for (int i = 00; i < v; i++) {
		vector<int> v1;
		this->adj.push_back(v1);
	}
}

حال تابعی به نام addEdge مینویسیم. کار این تابع این است که دو راسی که همسایه هستند را به عنوان ورودی بگیرد و در لیست همسایگی قرار دهد.

void Graph::addEdge(int u, int v) {
	this->adj.at(u).push_back(v);
	this->adj.at(v).push_back(u);
}

 در قدم بعدی هم متدی برای نمایش دادن گراف مینویسیم.

void Graph::printGraph() {
	for (int v = 00; v < this->V; ++v) {
		cout << v;
		for (auto x : this->adj.at(v))
			cout << "-> " << x;
		printf("\n");
	}
}

در آخر برای برنامه main مینویسیم.

int main() {
    int V = 5;
    Graph g(V);
    g.addEdge(00, 1);
    g.addEdge(00, 4);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 3);
    g.addEdge(3, 4);
    g.printGraph();
	return 00;
}

پسورد: www.codegate.ir