فرادرس
یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
۵۷۳ بازدید
آخرین به‌روزرسانی:
۱۰ تیر ۱۴۰۲
زمان مطالعه:
۱۳ دقیقه
«مسیر همیلتونی» (Hamiltonian Path) در یک گراف غیر جهت‌دار، مسیری است که در آن هر «راس» (Vertex) دقیقا یک‌بار مشاهده می‌شود. یک «دور همیلتونی» یا «مدار همیلتونی» (Hamiltonian Cycle | Hamiltonian Circuit)، یک مسیر همیلتونی است که در آن از آخرین راس به اولین راس یک «یال» (Edge) وجود دارد. در ادامه، روشی جهت بررسی اینکه آیا در یک گراف داده شده، دور همیلتونی وجود دارد یا خیر بررسی می‌شود. همچنین، در صورت وجود دور، مسیر آن را چاپ می‌کند. در واقع، با استفاده از یک روش ساده و یک روش «پس‌گرد» (Backtracking)، بررسی می‌شود که آیا در یک گراف دور همیلتونی وجود دارد یا خیر و در صورت وجود، مسیر در خروجی چاپ می‌شود. ورودی و خروجی تابع لازم برای این کار به صورت زیر هستند.
یافتن دور همیلتونی در گراف
برای یافتن دور همیلتونی در گراف، به طور کلی به صورت زیر عمل می‌شود.
ورودی:
یک آرایه دوبُعدی [graph[V][V که در آن V تعداد راس‌ها در گراف و [graph[V][V «ماتریس همسایگی» (Adjacency Matrix) گراف است. مقدار [graph[i][j در صورت وجود یک یال مستقیم از راس i به راس j برابر با یک و در غیر این صورت، [graph[i][j برابر با صفر است.
خروجی:
یک آرایه [path[V باید حاوی یک مسیر همیلتونی باشد. [path[i باید راس i در مسیر همیلتونی را نمایش دهد. همچنین، کد باید مقدار false را در صورت عدم وجود دور همیلتونی در گراف، بازگرداند.
برای مثال، دور همیلتونی در گراف زیر به صورت {۰ ،۳ ،۴ ،۲ ،۱ ، ۰} است.
(0)--(1)--(2) | / \ | | / \ | | / \ | (3)-------(4)
گراف زیر حاوی هیچ دور همیلتونی نیست.
(0)--(1)--(2) | / \ | | / \ | | / \ | (3) (4)
الگوریتم ساده (Naive Algorithm)
الگوریتم ساده‌ای که در زیر ارائه شده، همه پیکربندی‌های ممکن برای راس‌ها را ارائه می‌کند و پیکربندی که محدودیت های داده شده را ارضا می‌کند، باز می‌گرداند. به تعداد !n، پیکربندی ممکن وجود دارد.
while there are untried conflagrations
{
generate the next configuration
if ( there are edges between two consecutive vertices of this
configuration and there is an edge from the last vertex to
the first ).
{
print this configuration;
break;
}
}
یافتن دور همیلتونی با الگوریتم پس‌گرد (Backtracking Algorithm)
این الگوریتم یک آرایه مسیر خالی می‌سازد و راس ۰ را به آن اضافه می‌کند.
در ادامه، دیگر راس‌ها را با آغاز از راس ۱ به آرایه اضافه می‌کند؛ اما پیش از اضافه کردن یک راس، بررسی می‌کند که آیا با راس پیشین اضافه شده مجاور است یا خیر و همچنین، بررسی می‌کند که راس، پیش از این به آرایه اضافه نشده باشد. اگر چنین راسی پیدا شود، یال به عنوان بخشی از راهکار اضافه می‌شود. اگر راس پیدا نشود، مقدار false بازگردانده می‌شود.
پیاده‌سازی الگوریتم پس‌گرد برای مساله یافتن دور همیلتونی در گراف
در ادامه، پیاده‌سازی الگوریتم پس‌گرد برای مساله یافتن دور همیلتونی در گراف در زبان‌های برنامهنویسی گوناگون ارائه شده است.
++C
/* C++ program for solution of Hamiltonian
Cycle problem using backtracking */
#include <bits/stdc++.h>
using namespace std;
// Number of vertices in the graph
#define V 5
void printSolution(int path[]);
/* A utility function to check if
the vertex v can be added at index 'pos'
in the Hamiltonian Cycle constructed
so far (stored in 'path[]') */
bool isSafe(int v, bool graph[V][V],
int path[], int pos)
{
/* Check if this vertex is an adjacent
vertex of the previously added vertex. */
if (graph [path[pos - 1]][ v ] == 0)
return false;
/* Check if the vertex has already been included.
This step can be optimized by creating
an array of size V */
for (int i = 0; i < pos; i++)
if (path[i] == v)
return false;
return true;
}
/* A recursive utility function
to solve hamiltonian cycle problem */
bool hamCycleUtil(bool graph[V][V],
int path[], int pos)
{
/* base case: If all vertices are
included in Hamiltonian Cycle */
if (pos == V)
{
// And if there is an edge from the
// last included vertex to the first vertex
if (graph[path[pos - 1]][path[0]] == 1)
return true;
else
return false;
}
// Try different vertices as a next candidate
// in Hamiltonian Cycle. We don't try for 0 as
// we included 0 as starting point in in hamCycle()
for (int v = 1; v < V; v++)
{
/* Check if this vertex can be added
// to Hamiltonian Cycle */
if (isSafe(v, graph, path, pos))
{
path[pos] = v;
/* recur to construct rest of the path */
if (hamCycleUtil (graph, path, pos + 1) == true)
return true;
/* If adding vertex v doesn't lead to a solution,
then remove it */
path[pos] = -1;
}
}
/* If no vertex can be added to
Hamiltonian Cycle constructed so far,
then return false */
return false;
}
/* This function solves the Hamiltonian Cycle problem
using Backtracking. It mainly uses hamCycleUtil() to
solve the problem. It returns false if there is no
Hamiltonian Cycle possible, otherwise return true
and prints the path. Please note that there may be
more than one solutions, this function prints one
of the feasible solutions. */
bool hamCycle(bool graph[V][V])
{
int *path = new int[V];
for (int i = 0; i < V; i++)
path[i] = -1;
/* Let us put vertex 0 as the first vertex in the path.
If there is a Hamiltonian Cycle, then the path can be
started from any point of the cycle as the graph is undirected */
path[0] = 0;
if (hamCycleUtil(graph, path, 1) == false )
{
cout << "\nSolution does not exist";
return false;
}
printSolution(path);
return true;
}
/* A utility function to print solution */
void printSolution(int path[])
{
cout << "Solution Exists:"
" Following is one Hamiltonian Cycle \n";
for (int i = 0; i < V; i++)
cout << path[i] << " ";
// Let us print the first vertex again
// to show the complete cycle
cout << path[0] << " ";
cout << endl;
}
// Driver Code
int main()
{
/* Let us create the following graph
(0)--(1)--(2)
| / \ |
| / \ |
| / \ |
(3)-------(4) */
bool graph1[V][V] = {{0, 1, 0, 1, 0},
{1, 0, 1, 1, 1},
{0, 1, 0, 0, 1},
{1, 1, 0, 0, 1},
{0, 1, 1, 1, 0}};
// Print the solution
hamCycle(graph1);
/* Let us create the following graph
(0)--(1)--(2)
| / \ |
| / \ |
| / \ |
(3) (4) */
bool graph2[V][V] = {{0, 1, 0, 1, 0},
{1, 0, 1, 1, 1},
{0, 1, 0, 0, 1},
{1, 1, 0, 0, 0},
{0, 1, 1, 0, 0}};
// Print the solution
hamCycle(graph2);
return 0;
}
// This is code is contributed by rathbhupendra
C
/* C program for solution of Hamiltonian Cycle problem
using backtracking */
#include<stdio.h>
// Number of vertices in the graph
#define V 5
void printSolution(int path[]);
/* A utility function to check if the vertex v can be added at
index 'pos' in the Hamiltonian Cycle constructed so far (stored
in 'path[]') */
bool isSafe(int v, bool graph[V][V], int path[], int pos)
{
/* Check if this vertex is an adjacent vertex of the previously
added vertex. */
if (graph [ path[pos-1] ][ v ] == 0)
return false;
/* Check if the vertex has already been included.
This step can be optimized by creating an array of size V */
for (int i = 0; i < pos; i++)
if (path[i] == v)
return false;
return true;
}
/* A recursive utility function to solve hamiltonian cycle problem */
bool hamCycleUtil(bool graph[V][V], int path[], int pos)
{
/* base case: If all vertices are included in Hamiltonian Cycle */
if (pos == V)
{
// And if there is an edge from the last included vertex to the
// first vertex
if ( graph[ path[pos-1] ][ path[0] ] == 1 )
return true;
else
return false;
}
// Try different vertices as a next candidate in Hamiltonian Cycle.
// We don't try for 0 as we included 0 as starting point in in hamCycle()
for (int v = 1; v < V; v++)
{
/* Check if this vertex can be added to Hamiltonian Cycle */
if (isSafe(v, graph, path, pos))
{
path[pos] = v;
/* recur to construct rest of the path */
if (hamCycleUtil (graph, path, pos+1) == true)
return true;
/* If adding vertex v doesn't lead to a solution,
then remove it */
path[pos] = -1;
}
}
/* If no vertex can be added to Hamiltonian Cycle constructed so far,
then return false */
return false;
}
/* This function solves the Hamiltonian Cycle problem using Backtracking.
It mainly uses hamCycleUtil() to solve the problem. It returns false
if there is no Hamiltonian Cycle possible, otherwise return true and
prints the path. Please note that there may be more than one solutions,
this function prints one of the feasible solutions. */
bool hamCycle(bool graph[V][V])
{
int *path = new int[V];
for (int i = 0; i < V; i++)
path[i] = -1;
/* Let us put vertex 0 as the first vertex in the path. If there is
a Hamiltonian Cycle, then the path can be started from any point
of the cycle as the graph is undirected */
path[0] = 0;
if ( hamCycleUtil(graph, path, 1) == false )
{
printf("\nSolution does not exist");
return false;
}
printSolution(path);
return true;
}
/* A utility function to print solution */
void printSolution(int path[])
{
printf ("Solution Exists:"
" Following is one Hamiltonian Cycle \n");
for (int i = 0; i < V; i++)
printf(" %d ", path[i]);
// Let us print the first vertex again to show the complete cycle
printf(" %d ", path[0]);
printf("\n");
}
// driver program to test above function
int main()
{
/* Let us create the following graph
(0)--(1)--(2)
| / \ |
| / \ |
| / \ |
(3)-------(4) */
bool graph1[V][V] = {{0, 1, 0, 1, 0},
{1, 0, 1, 1, 1},
{0, 1, 0, 0, 1},
{1, 1, 0, 0, 1},
{0, 1, 1, 1, 0},
};
// Print the solution
hamCycle(graph1);
/* Let us create the following graph
(0)--(1)--(2)
| / \ |
| / \ |
| / \ |
(3) (4) */
bool graph2[V][V] = {{0, 1, 0, 1, 0},
{1, 0, 1, 1, 1},
{0, 1, 0, 0, 1},
{1, 1, 0, 0, 0},
{0, 1, 1, 0, 0},
};
// Print the solution
hamCycle(graph2);
return 0;
}
پایتون
# Python program for solution of
# hamiltonian cycle problem
class Graph():
def __init__(self, vertices):
self.graph = [[0 for column in range(vertices)]\
for row in range(vertices)]
self.V = vertices
''' Check if this vertex is an adjacent vertex
of the previously added vertex and is not
included in the path earlier '''
def isSafe(self, v, pos, path):
# Check if current vertex and last vertex
# in path are adjacent
if self.graph[ path[pos-1] ][v] == 0:
return False
# Check if current vertex not already in path
for vertex in path:
if vertex == v:
return False
return True
# A recursive utility function to solve
# hamiltonian cycle problem
def hamCycleUtil(self, path, pos):
# base case: if all vertices are
# included in the path
if pos == self.V:
# Last vertex must be adjacent to the
# first vertex in path to make a cyle
if self.graph[ path[pos-1] ][ path[0] ] == 1:
return True
else:
return False
# Try different vertices as a next candidate
# in Hamiltonian Cycle. We don't try for 0 as
# we included 0 as starting point in in hamCycle()
for v in range(1,self.V):
if self.isSafe(v, pos, path) == True:
path[pos] = v
if self.hamCycleUtil(path, pos+1) == True:
return True
# Remove current vertex if it doesn't
# lead to a solution
path[pos] = -1
return False
def hamCycle(self):
path = [-1] * self.V
''' Let us put vertex 0 as the first vertex
in the path. If there is a Hamiltonian Cycle,
then the path can be started from any point
of the cycle as the graph is undirected '''
path[0] = 0
if self.hamCycleUtil(path,1) == False:
print "Solution does not exist\n"
return False
self.printSolution(path)
return True
def printSolution(self, path):
print "Solution Exists: Following is one Hamiltonian Cycle"
for vertex in path:
print vertex,
print path[0], "\n"
# Driver Code
''' Let us create the following graph
(0)--(1)--(2)
| / \ |
| / \ |
| / \ |
(3)-------(4) '''
g1 = Graph(5)
g1.graph = [ [0, 1, 0, 1, 0], [1, 0, 1, 1, 1],
[0, 1, 0, 0, 1,],[1, 1, 0, 0, 1],
[0, 1, 1, 1, 0], ]
# Print the solution
g1.hamCycle();
''' Let us create the following graph
(0)--(1)--(2)
| / \ |
| / \ |
| / \ |
(3) (4) '''
g2 = Graph(5)
g2.graph = [ [0, 1, 0, 1, 0], [1, 0, 1, 1, 1],
[0, 1, 0, 0, 1,], [1, 1, 0, 0, 0],
[0, 1, 1, 0, 0], ]
# Print the solution
g2.hamCycle();
# This code is contributed by Divyanshu Mehta
جاوا
/* Java program for solution of Hamiltonian Cycle problem
using backtracking */
class HamiltonianCycle
{
final int V = 5;
int path[];
/* A utility function to check if the vertex v can be
added at index 'pos'in the Hamiltonian Cycle
constructed so far (stored in 'path[]') */
boolean isSafe(int v, int graph[][], int path[], int pos)
{
/* Check if this vertex is an adjacent vertex of
the previously added vertex. */
if (graph[path[pos - 1]][v] == 0)
return false;
/* Check if the vertex has already been included.
This step can be optimized by creating an array
of size V */
for (int i = 0; i < pos; i++)
if (path[i] == v)
return false;
return true;
}
/* A recursive utility function to solve hamiltonian
cycle problem */
boolean hamCycleUtil(int graph[][], int path[], int pos)
{
/* base case: If all vertices are included in
Hamiltonian Cycle */
if (pos == V)
{
// And if there is an edge from the last included
// vertex to the first vertex
if (graph[path[pos - 1]][path[0]] == 1)
return true;
else
return false;
}
// Try different vertices as a next candidate in
// Hamiltonian Cycle. We don't try for 0 as we
// included 0 as starting point in in hamCycle()
for (int v = 1; v < V; v++)
{
/* Check if this vertex can be added to Hamiltonian
Cycle */
if (isSafe(v, graph, path, pos))
{
path[pos] = v;
/* recur to construct rest of the path */
if (hamCycleUtil(graph, path, pos + 1) == true)
return true;
/* If adding vertex v doesn't lead to a solution,
then remove it */
path[pos] = -1;
}
}
/* If no vertex can be added to Hamiltonian Cycle
constructed so far, then return false */
return false;
}
/* This function solves the Hamiltonian Cycle problem using
Backtracking. It mainly uses hamCycleUtil() to solve the
problem. It returns false if there is no Hamiltonian Cycle
possible, otherwise return true and prints the path.
Please note that there may be more than one solutions,
this function prints one of the feasible solutions. */
int hamCycle(int graph[][])
{
path = new int[V];
for (int i = 0; i < V; i++)
path[i] = -1;
/* Let us put vertex 0 as the first vertex in the path.
If there is a Hamiltonian Cycle, then the path can be
started from any point of the cycle as the graph is
undirected */
path[0] = 0;
if (hamCycleUtil(graph, path, 1) == false)
{
System.out.println("\nSolution does not exist");
return 0;
}
printSolution(path);
return 1;
}
/* A utility function to print solution */
void printSolution(int path[])
{
System.out.println("Solution Exists: Following" +
" is one Hamiltonian Cycle");
for (int i = 0; i < V; i++)
System.out.print(" " + path[i] + " ");
// Let us print the first vertex again to show the
// complete cycle
System.out.println(" " + path[0] + " ");
}
// driver program to test above function
public static void main(String args[])
{
HamiltonianCycle hamiltonian =
new HamiltonianCycle();
/* Let us create the following graph
(0)--(1)--(2)
| / \ |
| / \ |
| / \ |
(3)-------(4) */
int graph1[][] = {{0, 1, 0, 1, 0},
{1, 0, 1, 1, 1},
{0, 1, 0, 0, 1},
{1, 1, 0, 0, 1},
{0, 1, 1, 1, 0},
};
// Print the solution
hamiltonian.hamCycle(graph1);
/* Let us create the following graph
(0)--(1)--(2)
| / \ |
| / \ |
| / \ |
(3) (4) */
int graph2[][] = {{0, 1, 0, 1, 0},
{1, 0, 1, 1, 1},
{0, 1, 0, 0, 1},
{1, 1, 0, 0, 0},
{0, 1, 1, 0, 0},
};
// Print the solution
hamiltonian.hamCycle(graph2);
}
}
// This code is contributed by Abhishek Shankhadhar
سی شارپ
// C# program for solution of Hamiltonian
// Cycle problem using backtracking
using System;
public class HamiltonianCycle
{
readonly int V = 5;
int []path;
/* A utility function to check
if the vertex v can be added at
index 'pos'in the Hamiltonian Cycle
constructed so far (stored in 'path[]') */
bool isSafe(int v, int [,]graph,
int []path, int pos)
{
/* Check if this vertex is
an adjacent vertex of the
previously added vertex. */
if (graph[path[pos - 1], v] == 0)
return false;
/* Check if the vertex has already
been included. This step can be
optimized by creating an array
of size V */
for (int i = 0; i < pos; i++)
if (path[i] == v)
return false;
return true;
}
/* A recursive utility function
to solve hamiltonian cycle problem */
bool hamCycleUtil(int [,]graph, int []path, int pos)
{
/* base case: If all vertices
are included in Hamiltonian Cycle */
if (pos == V)
{
// And if there is an edge from the last included
// vertex to the first vertex
if (graph[path[pos - 1],path[0]] == 1)
return true;
else
return false;
}
// Try different vertices as a next candidate in
// Hamiltonian Cycle. We don't try for 0 as we
// included 0 as starting point in in hamCycle()
for (int v = 1; v < V; v++)
{
/* Check if this vertex can be
added to Hamiltonian Cycle */
if (isSafe(v, graph, path, pos))
{
path[pos] = v;
/* recur to construct rest of the path */
if (hamCycleUtil(graph, path, pos + 1) == true)
return true;
/* If adding vertex v doesn't
lead to a solution, then remove it */
path[pos] = -1;
}
}
/* If no vertex can be added to Hamiltonian Cycle
constructed so far, then return false */
return false;
}
/* This function solves the Hamiltonian
Cycle problem using Backtracking. It
mainly uses hamCycleUtil() to solve the
problem. It returns false if there
is no Hamiltonian Cycle possible,
otherwise return true and prints the path.
Please note that there may be more than
one solutions, this function prints one
of the feasible solutions. */
int hamCycle(int [,]graph)
{
path = new int[V];
for (int i = 0; i < V; i++)
path[i] = -1;
/* Let us put vertex 0 as the first
vertex in the path. If there is a
Hamiltonian Cycle, then the path can be
started from any point of the cycle
as the graph is undirected */
path[0] = 0;
if (hamCycleUtil(graph, path, 1) == false)
{
Console.WriteLine("\nSolution does not exist");
return 0;
}
printSolution(path);
return 1;
}
/* A utility function to print solution */
void printSolution(int []path)
{
Console.WriteLine("Solution Exists: Following" +
" is one Hamiltonian Cycle");
for (int i = 0; i < V; i++)
Console.Write(" " + path[i] + " ");
// Let us print the first vertex again
// to show the complete cycle
Console.WriteLine(" " + path[0] + " ");
}
// Driver code
public static void Main(String []args)
{
HamiltonianCycle hamiltonian =
new HamiltonianCycle();
/* Let us create the following graph
(0)--(1)--(2)
| / \ |
| / \ |
| / \ |
(3)-------(4) */
int [,]graph1= {{0, 1, 0, 1, 0},
{1, 0, 1, 1, 1},
{0, 1, 0, 0, 1},
{1, 1, 0, 0, 1},
{0, 1, 1, 1, 0},
};
// Print the solution
hamiltonian.hamCycle(graph1);
/* Let us create the following graph
(0)--(1)--(2)
| / \ |
| / \ |
| / \ |
(3) (4) */
int [,]graph2 = {{0, 1, 0, 1, 0},
{1, 0, 1, 1, 1},
{0, 1, 0, 0, 1},
{1, 1, 0, 0, 0},
{0, 1, 1, 0, 0},
};
// Print the solution
hamiltonian.hamCycle(graph2);
}
}
// This code contributed by Rajput-Ji
خروجی:
Solution Exists: Following is one Hamiltonian Cycle 0 1 2 4 3 0 Solution does not exist
توجه به این نکته لازم است که قطعه کد بالا، همیشه دورهایی که از صفر شروع می‌شوند را چاپ می‌کند. نقطه شروع نباید اهمیتی داشته باشد، زیرا یک دور می‌تواند از هر راسی آغاز شود.
افرادی که قصد تغییر دادن نقطه شروع را دارند، باید دو تغییر در کد بالا اعمال کنند. تغییر «;path[0] = 0» به «;path[0] = s» که در آن، s نقطه شروع جدید است. همچنین، باید حلقه «(++for (int v = 1; v < V; v» در ()hamCycleUtil، به «(++for (int v = 0; v < V; v» تغییر پیدا کند.
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد می‌شوند:
- مجموعه آموزشهای برنامهنویسی
- آموزش ساختمان داده‌ها
- مجموعه آموزشهای ساختمان داده و طراحی الگوریتم
- زبان برنامهنویسی پایتون (Python) — از صفر تا صد
- آموزش ساختمان داده — مجموعه مقالات جامع وبلاگ فرادرس
- ساختمان داده (Data Structure) — راهنمای جامع و کاربردی
^^
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
ثبت نظر
منابع:
GeeksforGeeks
کپی شد
«الهام حصارکی»، فارغ‌التحصیل مقطع کارشناسی ارشد مهندسی فناوری اطلاعات، گرایش سیستم‌های اطلاعات مدیریت است. او در زمینه هوش مصنوعی و داده‌کاوی، به ویژه تحلیل شبکه‌های اجتماعی، فعالیت می‌کند.
مطالب مرتبط
