close

ग्राफ खोज (Graph Search) एल्गोरिदम मा Java

ग्राफ खोज एल्गोरिदम Java एक ग्राफ भित्र ठाडो वा किनाराहरू खोज्न प्रयोग गरिने प्रोग्रामिङमा एक आवश्यक प्रविधि हो। ग्राफ भनेको किनारहरूद्वारा जोडिएका ठाडोहरूको सङ्ग्रह हो। यो एल्गोरिथ्म प्रायः समस्याहरूमा लागू हुन्छ जस्तै छोटो बाटो खोज्ने, तत्वहरू बीच जडानहरू खोज्ने, र नेटवर्कहरू विश्लेषण गर्ने।

कसरी ग्राफ खोज एल्गोरिदम काम गर्दछ

ग्राफ खोज एल्गोरिदममा बिभिन्न विधिहरू छन्, जस्तै ब्रेडथ-फर्स्ट सर्च(BFS) र डेप्थ-फर्स्ट सर्च(DFS)। यी दुवै विधिहरूमा लक्ष्य वा आवश्यक अवस्था पत्ता लगाउन ग्राफ भित्रको ठेगाना र किनाराहरू पार गर्ने समावेश छ।

  • Breadth-First Search(BFS) ले पहिले रूट भेर्टेक्स पार गर्छ र त्यसपछि टाढाको ठाडोहरूमा जानु अघि छिमेकी ठाडोहरू अन्वेषण गर्दछ।
  • Depth-First Search(DFS) ले प्रत्येक vertex को अन्वेषण गर्छ र गन्तव्य फेला नपरेसम्म वा थप अन्वेषण सम्भव नभएसम्म गहिराइ-पहिलो खोजी गर्छ।

ग्राफ खोज एल्गोरिथ्मका फाइदाहरू र हानिहरू

फाइदा:

  • जडानहरू खोज्दै: यो एल्गोरिदमले ग्राफमा ठाडोहरू बीचको जडानहरू पहिचान गर्न मद्दत गर्दछ, जुन सबैभन्दा छोटो मार्गहरू वा तत्वहरू बीचको सम्बन्धहरू फेला पार्न उपयोगी छ।
  • द्रुत खोज क्षमता: ग्राफको संरचनामा निर्भर गर्दै, एल्गोरिदमले द्रुत रूपमा लक्ष्य खोज्न सक्छ।

बेफाइदाहरू:

  • हराउने सम्भावना: ठूला र जटिल ग्राफहरूको अवस्थामा, एल्गोरिथ्म हराउन वा विचलित हुन सक्छ, जसले समय-उपभोग खोजहरू निम्त्याउँछ।

उदाहरण र व्याख्या

Java ग्राफमा भेर्टिसहरू बीचको छोटो बाटो पत्ता लगाउन ब्रेडथ-फर्स्ट सर्च(BFS) विधि प्रयोग गर्ने उदाहरण प्रयोग गरेर ग्राफ खोज एल्गोरिदमलाई चित्रण गर्नुहोस् । 

import java.util.*;  
  
public class GraphSearchExample {  
    // Class implementation of the graph and BFS here...  
}  
  
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, 0);  
    g.addEdge(2, 3);  
    g.addEdge(3, 3);  
  
    System.out.println("BFS search from vertex 2:");  
    g.BFS(2);  
}

यस उदाहरणमा, हामीले एउटा ग्राफ सिर्जना गर्छौं र भेर्टेक्स २ बाट जोडिएका ठाडोहरू खोज्नको लागि ब्रेडथ-फर्स्ट सर्च(BFS) विधि प्रयोग गर्छौं। परिणाम vertex 2 बाट चौडाइ-पहिलो तरिकामा पार गरिएका ठाडोहरूको अनुक्रम हुनेछ। यो आधारभूत हो। मा ग्राफ खोज एल्गोरिथ्म प्रयोग गरेर ग्राफ भित्र खोजी गर्ने दृष्टिकोण Java ।