अवधारणा
दिए गए ग्राफ के संबंध में, ग्राफ में एक स्रोत शीर्ष और एक संख्या k (यहां k स्रोत शीर्ष और गंतव्य शीर्ष के बीच ग्राफ की पथ लंबाई को इंगित करता है), हमारा कार्य यह निर्धारित करना है कि क्या कोई सरल पथ (बिना किसी चक्र के) शुरुआत है दिए गए स्रोत से और किसी अन्य शीर्ष (अर्थात गंतव्य) पर समाप्त होता है। ग्राफ निम्नलिखित में दिखाया गया है -
इनपुट
Source s = 0, k = 64
आउटपुट
True
एक आसान रास्ता मौजूद है 0 -> 7 -> 1-> 2 -> 8 -> 6 -> 5 -> 3 -> 4, जिसकी कुल दूरी 68 किमी है जो 64 से अधिक है।
इनपुट
Source s = 0, k = 70
आउटपुट
False
उपरोक्त ग्राफ में, सबसे लंबे सरल पथ की दूरी 69 है (0 -> 7 -> 1-> 2 -> 3 -> 4 -> 5-> 6 -> 8, 69 से अधिक इनपुट के लिए आउटपुट गलत होना चाहिए।
विधि
यह ध्यान दिया जाना चाहिए कि एक महत्वपूर्ण बात बस बीएफएस (ब्रेडथ फर्स्ट सर्च) या डीएफएस (डेप्थ फर्स्ट सर्च) कर रही है और हर कदम पर सबसे लंबे किनारे का चयन करने से काम नहीं चलेगा। इसका कारण यह है कि एक छोटा किनारा लंबा रास्ता बना सकता है क्योंकि इसके माध्यम से जुड़े उच्च भार।
अब अवधारणा बैकट्रैकिंग को लागू करने की है। इस मामले में, हम दिए गए स्रोत से शुरू करते हैं; वर्तमान शीर्ष से सभी पथों को पार करें। यहां, हम स्रोत से वर्तमान दूरी का ट्रैक रखते हैं। यह देखा गया है कि यदि दूरी k से अधिक हो जाती है, तो हम सही लौटते हैं। लेकिन विकल्प के मामले में ताकि यदि कोई पथ k दूरी से अधिक का उत्पादन नहीं करता है, तो हम पीछे हट जाते हैं।
अब सवाल यह उठता है कि हम कैसे सुनिश्चित करें कि रास्ता आसान है और हम साइकिल में लूप नहीं करते हैं? यहां अवधारणा एक सरणी में वर्तमान पथ शिखर का ट्रैक बनाए रखना है। इस मामले में, जब भी हम पथ में एक शीर्ष जोड़ते हैं, तो हम सत्यापित करते हैं कि यह पहले से मौजूद है या वर्तमान पथ में नहीं है। यह देखा गया है कि अगर यह मौजूद है, तो हम किनारे को नजरअंदाज कर देते हैं।
उदाहरण
// Program to find if there is a simple path with
// weight more than k
#include<bits/stdc++.h>
using namespace std;
// iPair ==> Integer Pair
typedef pair<int, int> iPair;
// Now this class represents a dipathted graph using
// adjacency list representation
class Graph{
int V1; // Indicates no. of vertices
// In this case, in a weighted graph, we need to store vertex
// and weight pair for every edge
list< pair<int, int>> *adj1;
bool pathMoreThanKUtil(int src1, int k, vector<bool>&path1);
public:
Graph(int V1); // Shows constructor
// Shows function to add an edge to graph
void addEdge(int u1, int v1, int w1);
bool pathMoreThanK(int src1, int k);
};
// Used to return true if graph has path more than k length
bool Graph::pathMoreThanK(int src1, int k){
// Used to create a path array with nothing included
// in path
vector<bool> path1(V1, false);
// Used to add source vertex to path
path1[src1] = 1;
return pathMoreThanKUtil(src1, k, path1);
}
// Used to print shortest paths from src to all other vertices
bool Graph::pathMoreThanKUtil(int src1, int k, vector<bool>&path1){
// Now if k is 0 or negative, return true;
if (k <= 0)
return true;
//Used to get all adjacent vertices of source vertex src and
// recursively explore all paths from src.
list<iPair>::iterator i;
for (i = adj1[src1].begin(); i != adj1[src1].end(); ++i){
// Used to get adjacent vertex and weight of edge
int v1 = (*i).first;
int w1 = (*i).second;
// Now if vertex v is already there in path, then
// there is a cycle (we ignore this edge)
if (path1[v1] == true)
continue;
// Now if weight of is more than k, return true
if (w1 >= k)
return true;
// Else add this vertex to path
path1[v1] = true;
// Now if this adjacent can provide a path longer
// than k, return true.
if (pathMoreThanKUtil(v1, k-w1, path1))
return true;
// Backtrack
path1[v1] = false;
}
// Now if no adjacent could produce longer path, return
// false
return false;
}
// Used to allocates memory for adjacency list
Graph::Graph(int V1){
this->V1 = V1;
adj1 = new list<iPair> [V1];
}
//Shows utility function to an edge (u, v) of weight w
void Graph::addEdge(int u1, int v1, int w1){
adj1[u1].push_back(make_pair(v1, w1));
adj1[v1].push_back(make_pair(u1, w1));
}
// Driver program to test methods of graph class
int main(){
// Used to create the graph given in above fugure
int V1 = 9;
Graph g(V1);
// making above shown graph
g.addEdge(0, 1, 5);
g.addEdge(0, 7, 9);
g.addEdge(1, 2, 9);
g.addEdge(1, 7, 12);
g.addEdge(2, 3, 8);
g.addEdge(2, 8, 3);
g.addEdge(2, 5, 10);
g.addEdge(3, 4, 10);
g.addEdge(3, 5, 15);
g.addEdge(4, 5, 11);
g.addEdge(5, 6, 3);
g.addEdge(6, 7, 2);
g.addEdge(6, 8, 7);
g.addEdge(7, 8, 8);
int src1 = 0;
int k = 70;
g.pathMoreThanK(src1, k)? cout << "Yes\n" :
cout << "No\n";
k = 68;
g.pathMoreThanK(src1, k)? cout << "Yes\n" :
cout << "No\n";
return 0;
} आउटपुट
No Yes