یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده

۱۳۴۶ بازدید
آخرین به‌روزرسانی: ۱۰ تیر ۱۴۰۲
زمان مطالعه: ۱۳ دقیقه
یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده

«مسیر همیلتونی» (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، پیکربندی ممکن وجود دارد.

1while there are untried conflagrations
2{
3   generate the next configuration
4   if ( there are edges between two consecutive vertices of this
5      configuration and there is an edge from the last vertex to 
6      the first ).
7   {
8      print this configuration;
9      break;
10   }
11}

یافتن دور همیلتونی با الگوریتم پس‌گرد (Backtracking Algorithm)

این الگوریتم یک آرایه مسیر خالی می‌سازد و راس ۰ را به آن اضافه می‌کند.

در ادامه، دیگر راس‌ها را با آغاز از راس ۱ به آرایه اضافه می‌کند؛ اما پیش از اضافه کردن یک راس، بررسی می‌کند که آیا با راس پیشین اضافه شده مجاور است یا خیر و همچنین، بررسی می‌کند که راس، پیش از این به آرایه اضافه نشده باشد. اگر چنین راسی پیدا شود، یال به عنوان بخشی از راهکار اضافه می‌شود. اگر راس پیدا نشود، مقدار false بازگردانده می‌شود.

پیاده‌سازی الگوریتم پس‌گرد برای مساله یافتن دور همیلتونی در گراف

در ادامه، پیاده‌سازی الگوریتم پس‌گرد برای مساله یافتن دور همیلتونی در گراف در زبان‌های برنامه‌نویسی گوناگون ارائه شده است.

++C

1/* C++ program for solution of Hamiltonian  
2Cycle problem using backtracking */
3#include <bits/stdc++.h> 
4using namespace std; 
5  
6// Number of vertices in the graph  
7#define V 5  
8  
9void printSolution(int path[]);  
10  
11/* A utility function to check if  
12the vertex v can be added at index 'pos'  
13in the Hamiltonian Cycle constructed  
14so far (stored in 'path[]') */
15bool isSafe(int v, bool graph[V][V],  
16            int path[], int pos)  
17{  
18    /* Check if this vertex is an adjacent  
19    vertex of the previously added vertex. */
20    if (graph [path[pos - 1]][ v ] == 0)  
21        return false;  
22  
23    /* Check if the vertex has already been included.  
24    This step can be optimized by creating 
25    an array of size V */
26    for (int i = 0; i < pos; i++)  
27        if (path[i] == v)  
28            return false;  
29  
30    return true;  
31}  
32  
33/* A recursive utility function  
34to solve hamiltonian cycle problem */
35bool hamCycleUtil(bool graph[V][V],  
36                  int path[], int pos)  
37{  
38    /* base case: If all vertices are  
39    included in Hamiltonian Cycle */
40    if (pos == V)  
41    {  
42        // And if there is an edge from the  
43        // last included vertex to the first vertex  
44        if (graph[path[pos - 1]][path[0]] == 1)  
45            return true;  
46        else
47            return false;  
48    }  
49  
50    // Try different vertices as a next candidate  
51    // in Hamiltonian Cycle. We don't try for 0 as  
52    // we included 0 as starting point in in hamCycle()  
53    for (int v = 1; v < V; v++)  
54    {  
55        /* Check if this vertex can be added  
56        // to Hamiltonian Cycle */
57        if (isSafe(v, graph, path, pos))  
58        {  
59            path[pos] = v;  
60  
61            /* recur to construct rest of the path */
62            if (hamCycleUtil (graph, path, pos + 1) == true)  
63                return true;  
64  
65            /* If adding vertex v doesn't lead to a solution,  
66            then remove it */
67            path[pos] = -1;  
68        }  
69    }  
70  
71    /* If no vertex can be added to  
72    Hamiltonian Cycle constructed so far,  
73    then return false */
74    return false;  
75}  
76  
77/* This function solves the Hamiltonian Cycle problem  
78using Backtracking. It mainly uses hamCycleUtil() to  
79solve the problem. It returns false if there is no  
80Hamiltonian Cycle possible, otherwise return true  
81and prints the path. Please note that there may be  
82more than one solutions, this function prints one  
83of the feasible solutions. */
84bool hamCycle(bool graph[V][V])  
85{  
86    int *path = new int[V];  
87    for (int i = 0; i < V; i++)  
88        path[i] = -1;  
89  
90    /* Let us put vertex 0 as the first vertex in the path. 
91    If there is a Hamiltonian Cycle, then the path can be  
92    started from any point of the cycle as the graph is undirected */
93    path[0] = 0;  
94    if (hamCycleUtil(graph, path, 1) == false )  
95    {  
96        cout << "\nSolution does not exist";  
97        return false;  
98    }  
99  
100    printSolution(path);  
101    return true;  
102}  
103  
104/* A utility function to print solution */
105void printSolution(int path[])  
106{  
107    cout << "Solution Exists:"
108            " Following is one Hamiltonian Cycle \n";  
109    for (int i = 0; i < V; i++)  
110        cout << path[i] << " ";  
111  
112    // Let us print the first vertex again 
113    // to show the complete cycle  
114    cout << path[0] << " ";  
115    cout << endl; 
116}  
117  
118// Driver Code  
119int main()  
120{  
121    /* Let us create the following graph  
122        (0)--(1)--(2)  
123        | / \ |  
124        | / \ |  
125        | / \ |  
126        (3)-------(4) */
127    bool graph1[V][V] = {{0, 1, 0, 1, 0},  
128                        {1, 0, 1, 1, 1},  
129                        {0, 1, 0, 0, 1},  
130                        {1, 1, 0, 0, 1},  
131                        {0, 1, 1, 1, 0}};  
132      
133    // Print the solution  
134    hamCycle(graph1);  
135      
136    /* Let us create the following graph  
137    (0)--(1)--(2)  
138    | / \ |  
139    | / \ |  
140    | / \ |  
141    (3) (4) */
142    bool graph2[V][V] = {{0, 1, 0, 1, 0},  
143                         {1, 0, 1, 1, 1},  
144                         {0, 1, 0, 0, 1},  
145                         {1, 1, 0, 0, 0},  
146                         {0, 1, 1, 0, 0}};  
147  
148    // Print the solution  
149    hamCycle(graph2);  
150  
151    return 0;  
152}  
153  
154// This is code is contributed by rathbhupendra 

C

1/* C program for solution of Hamiltonian Cycle problem 
2   using backtracking */
3#include<stdio.h> 
4  
5// Number of vertices in the graph 
6#define V 5 
7  
8void printSolution(int path[]); 
9  
10/* A utility function to check if the vertex v can be added at 
11   index 'pos' in the Hamiltonian Cycle constructed so far (stored 
12   in 'path[]') */
13bool isSafe(int v, bool graph[V][V], int path[], int pos) 
14{ 
15    /* Check if this vertex is an adjacent vertex of the previously 
16       added vertex. */
17    if (graph [ path[pos-1] ][ v ] == 0) 
18        return false; 
19  
20    /* Check if the vertex has already been included. 
21      This step can be optimized by creating an array of size V */
22    for (int i = 0; i < pos; i++) 
23        if (path[i] == v) 
24            return false; 
25  
26    return true; 
27} 
28  
29/* A recursive utility function to solve hamiltonian cycle problem */
30bool hamCycleUtil(bool graph[V][V], int path[], int pos) 
31{ 
32    /* base case: If all vertices are included in Hamiltonian Cycle */
33    if (pos == V) 
34    { 
35        // And if there is an edge from the last included vertex to the 
36        // first vertex 
37        if ( graph[ path[pos-1] ][ path[0] ] == 1 ) 
38           return true; 
39        else
40          return false; 
41    } 
42  
43    // Try different vertices as a next candidate in Hamiltonian Cycle. 
44    // We don't try for 0 as we included 0 as starting point in in hamCycle() 
45    for (int v = 1; v < V; v++) 
46    { 
47        /* Check if this vertex can be added to Hamiltonian Cycle */
48        if (isSafe(v, graph, path, pos)) 
49        { 
50            path[pos] = v; 
51  
52            /* recur to construct rest of the path */
53            if (hamCycleUtil (graph, path, pos+1) == true) 
54                return true; 
55  
56            /* If adding vertex v doesn't lead to a solution, 
57               then remove it */
58            path[pos] = -1; 
59        } 
60    } 
61  
62    /* If no vertex can be added to Hamiltonian Cycle constructed so far, 
63       then return false */
64    return false; 
65} 
66  
67/* This function solves the Hamiltonian Cycle problem using Backtracking. 
68  It mainly uses hamCycleUtil() to solve the problem. It returns false 
69  if there is no Hamiltonian Cycle possible, otherwise return true and 
70  prints the path. Please note that there may be more than one solutions, 
71  this function prints one of the feasible solutions. */
72bool hamCycle(bool graph[V][V]) 
73{ 
74    int *path = new int[V]; 
75    for (int i = 0; i < V; i++) 
76        path[i] = -1; 
77  
78    /* Let us put vertex 0 as the first vertex in the path. If there is 
79       a Hamiltonian Cycle, then the path can be started from any point 
80       of the cycle as the graph is undirected */
81    path[0] = 0; 
82    if ( hamCycleUtil(graph, path, 1) == false ) 
83    { 
84        printf("\nSolution does not exist"); 
85        return false; 
86    } 
87  
88    printSolution(path); 
89    return true; 
90} 
91  
92/* A utility function to print solution */
93void printSolution(int path[]) 
94{ 
95    printf ("Solution Exists:"
96            " Following is one Hamiltonian Cycle \n"); 
97    for (int i = 0; i < V; i++) 
98        printf(" %d ", path[i]); 
99  
100    // Let us print the first vertex again to show the complete cycle 
101    printf(" %d ", path[0]); 
102    printf("\n"); 
103} 
104  
105// driver program to test above function 
106int main() 
107{ 
108   /* Let us create the following graph 
109      (0)--(1)--(2) 
110       |   / \   | 
111       |  /   \  | 
112       | /     \ | 
113      (3)-------(4)    */
114   bool graph1[V][V] = {{0, 1, 0, 1, 0}, 
115                      {1, 0, 1, 1, 1}, 
116                      {0, 1, 0, 0, 1}, 
117                      {1, 1, 0, 0, 1}, 
118                      {0, 1, 1, 1, 0}, 
119                     }; 
120  
121    // Print the solution 
122    hamCycle(graph1); 
123  
124   /* Let us create the following graph 
125      (0)--(1)--(2) 
126       |   / \   | 
127       |  /   \  | 
128       | /     \ | 
129      (3)       (4)    */
130    bool graph2[V][V] = {{0, 1, 0, 1, 0}, 
131                      {1, 0, 1, 1, 1}, 
132                      {0, 1, 0, 0, 1}, 
133                      {1, 1, 0, 0, 0}, 
134                      {0, 1, 1, 0, 0}, 
135                     }; 
136  
137    // Print the solution 
138    hamCycle(graph2); 
139  
140    return 0; 
141}

پایتون

1# Python program for solution of 
2# hamiltonian cycle problem 
3  
4class Graph(): 
5    def __init__(self, vertices): 
6        self.graph = [[0 for column in range(vertices)]\ 
7                            for row in range(vertices)] 
8        self.V = vertices 
9  
10    ''' Check if this vertex is an adjacent vertex  
11        of the previously added vertex and is not  
12        included in the path earlier '''
13    def isSafe(self, v, pos, path): 
14        # Check if current vertex and last vertex  
15        # in path are adjacent 
16        if self.graph[ path[pos-1] ][v] == 0: 
17            return False
18  
19        # Check if current vertex not already in path 
20        for vertex in path: 
21            if vertex == v: 
22                return False
23  
24        return True
25  
26    # A recursive utility function to solve  
27    # hamiltonian cycle problem 
28    def hamCycleUtil(self, path, pos): 
29  
30        # base case: if all vertices are  
31        # included in the path 
32        if pos == self.V: 
33            # Last vertex must be adjacent to the  
34            # first vertex in path to make a cyle 
35            if self.graph[ path[pos-1] ][ path[0] ] == 1: 
36                return True
37            else: 
38                return False
39  
40        # Try different vertices as a next candidate  
41        # in Hamiltonian Cycle. We don't try for 0 as  
42        # we included 0 as starting point in in hamCycle() 
43        for v in range(1,self.V): 
44  
45            if self.isSafe(v, pos, path) == True: 
46  
47                path[pos] = v 
48  
49                if self.hamCycleUtil(path, pos+1) == True: 
50                    return True
51  
52                # Remove current vertex if it doesn't  
53                # lead to a solution 
54                path[pos] = -1
55  
56        return False
57  
58    def hamCycle(self): 
59        path = [-1] * self.V 
60  
61        ''' Let us put vertex 0 as the first vertex  
62            in the path. If there is a Hamiltonian Cycle,  
63            then the path can be started from any point 
64            of the cycle as the graph is undirected '''
65        path[0] = 0
66  
67        if self.hamCycleUtil(path,1) == False: 
68            print "Solution does not exist\n"
69            return False
70  
71        self.printSolution(path) 
72        return True
73  
74    def printSolution(self, path): 
75        print "Solution Exists: Following is one Hamiltonian Cycle"
76        for vertex in path: 
77            print vertex, 
78        print path[0], "\n"
79  
80# Driver Code 
81  
82''' Let us create the following graph 
83      (0)--(1)--(2) 
84       |   / \   | 
85       |  /   \  | 
86       | /     \ | 
87      (3)-------(4)    '''
88g1 = Graph(5) 
89g1.graph = [ [0, 1, 0, 1, 0], [1, 0, 1, 1, 1],  
90             [0, 1, 0, 0, 1,],[1, 1, 0, 0, 1],  
91             [0, 1, 1, 1, 0], ] 
92  
93# Print the solution 
94g1.hamCycle(); 
95  
96''' Let us create the following graph 
97      (0)--(1)--(2) 
98       |   / \   | 
99       |  /   \  | 
100       | /     \ | 
101      (3)       (4)    '''
102g2 = Graph(5) 
103g2.graph = [ [0, 1, 0, 1, 0], [1, 0, 1, 1, 1],  
104           [0, 1, 0, 0, 1,], [1, 1, 0, 0, 0],  
105           [0, 1, 1, 0, 0], ] 
106  
107# Print the solution 
108g2.hamCycle(); 
109  
110# This code is contributed by Divyanshu Mehta 

جاوا

1/* Java program for solution of Hamiltonian Cycle problem 
2   using backtracking */
3class HamiltonianCycle 
4{ 
5    final int V = 5; 
6    int path[]; 
7  
8    /* A utility function to check if the vertex v can be 
9       added at index 'pos'in the Hamiltonian Cycle 
10       constructed so far (stored in 'path[]') */
11    boolean isSafe(int v, int graph[][], int path[], int pos) 
12    { 
13        /* Check if this vertex is an adjacent vertex of 
14           the previously added vertex. */
15        if (graph[path[pos - 1]][v] == 0) 
16            return false; 
17  
18        /* Check if the vertex has already been included. 
19           This step can be optimized by creating an array 
20           of size V */
21        for (int i = 0; i < pos; i++) 
22            if (path[i] == v) 
23                return false; 
24  
25        return true; 
26    } 
27  
28    /* A recursive utility function to solve hamiltonian 
29       cycle problem */
30    boolean hamCycleUtil(int graph[][], int path[], int pos) 
31    { 
32        /* base case: If all vertices are included in 
33           Hamiltonian Cycle */
34        if (pos == V) 
35        { 
36            // And if there is an edge from the last included 
37            // vertex to the first vertex 
38            if (graph[path[pos - 1]][path[0]] == 1) 
39                return true; 
40            else
41                return false; 
42        } 
43  
44        // Try different vertices as a next candidate in 
45        // Hamiltonian Cycle. We don't try for 0 as we 
46        // included 0 as starting point in in hamCycle() 
47        for (int v = 1; v < V; v++) 
48        { 
49            /* Check if this vertex can be added to Hamiltonian 
50               Cycle */
51            if (isSafe(v, graph, path, pos)) 
52            { 
53                path[pos] = v; 
54  
55                /* recur to construct rest of the path */
56                if (hamCycleUtil(graph, path, pos + 1) == true) 
57                    return true; 
58  
59                /* If adding vertex v doesn't lead to a solution, 
60                   then remove it */
61                path[pos] = -1; 
62            } 
63        } 
64  
65        /* If no vertex can be added to Hamiltonian Cycle 
66           constructed so far, then return false */
67        return false; 
68    } 
69  
70    /* This function solves the Hamiltonian Cycle problem using 
71       Backtracking. It mainly uses hamCycleUtil() to solve the 
72       problem. It returns false if there is no Hamiltonian Cycle 
73       possible, otherwise return true and prints the path. 
74       Please note that there may be more than one solutions, 
75       this function prints one of the feasible solutions. */
76    int hamCycle(int graph[][]) 
77    { 
78        path = new int[V]; 
79        for (int i = 0; i < V; i++) 
80            path[i] = -1; 
81  
82        /* Let us put vertex 0 as the first vertex in the path. 
83           If there is a Hamiltonian Cycle, then the path can be 
84           started from any point of the cycle as the graph is 
85           undirected */
86        path[0] = 0; 
87        if (hamCycleUtil(graph, path, 1) == false) 
88        { 
89            System.out.println("\nSolution does not exist"); 
90            return 0; 
91        } 
92  
93        printSolution(path); 
94        return 1; 
95    } 
96  
97    /* A utility function to print solution */
98    void printSolution(int path[]) 
99    { 
100        System.out.println("Solution Exists: Following" + 
101                           " is one Hamiltonian Cycle"); 
102        for (int i = 0; i < V; i++) 
103            System.out.print(" " + path[i] + " "); 
104  
105        // Let us print the first vertex again to show the 
106        // complete cycle 
107        System.out.println(" " + path[0] + " "); 
108    } 
109  
110    // driver program to test above function 
111    public static void main(String args[]) 
112    { 
113        HamiltonianCycle hamiltonian = 
114                                new HamiltonianCycle(); 
115        /* Let us create the following graph 
116           (0)--(1)--(2) 
117            |   / \   | 
118            |  /   \  | 
119            | /     \ | 
120           (3)-------(4)    */
121        int graph1[][] = {{0, 1, 0, 1, 0}, 
122            {1, 0, 1, 1, 1}, 
123            {0, 1, 0, 0, 1}, 
124            {1, 1, 0, 0, 1}, 
125            {0, 1, 1, 1, 0}, 
126        }; 
127  
128        // Print the solution 
129        hamiltonian.hamCycle(graph1); 
130  
131        /* Let us create the following graph 
132           (0)--(1)--(2) 
133            |   / \   | 
134            |  /   \  | 
135            | /     \ | 
136           (3)       (4)    */
137        int graph2[][] = {{0, 1, 0, 1, 0}, 
138            {1, 0, 1, 1, 1}, 
139            {0, 1, 0, 0, 1}, 
140            {1, 1, 0, 0, 0}, 
141            {0, 1, 1, 0, 0}, 
142        }; 
143  
144        // Print the solution 
145        hamiltonian.hamCycle(graph2); 
146    } 
147} 
148// This code is contributed by Abhishek Shankhadhar

سی شارپ

1// C# program for solution of Hamiltonian  
2// Cycle problem using backtracking 
3using System; 
4  
5public class HamiltonianCycle 
6{ 
7    readonly int V = 5; 
8    int []path; 
9  
10    /* A utility function to check  
11    if the vertex v can be added at  
12    index 'pos'in the Hamiltonian Cycle 
13    constructed so far (stored in 'path[]') */
14    bool isSafe(int v, int [,]graph, 
15                int []path, int pos) 
16    { 
17        /* Check if this vertex is  
18        an adjacent vertex of the 
19        previously added vertex. */
20        if (graph[path[pos - 1], v] == 0) 
21            return false; 
22  
23        /* Check if the vertex has already  
24        been included. This step can be 
25        optimized by creating an array 
26        of size V */
27        for (int i = 0; i < pos; i++) 
28            if (path[i] == v) 
29                return false; 
30  
31        return true; 
32    } 
33  
34    /* A recursive utility function 
35    to solve hamiltonian cycle problem */
36    bool hamCycleUtil(int [,]graph, int []path, int pos) 
37    { 
38        /* base case: If all vertices  
39        are included in Hamiltonian Cycle */
40        if (pos == V) 
41        { 
42            // And if there is an edge from the last included 
43            // vertex to the first vertex 
44            if (graph[path[pos - 1],path[0]] == 1) 
45                return true; 
46            else
47                return false; 
48        } 
49  
50        // Try different vertices as a next candidate in 
51        // Hamiltonian Cycle. We don't try for 0 as we 
52        // included 0 as starting point in in hamCycle() 
53        for (int v = 1; v < V; v++) 
54        { 
55            /* Check if this vertex can be  
56            added to Hamiltonian Cycle */
57            if (isSafe(v, graph, path, pos)) 
58            { 
59                path[pos] = v; 
60  
61                /* recur to construct rest of the path */
62                if (hamCycleUtil(graph, path, pos + 1) == true) 
63                    return true; 
64  
65                /* If adding vertex v doesn't  
66                lead to a solution, then remove it */
67                path[pos] = -1; 
68            } 
69        } 
70  
71        /* If no vertex can be added to Hamiltonian Cycle 
72        constructed so far, then return false */
73        return false; 
74    } 
75  
76    /* This function solves the Hamiltonian  
77    Cycle problem using Backtracking. It  
78    mainly uses hamCycleUtil() to solve the 
79    problem. It returns false if there 
80    is no Hamiltonian Cycle possible,  
81    otherwise return true and prints the path. 
82    Please note that there may be more than  
83    one solutions, this function prints one  
84    of the feasible solutions. */
85    int hamCycle(int [,]graph) 
86    { 
87        path = new int[V]; 
88        for (int i = 0; i < V; i++) 
89            path[i] = -1; 
90  
91        /* Let us put vertex 0 as the first 
92        vertex in the path. If there is a  
93        Hamiltonian Cycle, then the path can be 
94        started from any point of the cycle  
95        as the graph is undirected */
96        path[0] = 0; 
97        if (hamCycleUtil(graph, path, 1) == false) 
98        { 
99            Console.WriteLine("\nSolution does not exist"); 
100            return 0; 
101        } 
102  
103        printSolution(path); 
104        return 1; 
105    } 
106  
107    /* A utility function to print solution */
108    void printSolution(int []path) 
109    { 
110        Console.WriteLine("Solution Exists: Following" + 
111                        " is one Hamiltonian Cycle"); 
112        for (int i = 0; i < V; i++) 
113            Console.Write(" " + path[i] + " "); 
114  
115        // Let us print the first vertex again 
116        //  to show the complete cycle 
117        Console.WriteLine(" " + path[0] + " "); 
118    } 
119  
120    // Driver code 
121    public static void Main(String []args) 
122    { 
123        HamiltonianCycle hamiltonian = 
124                                new HamiltonianCycle(); 
125        /* Let us create the following graph 
126        (0)--(1)--(2) 
127            | / \ | 
128            | / \ | 
129            | /     \ | 
130        (3)-------(4) */
131        int [,]graph1= {{0, 1, 0, 1, 0}, 
132            {1, 0, 1, 1, 1}, 
133            {0, 1, 0, 0, 1}, 
134            {1, 1, 0, 0, 1}, 
135            {0, 1, 1, 1, 0}, 
136        }; 
137  
138        // Print the solution 
139        hamiltonian.hamCycle(graph1); 
140  
141        /* Let us create the following graph 
142        (0)--(1)--(2) 
143            | / \ | 
144            | / \ | 
145            | /     \ | 
146        (3)     (4) */
147        int [,]graph2 = {{0, 1, 0, 1, 0}, 
148            {1, 0, 1, 1, 1}, 
149            {0, 1, 0, 0, 1}, 
150            {1, 1, 0, 0, 0}, 
151            {0, 1, 1, 0, 0}, 
152        }; 
153  
154        // Print the solution 
155        hamiltonian.hamCycle(graph2); 
156    } 
157} 
158  
159// 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» تغییر پیدا کند.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۴ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeks
نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *