इस लेख में, हम समझेंगे कि ग्राफ डेटा स्ट्रक्चर कैसे लागू करें। हम 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 के लिए निर्भरता समाधान
- यूनियन-फाइंड: कनेक्टेड कंपोनेंट्स, साइकिल डिटेक्शन