गहराई पहली खोज (DFS) एल्गोरिथम

विषय - सूची

गहराई पहली खोज एल्गोरिथम
गहराई पहली खोज उदाहरण
DFS स्यूडोकोड (पुनरावर्ती कार्यान्वयन)
पायथन, जावा और सी / सी ++ में डीएफएस कार्यान्वयन
गहराई पहली खोज की जटिलता
डीएफएस एल्गोरिथ्म का अनुप्रयोग

इस ट्यूटोरियल में, आप उदाहरणों और स्यूडोकोड के साथ गहराई से पहले खोज एल्गोरिथ्म के बारे में जानेंगे। इसके अलावा, आप सी, जावा, पायथन और सी ++ में डीएफएस लागू करना सीखेंगे।

डेप्थ फर्स्ट सर्च या डेप्थ फर्स्ट ट्रैवर्सल एक ग्राफ या ट्री डेटा संरचना के सभी कोने की खोज के लिए एक पुनरावर्ती एल्गोरिदम है। ट्रैवर्सल का अर्थ है ग्राफ के सभी नोड्स पर जाना।

गहराई पहली खोज एल्गोरिथम

एक मानक डीएफएस कार्यान्वयन ग्राफ के प्रत्येक शीर्ष को दो श्रेणियों में से एक में रखता है:

का दौरा किया
देखा नहीं गया

एल्गोरिथ्म का उद्देश्य चक्रों से बचने के दौरान दौरा किए गए प्रत्येक शीर्ष को चिह्नित करना है।

DFS एल्गोरिथ्म निम्नानुसार काम करता है:

स्टैक के शीर्ष पर ग्राफ़ के किसी एक कोने को रखकर शुरू करें।
स्टैक का शीर्ष आइटम लें और इसे विज़िट की गई सूची में जोड़ें।
उस शीर्ष के आसन्न नोड्स की एक सूची बनाएं। उन लोगों को जोड़ें जो स्टैक के शीर्ष पर विज़िट की गई सूची में नहीं हैं।
स्टैक खाली होने तक चरण 2 और 3 दोहराते रहें।

गहराई पहली खोज उदाहरण

आइए देखें कि डेप्थ फर्स्ट सर्च एल्गोरिदम एक उदाहरण के साथ कैसे काम करता है। हम 5 कोने के साथ एक अप्रत्यक्ष ग्राफ का उपयोग करते हैं।

5 कोने के साथ अप्रत्यक्ष ग्राफ

हम वर्टेक्स 0 से शुरू करते हैं, डीएफएस एल्गोरिथ्म इसे विज़ि‍टेड लिस्ट में डालकर और इसके आस-पास के सभी वर्टिकल को स्टैक में रखकर शुरू होता है।

तत्व पर जाएँ और इसे विज़िट की गई सूची में डालें

इसके बाद, हम तत्व को स्टैक के शीर्ष पर अर्थात 1 पर जाते हैं और उसके निकटवर्ती नोड्स पर जाते हैं। चूँकि 0 का दौरा हो चुका है, इसलिए हम 2 के बजाय जाते हैं।

स्टैक के शीर्ष पर स्थित तत्व पर जाएँ

वर्टेक्स 2 में 4 में एक गैर-समीपवर्ती शीर्ष है, इसलिए हम इसे स्टैक के शीर्ष पर जोड़ते हैं और इसे देखते हैं।

जब हम अंतिम तत्व 3 पर जाते हैं, तो इसमें कोई भी समीपस्थ नोड नहीं होता है, इसलिए हमने ग्राफ के डेप्थ फर्स्ट ट्रैवर्सल को पूरा कर लिया है।

DFS स्यूडोकोड (पुनरावर्ती कार्यान्वयन)

डीएफएस के लिए छद्म कोड नीचे दिखाया गया है। Init () फ़ंक्शन में, ध्यान दें कि हम प्रत्येक नोड पर DFS फ़ंक्शन चलाते हैं। ऐसा इसलिए है क्योंकि ग्राफ़ में दो अलग-अलग डिस्कनेक्ट किए गए भाग हो सकते हैं ताकि यह सुनिश्चित हो सके कि हम प्रत्येक शीर्ष को कवर करते हैं, हम हर नोड पर डीएफएस एल्गोरिथ्म भी चला सकते हैं।

 DFS (G, u) u.visited = प्रत्येक v each के लिए सच है। यू ∈ जी डीएफएस (जी, यू))

पायथन, जावा और सी / सी ++ में डीएफएस कार्यान्वयन

एक उदाहरण के साथ गहराई पहली खोज एल्गोरिदम का कोड नीचे दिखाया गया है। कोड को सरल बनाया गया है ताकि हम अन्य विवरणों के बजाय एल्गोरिथ्म पर ध्यान केंद्रित कर सकें।

पायथन जावा सी सी +

 # DFS algorithm in Python # DFS algorithm def dfs(graph, start, visited=None): if visited is None: visited = set() visited.add(start) print(start) for next in graph(start) - visited: dfs(graph, next, visited) return visited graph = ('0': set(('1', '2')), '1': set(('0', '3', '4')), '2': set(('0')), '3': set(('1')), '4': set(('2', '3'))) dfs(graph, '0')

 // DFS algorithm in Java import java.util.*; class Graph ( private LinkedList adjLists(); private boolean visited(); // Graph creation Graph(int vertices) ( adjLists = new LinkedList(vertices); visited = new boolean(vertices); for (int i = 0; i < vertices; i++) adjLists(i) = new LinkedList(); ) // Add edges void addEdge(int src, int dest) ( adjLists(src).add(dest); ) // DFS algorithm void DFS(int vertex) ( visited(vertex) = true; System.out.print(vertex + " "); Iterator ite = adjLists(vertex).listIterator(); while (ite.hasNext()) ( int adj = ite.next(); if (!visited(adj)) DFS(adj); ) ) public static void main(String args()) ( Graph g = new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 3); System.out.println("Following is Depth First Traversal"); g.DFS(2); ) )

 // DFS algorithm in C #include #include struct node ( int vertex; struct node* next; ); struct node* createNode(int v); struct Graph ( int numVertices; int* visited; // We need int** to store a two dimensional array. // Similary, we need struct node** to store an array of Linked lists struct node** adjLists; ); // DFS algo void DFS(struct Graph* graph, int vertex) ( struct node* adjList = graph->adjLists(vertex); struct node* temp = adjList; graph->visited(vertex) = 1; printf("Visited %d ", vertex); while (temp != NULL) ( int connectedVertex = temp->vertex; if (graph->visited(connectedVertex) == 0) ( DFS(graph, connectedVertex); ) temp = temp->next; ) ) // Create a node struct node* createNode(int v) ( struct node* newNode = malloc(sizeof(struct node)); newNode->vertex = v; newNode->next = NULL; return newNode; ) // Create graph struct Graph* createGraph(int vertices) ( struct Graph* graph = malloc(sizeof(struct Graph)); graph->numVertices = vertices; graph->adjLists = malloc(vertices * sizeof(struct node*)); graph->visited = malloc(vertices * sizeof(int)); int i; for (i = 0; i adjLists(i) = NULL; graph->visited(i) = 0; ) return graph; ) // Add edge void addEdge(struct Graph* graph, int src, int dest) ( // Add edge from src to dest struct node* newNode = createNode(dest); newNode->next = graph->adjLists(src); graph->adjLists(src) = newNode; // Add edge from dest to src newNode = createNode(src); newNode->next = graph->adjLists(dest); graph->adjLists(dest) = newNode; ) // Print the graph void printGraph(struct Graph* graph) ( int v; for (v = 0; v numVertices; v++) ( struct node* temp = graph->adjLists(v); printf(" Adjacency list of vertex %d ", v); while (temp) ( printf("%d -> ", temp->vertex); temp = temp->next; ) printf(""); ) ) int main() ( struct Graph* graph = createGraph(4); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 1, 2); addEdge(graph, 2, 3); printGraph(graph); DFS(graph, 2); return 0; )

 // DFS algorithm in C++ #include #include using namespace std; class Graph ( int numVertices; list *adjLists; bool *visited; public: Graph(int V); void addEdge(int src, int dest); void DFS(int vertex); ); // Initialize graph Graph::Graph(int vertices) ( numVertices = vertices; adjLists = new list(vertices); visited = new bool(vertices); ) // Add edges void Graph::addEdge(int src, int dest) ( adjLists(src).push_front(dest); ) // DFS algorithm void Graph::DFS(int vertex) ( visited(vertex) = true; list adjList = adjLists(vertex); cout << vertex << " "; list::iterator i; for (i = adjList.begin(); i != adjList.end(); ++i) if (!visited(*i)) DFS(*i); ) int main() ( Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 3); g.DFS(2); return 0; )