Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Java

ग्राफ डेटा स्ट्रक्चर लागू करने के लिए Java प्रोग्राम


इस लेख में, हम समझेंगे कि ग्राफ डेटा स्ट्रक्चर कैसे लागू करें। हम Java में HashMap संग्रह का उपयोग करके ग्राफ डेटा स्ट्रक्चर लागू करते हैं। HashMap एलिमेंट्स कुंजी-मान जोड़े के रूप में होते हैं। हम ग्राफ एडजेसेंसी लिस्ट को HashMap में प्रस्तुत कर सकते हैं।

नीचे इसका प्रदर्शन है:

मान लीजिए हमारा इनपुट है:

वर्टेक्स की संख्या: 5
एज की संख्या: 5

वांछित आउटपुट होगा:

ग्राफ के नोड्स के बीच कनेक्शन हैं:
1 - 2
1 - 3
1 - 4
2 - 4
2 - 5
3 - 4
3 - 5
4 - 5

एल्गोरिदम

चरण 1 - शुरू
चरण 2 - Graph क्लास का एक ऑब्जेक्ट घोषित करें जिसका नाम graph_object हो, 'Edge' क्लास में दो इंटीजर्स source और destination, और 'main' फंक्शन में दो इंटीजर्स vertices_count, edges_count
चरण 3 - मान परिभाषित करें
चरण 4 - वर्टेक्स और काउंट के लिए मान इनिशियलाइज़ करें
चरण 5 - पहले से परिभाषित क्लास का नया इंस्टेंस बनाएं
चरण 6 - इंस्टेंस को प्रासंगिक मानों से इनिशियलाइज़ करें
चरण 7 - 'for' लूप का उपयोग करके इंस्टेंस पर इटरेट करें, और कंसोल पर आउटपुट प्रदर्शित करें
चरण 8 - परिणाम प्रदर्शित करें
चरण 9 - रुकें

उदाहरण 1: एज लिस्ट प्रतिनिधित्व

यहाँ, हम सभी ऑपरेशन्स को 'main' फंक्शन के तहत बांधते हैं।

public class Graph {
    class Edge {
        int source, destination;
    }
    
    int vertices, edges;
    Edge[] edge;
    
    Graph(int vertices, int edges) {
        this.vertices = vertices;
        this.edges = edges;
        edge = new Edge[edges];
        for (int i = 0; i < edges; i++) {
            edge[i] = new Edge();
        }
    }
    
    public static void main(String[] args) {
        int vertices_count = 5;
        int edges_count = 8;
        Graph graph_object = new Graph(vertices_count, edges_count);
        System.out.println("एक ग्राफ ऑब्जेक्ट परिभाषित है।");
        
        graph_object.edge[0].source = 1;
        graph_object.edge[0].destination = 2;
        graph_object.edge[1].source = 1;
        graph_object.edge[1].destination = 3;
        graph_object.edge[2].source = 1;
        graph_object.edge[2].destination = 4;
        graph_object.edge[3].source = 2;
        graph_object.edge[3].destination = 4;
        graph_object.edge[4].source = 2;
        graph_object.edge[4].destination = 5;
        graph_object.edge[5].source = 3;
        graph_object.edge[5].destination = 4;
        graph_object.edge[6].source = 3;
        graph_object.edge[6].destination = 5;
        graph_object.edge[7].source = 4;
        graph_object.edge[7].destination = 5;
        
        System.out.println("ग्राफ के एज के बीच कनेक्शन हैं: ");
        for (int i = 0; i < edges_count; i++) {
            System.out.println(graph_object.edge[i].source + " - " + graph_object.edge[i].destination);
        }
    }
}

आउटपुट

एक ग्राफ ऑब्जेक्ट परिभाषित है।
ग्राफ के एज के बीच कनेक्शन हैं:
1 - 2
1 - 3
1 - 4
2 - 4
2 - 5
3 - 4
3 - 5
4 - 5

उदाहरण 2: एडजेसेंसी लिस्ट (HashMap) प्रतिनिधित्व

यहाँ, हम ऑपरेशन्स को फंक्शन्स में एनकैप्सुलेट करते हैं जो ऑब्जेक्ट-ओरिएंटेड प्रोग्रामिंग प्रदर्शित करते हैं।

import java.util.*;

public class Graph {
    private Map> adjList;
    private int vertices;
    
    Graph(int vertices) {
        this.vertices = vertices;
        adjList = new HashMap<>();
        for (int i = 1; i <= vertices; i++) {
            adjList.put(i, new ArrayList<>());
        }
    }
    
    void addEdge(int src, int dest) {
        adjList.get(src).add(dest);
        adjList.get(dest).add(src); // अनडायरेक्टेड ग्राफ के लिए
    }
    
