ट्री और ग्राफ

Python में Data Structures और Algorithms

Miriam Antona

Software engineer

ट्री - परिभाषा

नोड्स वाला एक ट्री.

नोड-आधारित डेटा स्ट्रक्चर
हर नोड के एक से अधिक नोड्स से लिंक्स हो सकते हैं.

ट्री - शब्दावली

नोड्स वाला एक ट्री. रूट नोड पीला है.

ट्री - शब्दावली

नोड्स वाला एक ट्री. रूट नोड पीला है. एक पेरेंट नोड नारंगी है.

ट्री - शब्दावली

नोड्स वाला एक ट्री. रूट नोड पीला है. एक पेरेंट नोड नारंगी है और उसके बच्चे हरे हैं.

ट्री - शब्दावली

नोड्स वाला एक ट्री.

ट्री - शब्दावली

नोड्स और अलग-अलग लेवल्स वाला एक ट्री.

ट्री - बाइनरी ट्री

एक बाइनरी ट्री का चित्रात्मक निरूपण.

हर नोड के पास:
- शून्य बच्चे
- एक बच्चा
- दो बच्चे

ट्री - बाइनरी ट्री इम्प्लीमेंटेशन

class TreeNode:

  def __init__(self, data, left=None, right=None):
    self.data = data
    self.left_child = left
    self.right_child = right

नोड्स वाला एक ट्री.

node1 = TreeNode("B")
node2 = TreeNode("C")
root_node = TreeNode("A", node1, node2)

ट्री - वास्तविक उपयोग

हरेकिकल रिलेशनशिप स्टोर करना
- कंप्यूटर का फाइल सिस्टम
- HTML डॉक्युमेंट की संरचना
चेस: प्रतिद्वंद्वी की संभावित चालें
सर्चिंग और सॉर्टिंग एल्गोरिदम

ग्राफ

नोड्स वाला एक ग्राफ.

समुच्चय:
- नोड्स/वर्टिसेज
- लिंक्स/एजेज
ट्री, ग्राफ का एक प्रकार हैं

ग्राफ - प्रकार

डायरेक्टेड ग्राफ:
- विशिष्ट दिशा

डायरेक्टेड ग्राफ का चित्र.

ग्राफ - प्रकार

अनडायरेक्टेड ग्राफ:
- एजेज की कोई दिशा नहीं होती
- रिलेशनशिप द्विपक्षीय होता है

अनडायरेक्टेड ग्राफ का चित्र.

ग्राफ - प्रकार

वेटेड ग्राफ:
- एजेज से जुड़े संख्यात्मक मान
- डायरेक्टेड भी हो सकते हैं या अनडायरेक्टेड भी

कई शहरों के नाम और उनके बीच की दूरी वाला अनडायरेक्टेड ग्राफ.

ग्राफ बनाम ट्री

ट्री

साइकल्स नहीं होते
सभी नोड्स कनेक्टेड होने चाहिए

नोड्स वाला एक ट्री.

ग्राफ

साइकल्स हो सकते हैं
अनकनेक्टेड नोड्स हो सकते हैं

नोड्स वाला एक ग्राफ.

ग्राफ बनाम ट्री

ट्री

साइकल्स नहीं होते
सभी नोड्स कनेक्टेड होने चाहिए

नोड्स वाला एक ट्री.

ग्राफ

साइकल्स हो सकते हैं
अनकनेक्टेड नोड्स हो सकते हैं

नोड्स वाला एक ग्राफ. एक नोड बाकी से कनेक्टेड नहीं है.

ग्राफ - वास्तविक उपयोग मामले

सोशल नेटवर्क्स में यूज़र रिलेशनशिप्स
- फ्रेंडशिप
- फॉलोज़
- लाइक्स
- आदि
लोकेशंस और डिस्टेंसेज़
- रूट्स को ऑप्टिमाइज़ करें
ग्राफ डेटाबेस
सर्चिंग और सॉर्टिंग एल्गोरिदम

ग्राफ - इम्प्लीमेंटेशन

class Graph:
  def__init(self):
    self.vertices = {}

  def add_vertex(self, vertex):
    self.vertices[vertex] = []

  def add_edge(self, source, target):    
    self.vertices[source].append(target)

डायरेक्टेड ग्राफ का चित्र.

my_graph = Graph()
my_graph.add_vertex('David')
my_graph.add_vertex('Miriam')
my_graph.add_vertex('Martin')

my_graph.add_edge('David', 'Miriam')
my_graph.add_edge('David', 'Martin')
my_graph.add_edge('Miriam', 'Martin')

print(my_graph.vertices)

{
  'David' : ['Miriam','Martin'],
  'Miriam' : ['Martin'],
  'Martin' : []
}

अभ्यास करते हैं!

Python में Data Structures और Algorithms