دانلود سورس تشخیص دور گراف در سی پلاس پلاس

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

تشخیص دور در گراف

پیدا کردن دور یا تشخیص وجود آن در گراف بدون جهت و گراف جهت‌دار، به وسیله جستجوی عمق اول امکان‌پذیر است. یال برگشت (به انگلیسی: Back Edge) به یالی مانند e گفته می شود که از رأس u – که در مرحله کنونی اجرای الگوریتم در آن مشغول جستجو هستیم – به رأسی مانند v باشد، در حالی که v یکی از اجداد u است. حال اگر جستجوی عمق اول در حین اجرا به یک یال برگشت، برخورد، نشان‌دهنده این است که گراف شامل حداقل یک دور می باشد. در صورتی هم که هیچ یال برگشتی وجود نداشته باشد، گراف فاقد دور است(ویکیپدیا).

یک نمونه خروجی برنامه به صورت زیر می‌باشد:

Graph G1 contains cycle
Graph G2 doesn't contain cycle

قسمتی از کد برنامه به صورت زیر می‌باشد:

// A recursive function that uses visited[] and parent to detect
// cycle in subgraph reachable from vertex v.
bool Graph::isCyclicUtil(int v, bool visited[], int parent) {
// Mark the current node as visited
visited[v] = true;
// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i) {
// If an adjacent is not visited, then recur for that adjacent
if (!visited[*i]) {
if (isCyclicUtil(*i, visited, v))
return true;
}
// If an adjacent is visited and not parent of current vertex,
// then there is a cycle.
else if (*i != parent)
return true;
}
return false;
}
// Returns true if the graph contains a cycle, else false.
bool Graph::isCyclic() {
// Mark all the vertices as not visited and not part of recursion
// stack
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
// Call the recursive helper function to detect cycle in different
// DFS trees
for (int u = 0; u < V; u++)
if (!visited[u]) // Don't recur for u if it is already visited
if (isCyclicUtil(u, visited, -1))
return true;
return false;
}

گراف ورودی برنامه به صورت زیر می‌باشد:

دانلود سورس تشخیص دور گراف در سی پلاس پلاس

دانلود

زبان برنامه‌نویسی: سی پلاس پلاس

نوع فایل: Rar

حجم فایل: 2 کیلوبایت

Download “دانلود سورس کد تشخیص دور گراف در سی پلاس پلاس” Detect-cycle-in-undirected-graph-Cpp-Code-CodeGate-.rar – 59 بار دانلود شده است – 1 کیلوبایت

پسورد: www.codegate.ir