    void printGraph() {
        System.out.println("ग्राफ की एडजेसेंसी लिस्ट:");
        for (int i = 1; i <= vertices; i++) {
            System.out.print(i + " -> ");
            for (int neighbor : adjList.get(i)) {
                System.out.print(neighbor + " ");
            }
            System.out.println();
        }
    }
    
    static void connect_edges(Graph graph_object) {
        graph_object.addEdge(1, 2);
        graph_object.addEdge(1, 3);
        graph_object.addEdge(1, 4);
        graph_object.addEdge(2, 4);
        graph_object.addEdge(2, 5);
        graph_object.addEdge(3, 4);
        graph_object.addEdge(3, 5);
        graph_object.addEdge(4, 5);
    }
    
    public static void main(String[] args) {
        int vertices_count = 5;
        Graph graph_object = new Graph(vertices_count);
        System.out.println("एक ग्राफ ऑब्जेक्ट परिभाषित है।");
        connect_edges(graph_object);
        graph_object.printGraph();
    }
}

आउटपुट

एक ग्राफ ऑब्जेक्ट परिभाषित है।
ग्राफ की एडजेसेंसी लिस्ट:
1 -> 2 3 4
2 -> 1 4 5
3 -> 1 4 5
4 -> 1 2 3 5
5 -> 2 3 4

ग्राफ प्रतिनिधित्व तुलना

प्रतिनिधित्वस्पेसएज चेकनेबर्स इटरेशनसर्वश्रेष्ठ लिए
एडजेसेंसी मैट्रिक्सO(V²)O(1)O(V)घने ग्राफ, फ्रीक्वेंट एज लुकअप
एडजेसेंसी लिस्ट (Array)O(V+E)O(deg(V))O(deg(V))विरल ग्राफ, मेमोरी एफिशिएंट
एडजेसेंसी लिस्ट (HashMap)O(V+E)O(1) औसतO(deg(V))डायनामिक वर्टेक्स, स्पार्स ग्राफ
एज लिस्टO(E)O(E)O(E)सिंपल एल्गोरिदम (क्रुस्कल)

सामान्य ग्राफ एल्गोरिदम

  • BFS/DFS: ट्रैवर्सल, पाथ फाइंडिंग, साइकिल डिटेक्शन
  • डिज्क्स्ट्रा: भारित ग्राफ में सबसे छोटा पथ
  • टोपोलॉजिकल सॉर्ट: DAG के लिए निर्भरता समाधान
  • यूनियन-फाइंड: कनेक्टेड कंपोनेंट्स, साइकिल डिटेक्शन
  1. Java प्रोग्राम: ट्रैपेज़ियम (Trapezium) का क्षेत्रफल ज्ञात करें Java प्रोग्राम: ट्रैपेज़ियम (Trapezium) का क्षेत्रफल ज्ञात करें

    इस लेख में, हम समझेंगे कि ट्रैपेज़ियम का क्षेत्रफल कैसे ज्ञात करें। ट्रैपेज़ियम एक प्रकार का चतुर्भुज है जिसमें कम से कम एक जोड़ी भुजाएं एक-दूसरे के समानांतर होती हैं। ट्रैपेज़ियम की समानांतर भुजाओं को बेस कहा जाता है और असमानांतर भुजाओं को लेग्स कहा जाता है। इसे ट्रेपेजॉयड भी कहा जाता है।ट्रैपेज़िय

  1. जावा प्रोग्राम से आयत का परिमाप (Perimeter of Rectangle) निकालना जावा प्रोग्राम से आयत का परिमाप (Perimeter of Rectangle) निकालना

    इस लेख में हम समझेंगे कि आयत का परिमाप कैसे निकाला जाता है। आयत का परिमाप आयत की सभी भुजाओं की लंबाई को जोड़कर निकाला जाता है। नीचे एक आयत का प्रदर्शन दिया गया है। आयत का परिमाप आयत की दो लंबाई और दो चौड़ाई की कुल लंबाई होती है: इनपुट मान लीजिए हमारा इनपुट है: आयत की भुजाओं की लंबाई हैं: 5, 8, 5,

  1. Java में संख्या गिनने का प्रोग्राम कैसे लागू करें? Java में संख्या गिनने का प्रोग्राम कैसे लागू करें?

    प्रोग्राम एक JLabel का उपयोग काउंट लेबल रखने के लिए करता है, एक JTextField घटक संख्या काउंट रखने के लिए, JButton घटक जोड़ें, हटाएं और रीसेट बटन बनाने के लिए। जब हम ऐड बटन पर क्लिक करते हैं, तो JTextField में काउंट 1 से बढ़ जाता है और रिमूव बटन पर क्लिक करके काउंट 1 से घट जाता है। यदि हम रीसेट बटन प