ساختمان داده در پایتون — معرفی جامع انواع داده در پایتون

ساختمان داده در پایتون روشی برای سازمان‌دهی داده‌ها «Data» هستند تا بتوان بر اساس نیاز، آن‌ها را به شکل کارآمدتری مورد دسترسی قرار داد. این ساختمان‌ها پایه و اساس هر زبان برنامه‌نویسی «Programming» را تشکیل می‌دهند و برنامه‌ها بر اساس آن‌ها ساخته می‌شوند.

مقدمه

یادگیری مفاهیم پایه‌ای ساختمان داده در پایتون در مقایسه با سایر زبان‌های برنامه‌نویسی، به شکل ساده‌تری امکان‌پذیر است. در این مقاله، به بررسی ساختمان داده در پایتون و ارتباط آن‌ها با برخی از انواع داده‌ای خاص در پایتون می‌پردازیم و ساختمان داده داخلی مانند لیست‌ها «Lists»، تاپل‌ها «Tuples»، دیکشنری‌ها «Dictionaries» و غیره را بررسی خواهیم کرد، همچنین به برخی از ساختمان داده پیشرفته مانند درخت‌ها «Tree» و گراف‌ها «Graphs» نیز خواهیم پرداخت.

ساختمان داده لیست در پایتون

برای شروع بررسی ساختمان داده در پایتون از لیست List شروع می‌کنیم. ساختمان داده لیست‌ها در پایتون شبیه به آرایه‌ها «Arrays» در سایر زبان‌ها هستند و مجموعه‌ای مرتب از داده‌ها را نگه می‌دارند. این ساختار در پایتون بسیار انعطاف‌پذیر است، زیرا آیتم‌های یک لیست الزامی به داشتن نوع داده‌ای یکسان ندارند. پیاده‌سازی لیست در پایتون مشابه با Vectors در ++C یا ArrayList در Java است. انجام عملیات درج یا حذف یک عنصر از ابتدای لیست هزینه‌بر است، زیرا همه عناصر باید جابه‌جا شوند. همچنین، در مواردی که حافظه‌ی از پیش تخصیص‌یافته پر شود، درج و حذف در انتهای لیست نیز می‌تواند پردازش سنگینی داشته باشد. می‌توان یک لیست را در پایتون به شکل زیر ایجاد کرد.

مثال: ایجاد یک لیست در پایتون

List = [1, 2,  3, "PS", 2.3]
print(List)

خروجی:

[۱, ۲, ۳, 'PS', 2.3]

عناصر یک لیست را می‌توان با استفاده از اندیس اختصاص داده‌شده به آن‌ها دسترسی داشت. در پایتون، اندیس‌گذاری لیست از ۰ شروع می‌شود و اندیس آخرین عنصر (در صورتی که لیست N عنصر داشته باشد) N-1 خواهد بود.

مثال: عملیات روی لیست در پایتون

# Creating a List with 
# the use of multiple values 
List = ["Program", "Store"] 
print("\nList containing multiple values: ") 
print(List)

# Creating a Multi-Dimensional List 
# (By Nesting a list inside a List) 
List2 = [['Program'], ['Store']] 
print("\nMulti-Dimensional List: ") 
print(List2) 

# accessing a element from the  
# list using index number 
print("Accessing element from the list") 
print(List[0])  
print(List[2]) 

# accessing a element using 
# negative indexing 
print("Accessing element using negative indexing") 
    
# print the last element of list 
print(List[-1]) 
    
# print the third last element of list  
print(List[-3]) 

خروجی:

List containing multiple values: 
['Program', 'Store']

Multi-Dimensional List: 
[['Program'], ['Store']]
Accessing element from the list
Program
Program
Accessing element using negative indexing
Program
Program

ساختمان داده دیکشنری در پایتون

ساختمان داده دیکشنری در پایتون مشابه hash table در سایر زبان‌ها است و دارای پیچیدگی زمانی O(1) می‌باشد. این ساختمان داده، مجموعه‌ای نامرتب از داده‌ها است که برای ذخیره‌سازی مقادیر به‌صورت کلید مقدار استفاده می‌شود. برخلاف سایر انواع داده که تنها یک مقدار را به‌عنوان عنصر نگه می‌دارند، دیکشنری از این روش برای بهینه‌تر شدن استفاده می‌کند.

ایندکس‌گذاری در دیکشنری‌های پایتون با استفاده از کلیدها انجام می‌شود. کلیدها باید از نوع hashable باشند، یعنی اشیایی که تغییرپذیر نیستند، مانند رشته‌ها، اعداد، تاپل‌ها و غیره. می‌توان یک دیکشنری را با استفاده از آکولاد ({}) یا Dictionary Comprehension ایجاد کرد.

مثال: عملیات روی دیکشنری در پایتون

# Creating a Dictionary
Dict = {'Name': 'Program', 1: [1, 2, 3, 4]}
print("Creating Dictionary: ")
print(Dict)

# accessing a element using key 
print("Accessing a element using key:") 
print(Dict['Name']) 

# accessing a element using get() 
# method 
print("Accessing a element using get:") 
print(Dict.get(1)) 

# creation using Dictionary comprehension
myDict = {x: x**2 for x in [1,2,3,4,5]}
print(myDict)

خروجی:

Creating Dictionary: 
{'Name': 'Program', 1: [1, 2, 3, 4]}
Accessing a element using key:
Geeks
Accessing a element using get:
[۱, ۲, ۳, ۴]
{۱: ۱, ۲: ۴, ۳: ۹, ۴: ۱۶, ۵: ۲۵}

ساختمان داده تاپل در پایتون

ساختمان داده تاپل در پایتون مجموعه‌ای از اشیا است که مشابه لیست عمل می‌کند، اما تغییرناپذیر است، یعنی پس از ایجاد، امکان افزودن یا حذف عناصر آن وجود ندارد. مانند لیست، تاپل نیز می‌تواند شامل عناصر با انواع مختلف باشد. در پایتون، تاپل با قرار دادن یک دنباله از مقادیر، که با ویرگول (،) از هم جدا شده‌اند، ساخته می‌شود. این کار می‌تواند با یا بدون پرانتز انجام شود.

نکته: تاپل‌های تک‌عضوی «Single-member tuple» هم امکان‌پذیر هستند، اما تعریف آن‌ها کمی متفاوت است. داشتن یک مقدار درون پرانتز کافی نیست، بلکه باید یک ویرگول در انتها قرار داده شود تا پایتون آن را به‌عنوان یک تاپل تشخیص دهد.

مثال: عملیات روی تاپل در پایتون

# Creating a Tuple with
# the use of Strings
Tuple = ('Program', 'For')
print("\nTuple with the use of String: ")
print(Tuple)
    
# Creating a Tuple with
# the use of list
list1 = [1, 2, 4, 5, 6]
print("\nTuple using List: ")
Tuple = tuple(list1)

# Accessing element using indexing
print("First element of tuple")
print(Tuple[0])

# Accessing element from last
# negative indexing
print("\nLast element of tuple")
print(Tuple[-1])
  
print("\nThird last element of tuple")
print(Tuple[-3])

خروجی:

Tuple with the use of String: 
('Program', 'Store')

Tuple using List: 
First element of tuple
۱

Last element of tuple
۶

Third last element of tuple
۴

ساختمان داده مجموعه در پایتون

ساختمان داده مجموعه در پایتون یک ساختمان داده‌ی بدون ترتیب است که قابلیت تغییر دارد و از ورود عناصر تکراری جلوگیری می‌کند. مجموعه‌ها بیشتر برای بررسی عضویت عناصر و حذف موارد تکراری استفاده می‌شوند. در این ساختمان داده از هشینگ استفاده می‌شود که یک روش کارآمد برای درج، حذف و پیمایش عناصر با میانگین زمان اجرای O(1) است.

اگر چند مقدار در یک موقعیت شاخص (ایندکس) یکسان قرار بگیرند، این مقادیر در همان شاخص به صورت لیست پیوندی «Linked List» ذخیره می‌شوند. در CPython، مجموعه‌ها با استفاده از دیکشنری پیاده‌سازی می‌شوند که دارای متغیرهای کمکی هستند. در این روش، کلیدها اعضای مجموعه را تشکیل می‌دهند و با بهینه‌سازی‌هایی، پیچیدگی زمانی بهبود پیدا می‌کند.

پیاده‌سازی مجموعه:مجموعه‌ها با عملیات متعدد روی یک جدول هش:مثال: عملیات روی مجموعه در پایتون

# Creating a Set with  
# a mixed type of values 
# (Having numbers and strings) 
Set = set([1, 2, 'Program', 4, 'Store', 6, 'Tabriz']) 
print("\nSet with the use of Mixed Values") 
print(Set) 

# Accessing element using 
# for loop 
print("\nElements of set: ") 
for i in Set: 
    print(i, end =" ") 
print()

# Checking the element 
# using in keyword 
print("Program" in Set) 

خروجی:

Set with the use of Mixed Values
{۱, ۲, 'Program', 4, 6, 'For'}

Elements of set: 
۱ ۲ Program 4 6 For 
True

مجموعه‌ های ثابت در پایتون

مجموعه‌های ثابت در پایتون غیرقابل تغییر «Immutable» هستند و فقط از روش‌ها و عملگرهایی پشتیبانی می‌کنند که بدون تغییر مجموعه، نتیجه‌ای تولید می‌کنند. در حالی که عناصر یک مجموعه معمولی در هر زمان قابل تغییر هستند، عناصر یک مجموعه ثابت پس از ایجاد شدن بدون تغییر باقی می‌مانند.

اگر هیچ پارامتری به آن داده نشود، یک مجموعه ثابت خالی برمی‌گرداند.

# Same as {"a", "b","c"}
normal_set = set(["a", "b","c"])

print("Normal Set")
print(normal_set)

# A frozen set
frozen_set = frozenset(["e", "f", "g"])

print("\nFrozen Set")
print(frozen_set)

# Uncommenting below line would cause error as
# we are trying to add element to a frozen set
# frozen_set.add("h")

خروجی:

Normal Set
{'a', 'c', 'b'}

Frozen Set
frozenset({'g', 'e', 'f'})

ساختمان داده رشته در پایتون

ساختمان داده رشته‌ در پایتون آرایه‌ای از بایت‌ها هستند که کاراکترهای یونیکد را نمایش می‌دهند. به زبان ساده، یک رشته آرایه‌ای غیرقابل تغییر «Immutable» از کاراکترها است. پایتون نوع داده‌ای مخصوص کاراکتر ندارد، بنابراین یک کاراکتر تنها یک رشته با طول ۱ محسوب می‌شود.

نکته: از آنجا که رشته‌ها تغییرناپذیر هستند، هر گونه تغییر در یک رشته باعث ایجاد یک نسخه‌ی جدید از آن می‌شود.مثال: عملیات روی رشته‌ها در پایتون

String = "Welcome to ProgramStore"
print("Creating String: ") 
print(String) 
    
# Printing First character 
print("\nFirst character of String is: ") 
print(String[0]) 
    
# Printing Last character 
print("\nLast character of String is: ") 
print(String[-1]) 

خروجی:

Creating String: 
Welcome to ProgramStore

First character of String is: 
W

Last character of String is: 
s

ساختمان داده Bytearray در پایتون

ساختمان داده Bytearray در پایتون یک دنباله‌ی قابل تغییر «Mutable» از اعداد صحیح در بازه‌ی ۰ تا ۲۵۵ است.

مثال: عملیات روی Bytearray در پایتون

# Creating bytearray
a = bytearray((12, 8, 25, 2))
print("Creating Bytearray:")
print(a)

# accessing elements
print("\nAccessing Elements:", a[1])

# modifying elements 
a[1] = 3
print("\nAfter Modifying:")
print(a)

# Appending elements
a.append(30)
print("\nAfter Adding Elements:")
print(a)

خروجی:

Creating Bytearray:
bytearray(b'\x0c\x08\x19\x02')

Accessing Elements: 8

After Modifying:
bytearray(b'\x0c\x03\x19\x02')

After Adding Elements:
bytearray(b'\x0c\x03\x19\x02\x1e')

ماژول Collections در پایتون

ماژول collections در پایتون برای بهبود عملکرد انواع داده‌ای داخلی معرفی شده است. این ماژول مجموعه‌ای از ظرفیت‌های داده‌ای را ارائه می‌دهد که در بسیاری از موارد کاربردی هستند و ویژگی‌های بیشتری نسبت به توابع تعریف‌شده قبلی دارند.

کانترها در پایتون

کانتر «Counters» یک زیرکلاس از دیکشنری است که برای نگهداری تعداد عناصر در یک دنباله «iterable» استفاده می‌شود. این کانترها به صورت یک دیکشنری بدون ترتیب عمل می‌کنند که در آن کلیدها نمایانگر عناصر دنباله و مقادیر نشان‌دهنده تعداد آن عنصر در دنباله هستند. این مشابه مفهوم کیسه «bag» یا مجموعه چندتایی «multiset» در زبان‌های دیگر است.

مثال: عملیات روی Counter در پایتون

from collections import Counter
  
# With sequence of items 
print(Counter(['B','B','A','B','C','A','B','B','A','C']))
  
# with dictionary
count = Counter({'A':3, 'B':5, 'C':2})
print(count)

count.update(['A', 1])
print(count)

خروجی:

Counter({'B': 5, 'A': 3, 'C': 2})
Counter({'B': 5, 'A': 3, 'C': 2})
Counter({'B': 5, 'A': 4, 'C': 2, 1: 1})

OrderedDict در پایتون

یک OrderedDict نیز زیرکلاس دیکشنری است، اما برخلاف دیکشنری معمولی، ترتیب وارد شدن کلیدها را به خاطر می‌سپارد. به این معنا که زمانی که کلیدها وارد می‌شوند، ترتیب آن‌ها در OrderedDict حفظ می‌شود.

مثال: عملیات روی OrderedDict در پایتون

from collections import OrderedDict

print("Before deleting:\n")
od = OrderedDict()
od['a'] = 1
od['b'] = 2
od['c'] = 3
od['d'] = 4

for key, value in od.items():
    print(key, value)

print("\nAfter deleting:\n")
od.pop('c')
for key, value in od.items():
    print(key, value)

print("\nAfter re-inserting:\n")
od['c'] = 3
for key, value in od.items():
    print(key, value)

خروجی:

Before deleting:

a 1
b 2
c 3
d 4

After deleting:

a 1
b 2
d 4

After re-inserting:

a 1
b 2
d 4
c 3

DefaultDict در پایتون

DefaultDict برای فراهم کردن مقادیر پیش‌فرض برای کلیدهایی که وجود ندارند استفاده می‌شود و هیچ‌گاه KeyError ایجاد نمی‌کند. اشیای DefaultDict می‌توانند با استفاده از متد ()DefaultDict و با ارسال نوع داده‌ای به عنوان آرگومان مقداردهی اولیه شوند.

نکته: default_factory یک تابع است که مقدار پیش‌فرض را برای دیکشنری ایجاد شده فراهم می‌کند. اگر این پارامتر وجود نداشته باشد، KeyError رخ خواهد داد.

مثال: عملیات روی DefaultDict در پایتون

from collections import defaultdict
    

# Defining the dict
d = defaultdict(int)
    
L = [1, 2, 3, 4, 2, 4, 1, 2]
    
# Iterate through the list
# for keeping the count
for i in L:
        
    # The default value is 0
    # so there is no need to
    # enter the key first
    d[i] += 1
        
print(d)

خروجی:

defaultdict(<class 'int'>, {1: 2, 2: 3, 3: 1, 4: 2})

ChainMap در پایتون

ChainMap مجموعه‌ای از دیکشنری‌ها را در یک واحد ترکیب می‌کند و یک لیست از دیکشنری‌ها برمی‌گرداند. زمانی که نیاز به پیدا کردن یک کلید باشد، تمام دیکشنری‌ها به صورت یک به یک جستجو می‌شوند تا زمانی که کلید پیدا شود. این روش برای مدیریت چندین دیکشنری به صورت همزمان و با ترتیب جستجو مفید است.

مثال: عملیات روی ChainMap در پایتون

from collections import ChainMap
    
    
d1 = {'a': 1, 'b': 2}
d2 = {'c': 3, 'd': 4}
d3 = {'e': 5, 'f': 6}
    
# Defining the chainmap
c = ChainMap(d1, d2, d3)
print(c)

print(c['a'])
print(c['g'])

خروجی:

ChainMap({'a': 1, 'b': 2}, {'c': 3, 'd': 4}, {'e': 5, 'f': 6})
۱

KeyError: 'g'

NamedTuple در پایتون

NamedTuple یک شی تاپل «Tuple» است که برای هر موقعیت یک نام اختصاص می‌دهد، در حالی که تپل‌های معمولی فاقد این ویژگی هستند. به عنوان مثال، اگر یک تپل به نام student داشته باشیم که اولین عنصر آن نمایانگر نام، دومین عنصر نمایانگر نام خانوادگی و سومین عنصر نمایانگر تاریخ تولد باشد، به جای یادآوری موقعیت ایندکس‌ها، می‌توانیم از نام‌هایی مثل fname برای دسترسی به عنصرها استفاده کنیم. این ویژگی به دسترسی آسان‌تر به عناصر تپل کمک می‌کند.

مثال: عملیات روی NamedTuple در پایتون

from collections import namedtuple
    
# Declaring namedtuple()
Student = namedtuple('Student',['name','age','DOB'])
    
# Adding values
S = Student('Nandini','19','2541997')
    
# Access using index
print ("The Student age using index is : ",end ="")
print (S[1])
    
# Access using name
print ("The Student name using keyname is : ",end ="")
print (S.name)

خروجی:

The Student age using index is : 19
The Student name using keyname is : Nandini

Deque در پایتون

Deque یا صف دوطرفه یک نوع لیست بهینه‌شده است که برای انجام عملیات اضافه کردن «append» و حذف «pop» از هر دو طرف لیست به طور سریع‌تر طراحی شده است. این نوع لیست برای عملیات اضافه کردن و حذف از ابتدا یا انتهای لیست دارای پیچیدگی زمانی O(1) است، در حالی که لیست‌های معمولی پیچیدگی زمانی O(n) برای این عملیات‌ها دارند.

Deque در پایتون با استفاده از لیست‌های پیوندی دوطرفه پیاده‌سازی شده است. بنابراین، عملکرد دسترسی تصادفی به عناصر در این ساختمان داده O(n) است.

مثال: عملیات روی Deque در پایتون

# importing "collections" for deque operations
import collections

# initializing deque
de = collections.deque([1,2,3])

# using append() to insert element at right end
# inserts 4 at the end of deque
de.append(4)

# printing modified deque
print("The deque after appending at right is : ")
print(de)

# using appendleft() to insert element at left end
# inserts 6 at the beginning of deque
de.appendleft(6)

# printing modified deque
print("The deque after appending at left is : ")
print(de)

# using pop() to delete element from right end
# deletes 4 from the right end of deque
de.pop()

# printing modified deque
print("The deque after deleting from right is : ")
print(de)

# using popleft() to delete element from left end
# deletes 6 from the left end of deque
de.popleft()

# printing modified deque
print("The deque after deleting from left is : ")
print(de)

خروجی:

The deque after appending at right is : 
deque([1, 2, 3, 4])
The deque after appending at left is : 
deque([6, 1, 2, 3, 4])
The deque after deleting from right is : 
deque([6, 1, 2, 3])
The deque after deleting from left is : 
deque([1, 2, 3])

UserDict در پایتون

UserDict یک نوع کانتینر مشابه دیکشنری است که به عنوان یک پوشش «wrapper» برای اشیا دیکشنری عمل می‌کند. این کانتینر زمانی استفاده می‌شود که بخواهید دیکشنری خاص خود را با برخی ویژگی‌ها یا عملکردهای جدید یا اصلاح‌شده ایجاد کنید.

مثال: استفاده از UserDict در پایتون

from collections import UserDict

# Creating a Dictionary where
# deletion is not allowed
class MyDict(UserDict):
    
    # Function to stop deletion
    # from dictionary
    def __del__(self):
        raise RuntimeError("Deletion not allowed")
        
    # Function to stop pop from
    # dictionary
    def pop(self, s = None):
        raise RuntimeError("Deletion not allowed")
        
    # Function to stop popitem
    # from Dictionary
    def popitem(self, s = None):
        raise RuntimeError("Deletion not allowed")
    
# Driver's code
d = MyDict({'a':1,
    'b': 2,
    'c': 3})

print("Original Dictionary")
print(d)

d.pop(1)

خروجی:

Original Dictionary
{'a': 1, 'b': 2, 'c': 3}

RuntimeError: Deletion not allowed

UserList در پایتون

UserList یک کانتینر مشابه لیست است که به عنوان پوششی برای اشیا لیست عمل می‌کند. این کانتینر زمانی مفید است که کسی بخواهد لیست خاص خود را با برخی ویژگی‌ها یا عملکردهای جدید یا اصلاح‌شده ایجاد کند.

مثال‌ها: استفاده از UserList در پایتون

# Python program to demonstrate
# userlist


from collections import UserList


# Creating a List where
# deletion is not allowed
class MyList(UserList):
    
    # Function to stop deletion
    # from List
    def remove(self, s = None):
        raise RuntimeError("Deletion not allowed")
        
    # Function to stop pop from
    # List
    def pop(self, s = None):
        raise RuntimeError("Deletion not allowed")
    
# Driver's code
L = MyList([1, 2, 3, 4])

print("Original List")
print(L)

# Inserting to List"
L.append(5)
print("After Insertion")
print(L)

# Deleting From List
L.remove()

خروجی:

Original List
[۱, ۲, ۳, ۴]
After Insertion
[۱, ۲, ۳, ۴, ۵]

RuntimeError: Deletion not allowed

UserString در پایتون

UserString یک کانتینر مشابه رشته است که مانند UserDict و UserList به عنوان پوششی برای اشیا رشته‌ای عمل می‌کند. این کانتینر زمانی استفاده می‌شود که کسی بخواهد رشته خاص خود را با برخی ویژگی‌ها یا عملکردهای جدید یا اصلاح‌شده ایجاد کند.

مثال: استفاده از UserString در پایتون

from collections import UserString

# Creating a Mutable String
class Mystring(UserString):
    
    # Function to append to
    # string
    def append(self, s):
        self.data += s
        
    # Function to remove from
    # string
    def remove(self, s):
        self.data = self.data.replace(s, "")
    
# Driver's code
s1 = Mystring("Program")
print("Original String:", s1.data)

# Appending to string
s1.append("s")
print("String After Appending:", s1.data)

# Removing from string
s1.remove("e")
print("String after Removing:", s1.data)

خروجی:

Original String: Program
String After Appending: Programm
String after Removing: Pgram

ساختمان داده لیست پیوندی در پایتون

ساختمان داده لیست پیوندی در پایتون، خطی است که در آن عناصر در مکان‌های حافظه پیوسته ذخیره نمی‌شوند. به عبارت دیگر، هر عنصر در یک لیست پیوندی به وسیله‌ی اشاره‌گرها «pointers» به عنصر بعدی متصل می‌شود. این ویژگی باعث می‌شود که در لیست پیوندی بتوانیم به راحتی عناصری را اضافه یا حذف کنیم، بدون اینکه نیاز به جابجایی دیگر عناصر داشته باشیم.

در یک لیست پیوندی، هر عنصر معمولاً شامل داده و آدرس (یا اشاره‌گر) به عنصر بعدی است. این ساختمان داده به ما اجازه می‌دهد که به طور پویا به حافظه دسترسی داشته باشیم و اندازه لیست را به راحتی تغییر دهیم.

لیست پیوندی توسط یک اشاره‌گر به اولین گره «node» لیست پیوندی نمایش داده می‌شود. اولین گره به نام head شناخته می‌شود. اگر لیست پیوندی خالی باشد، مقدار head برابر NULL است. هر گره در لیست حداقل دو بخش دارد:

1. داده «Data»
2. اشاره‌گر یا مرجع به گره بعدی «Pointer or Reference to the next node»

در صورتی که بخواهید یک لیست پیوندی را در پایتون تعریف کنید، می‌توانید یک کلاس برای گره‌ها و کلاس دیگری برای خود لیست ایجاد کنید که در آن روش‌هایی برای اضافه کردن، حذف کردن یا پیمایش لیست فراهم باشد.

# Node class
class Node:

    # Function to initialize the node object
    def __init__(self, data):
        self.data = data # Assign data
        self.next = None # Initialize
                        # next as null

# Linked List class
class LinkedList:
    
    # Function to initialize the Linked
    # List object
    def __init__(self):
        self.head = None

برای ایجاد یک لیست پیوندی ساده با ۳ گره، می‌توانیم از یک کلاس برای گره‌ها و یک کلاس دیگر برای لیست پیوندی استفاده کنیم.

# A simple Python program to introduce a linked list

# Node class
class Node:

    # Function to initialise the node object
    def __init__(self, data):
        self.data = data # Assign data
        self.next = None # Initialize next as null


# Linked List class contains a Node object
class LinkedList:

    # Function to initialize head
    def __init__(self):
        self.head = None


# Code execution starts here
if __name__=='__main__':

    # Start with the empty list
    list = LinkedList()

    list.head = Node(1)
    second = Node(2)
    third = Node(3)

    '''
    Three nodes have been created.
    We have references to these three blocks as head,
    second and third

    list.head     second             third
        |             |                 |
        |             |                 |
    +----+------+     +----+------+     +----+------+
    | ۱ | None |     | 2 | None |     | 3 | None |
    +----+------+     +----+------+     +----+------+
    '''

    list.head.next = second; # Link first node with second

    '''
    Now next of first Node refers to second. So they
    both are linked.

    list.head     second             third
        |             |                 |
        |             |                 |
    +----+------+     +----+------+     +----+------+
    | ۱ | o-------->| 2 | null |     | 3 | null |
    +----+------+     +----+------+     +----+------+
    '''

    second.next = third; # Link second node with the third node

    '''
    Now next of second Node refers to third. So all three
    nodes are linked.

    list.head     second             third
        |             |                 |
        |             |                 |
    +----+------+     +----+------+     +----+------+
    | ۱ | o-------->| 2 | o-------->| 3 | null |
    +----+------+     +----+------+     +----+------+
    '''

برای پیمایش لیست پیوندی، تابع ()printList به این شکل عمل می‌کند که داده هر گره را چاپ کرده و به گره بعدی می‌رود تا زمانی که به انتهای لیست برسد.

# A simple Python program for traversal of a linked list

# Node class
class Node:

    # Function to initialise the node object
    def __init__(self, data):
        self.data = data # Assign data
        self.next = None # Initialize next as null


# Linked List class contains a Node object
class LinkedList:

    # Function to initialize head
    def __init__(self):
        self.head = None

    # This function prints contents of linked list
    # starting from head
    def printList(self):
        temp = self.head
        while (temp):
            print (temp.data)
            temp = temp.next


# Code execution starts here
if __name__=='__main__':

    # Start with the empty list
    list = LinkedList()

    list.head = Node(1)
    second = Node(2)
    third = Node(3)

    list.head.next = second; # Link first node with second
    second.next = third; # Link second node with the third node

    list.printList()

خروجی:

۱
۲
۳

ساختمان داده Stack در پایتون

ساختمان داده‌ استک یک ساختمان داده خطی است که اقلام را به روش آخرین وارد، اولین خارج «LIFO» یا اولین ورود، آخرین خارج «FILO» ذخیره می‌کند. در استک، یک عنصر جدید در یک انتها اضافه می‌شود و تنها از همان انتها حذف می‌شود. عملیات افزودن و حذف معمولاً به نام‌های push و pop شناخته می‌شوند.

عملکردهای مرتبط با استک عبارتند از:

• ()empty: بررسی می‌کند که آیا استک خالی است یا خیر – پیچیدگی زمانی: O(1)
• ()size: اندازه استک را برمی‌گرداند – پیچیدگی زمانی: O(1)
• ()top: ارجاعی به بالاترین عنصر استک می‌دهد – پیچیدگی زمانی: O(1)
• push(a): عنصر a را در بالای استک وارد می‌کند – پیچیدگی زمانی: O(1)
• ()pop: بالاترین عنصر استک را حذف می‌کند – پیچیدگی زمانی: O(1)

پیاده‌سازی استک در پایتون

استک در پایتون می‌تواند به روش‌های مختلف پیاده‌سازی شود:

• استفاده از لیست
• استفاده از collections.deque
• استفاده از queue.LifoQueue

پیاده‌سازی با استفاده از لیست

ساختمان داده داخلی پایتون، لیست، می‌تواند به عنوان یک استک عمل کند. به جای استفاده از ()push، از ()append برای افزودن عناصر به بالای استک استفاده می‌شود، در حالی که ()pop برای حذف عنصر به ترتیب LIFO به کار می‌رود.

stack = []

# append() function to push
# element in the stack
stack.append('P')
stack.append('S')
stack.append('T')

print('Initial stack')
print(stack)

# pop() function to pop
# element from stack in
# LIFO order
print('\nElements popped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())

print('\nStack after elements are popped:')
print(stack)

# uncommenting print(stack.pop())
# will cause an IndexError
# as the stack is now empty

خروجی:

Initial stack
['P', 'S', 'T']

Elements popped from stack:
P
S
T

Stack after elements are popped:
[]

پیاده‌سازی با استفاده از collections.deque در پایتون

استک در پایتون می‌تواند با استفاده از کلاس deque از ماژول collections پیاده‌سازی شود. Deque به دلیل ارائه پیچیدگی زمانی O(1) برای عملیات افزودن و حذف از هر دو انتهای کانتینر، نسبت به لیست ترجیح داده می‌شود. در حالی که لیست دارای پیچیدگی زمانی O(n) برای این عملیات‌ها است.

from collections import deque

stack = deque()

# append() function to push
# element in the stack
stack.append('P')
stack.append('S')
stack.append('T')

print('Initial stack:')
print(stack)

# pop() function to pop
# element from stack in
# LIFO order
print('\nElements popped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())

print('\nStack after elements are popped:')
print(stack)

# uncommenting print(stack.pop())
# will cause an IndexError
# as the stack is now empty

خروجی:

Initial stack:
deque(['P', 'S', 'T'])

Elements popped from stack:
P
S
T

Stack after elements are popped:
deque([])

پیاده‌سازی با استفاده از ماژول queue

ماژول queue همچنین یک LIFO Queue دارد که در واقع همان استک است. داده‌ها با استفاده از تابع ()put به صف اضافه می‌شوند و تابع ()get داده‌ها را از صف خارج می‌کند.

from queue import LifoQueue

# Initializing a stack
stack = LifoQueue(maxsize = 3)

# qsize() show the number of elements
# in the stack
print(stack.qsize())

# put() function to push
# element in the stack
stack.put('P')
stack.put('S')
stack.put('T')

print("Full: ", stack.full())
print("Size: ", stack.qsize())

# get() function to pop
# element from stack in
# LIFO order
print('\nElements popped from the stack')
print(stack.get())
print(stack.get())
print(stack.get())

print("\nEmpty: ", stack.empty())

خروجی:

۰
Full:  True
Size:  3

Elements popped from the stack
P
S
T

Empty:  True

ساختمان داده Queue در پایتون

ساختمان داده صف «Queue» یک ساختمان داده خطی است که اقلام را به روش اولین وارد، اولین خارج  ذخیره می‌کند. در صف، اولین عنصری که وارد می‌شود، اولین عنصری است که حذف می‌شود. یک مثال خوب از صف، صف مصرف‌کنندگان یک منبع است که مصرف‌کننده‌ای که اول آمده، اول خدمت می‌گیرد.

عملیات مرتبط با صف عبارتند از:

• Enqueue: افزودن یک عنصر به صف. اگر صف پر باشد، به آن Overflow condition گفته می‌شود – پیچیدگی زمانی: O(1)
• Dequeue: حذف یک عنصر از صف. اقلام به همان ترتیبی که وارد شده‌اند حذف می‌شوند. اگر صف خالی باشد، به آن Underflow condition گفته می‌شود – پیچیدگی زمانی: O(1)
• Front: گرفتن اولین عنصر از صف – پیچیدگی زمانی: O(1)
• Rear: گرفتن آخرین عنصر از صف – پیچیدگی زمانی: O(1)

پیاده‌سازی صف در پایتون

صف در پایتون می‌تواند به روش‌های مختلف پیاده‌سازی شود:

• استفاده از لیست
• استفاده از collections.deque
• استفاده از queue.Queue

پیاده‌سازی با استفاده از لیست

به جای استفاده از ()enqueue و ()dequeue ، از توابع ()append و ()pop برای افزودن و حذف عناصر به صف استفاده می‌شود.

# Initializing a queue
queue = []

# Adding elements to the queue
queue.append('P')
queue.append('S')
queue.append('T')

print("Initial queue")
print(queue)

# Removing elements from the queue
print("\nElements dequeued from queue")
print(queue.pop(0))
print(queue.pop(0))
print(queue.pop(0))

print("\nQueue after removing elements")
print(queue)

# Uncommenting print(queue.pop(0))
# will raise and IndexError
# as the queue is now empty

خروجی:

Initial queue
['g', 'f', 'g']

Elements dequeued from queue
P
S
T

Queue after removing elements
[]

پیاده‌سازی با استفاده از collections.deque در پایتون

در مواردی که نیاز به عملیات سریع‌تر append و pop از هر دو انتهای کانتینر داریم، استفاده از deque نسبت به لیست ترجیح داده می‌شود. زیرا deque پیچیدگی زمانی O(1) برای عملیات اضافه کردن و حذف دارد، در حالی که لیست برای این عملیات‌ها پیچیدگی زمانی O(n) دارد.

from collections import deque

# Initializing a queue
q = deque()

# Adding elements to a queue
q.append('P')
q.append('S')
q.append('T')

print("Initial queue")
print(q)

# Removing elements from a queue
print("\nElements dequeued from the queue")
print(q.popleft())
print(q.popleft())
print(q.popleft())

print("\nQueue after removing elements")
print(q)

# Uncommenting q.popleft()
# will raise an IndexError
# as queue is now empty

خروجی:

Initial queue
deque(['P', 'S', 'T'])

Elements dequeued from the queue
P
R
T

Queue after removing elements
deque([])

پیاده‌سازی با استفاده از queue.Queue در پایتون

queue.Queue(maxsize) یک متغیر صف با حداکثر اندازه maxsize را مقداردهی اولیه می‌کند. اگر مقدار maxsize برابر صفر باشد، به معنای صف نامحدود است. این صف از قانون FIFO پیروی می‌کند، به این معنی که اولین عنصر وارد شده، اولین عنصر خارج شده خواهد بود.

from queue import Queue

# Initializing a queue
q = Queue(maxsize = 3)

# qsize() give the maxsize
# of the Queue
print(q.qsize())

# Adding of element to queue
q.put('P')
q.put('S')
q.put('T')

# Return Boolean for Full
# Queue
print("\nFull: ", q.full())

# Removing element from queue
print("\nElements dequeued from the queue")
print(q.get())
print(q.get())
print(q.get())

# Return Boolean for Empty
# Queue
print("\nEmpty: ", q.empty())

q.put(1)
print("\nEmpty: ", q.empty())
print("Full: ", q.full())

# This would result into Infinite
# Loop as the Queue is empty.
# print(q.get())

خروجی:

۰

Full:  True

Elements dequeued from the queue
P
S
T

Empty:  True

Empty:  False
Full:  False

ساختمان داده Priority Queue در پایتون

ساختمان داده Priority Queue در پایتون یک ساختمان داده‌ انتزاعی است که در آن هر داده یا مقداری در صف یک اولویت خاص دارد. برای مثال، در خطوط هوایی، چمدان‌هایی با عنوان Business یا First-class زودتر از بقیه چمدان‌ها دریافت می‌شوند. Priority Queue یک گسترش از صف است که ویژگی‌های زیر را دارد:

• عنصری با اولویت بالا قبل از عنصری با اولویت پایین از صف حذف می‌شود.
• اگر دو عنصر اولویت یکسانی داشته باشند، بر اساس ترتیب ورودشان به صف پردازش می‌شوند.

# A simple implementation of Priority Queue
# using Queue.
class PriorityQueue(object):
    def __init__(self):
        self.queue = []

    def __str__(self):
        return ' '.join([str(i) for i in self.queue])

    # for checking if the queue is empty
    def isEmpty(self):
        return len(self.queue) == 0

    # for inserting an element in the queue
    def insert(self, data):
        self.queue.append(data)

    # for popping an element based on Priority
    def delete(self):
        try:
            max = 0
            for i in range(len(self.queue)):
                if self.queue[i] > self.queue[max]:
                    max = i
            item = self.queue[max]
            del self.queue[max]
            return item
        except IndexError:
            print()
            exit()

if __name__ == '__main__':
    myQueue = PriorityQueue()
    myQueue.insert(12)
    myQueue.insert(1)
    myQueue.insert(14)
    myQueue.insert(7)
    print(myQueue)            
    while not myQueue.isEmpty():
        print(myQueue.delete())

خروجی:

۱۲ ۱ ۱۴ ۷
۱۴
۱۲
۷
۱

ساختمان داده Heap queue در پایتون

ساختمان داده Heap queue در پایتون ، ساختمان داده‌ heap را فراهم می‌کند که عمدتا برای نمایش صف اولویت استفاده می‌شود. ویژگی ساختمان داده در پایتون این است که هر بار که کوچکترین عنصر هیپ حذف می‌شود (min-heap). هر زمان که عناصری اضافه یا حذف می‌شوند، ساختار هیپ حفظ می‌شود. عنصر heap[0] همچنین همیشه کوچکترین عنصر را باز می‌گرداند.

این ساختمان داده در پایتون از استخراج و وارد کردن کوچکترین عنصر با پیچیدگی زمانی O(log n) پشتیبانی می‌کند.

# importing "heapq" to implement heap queue
import heapq

# initializing list
li = [5, 7, 9, 1, 3]

# using heapify to convert list into heap
heapq.heapify(li)

# printing created heap
print ("The created heap is : ",end="")
print (list(li))

# using heappush() to push elements into heap
# pushes 4
heapq.heappush(li,4)

# printing modified heap
print ("The modified heap after push is : ",end="")
print (list(li))

# using heappop() to pop smallest element
print ("The popped and smallest element is : ",end="")
print (heapq.heappop(li))

خروجی:

The created heap is : [1, 3, 9, 7, 5]
The modified heap after push is : [1, 3, 4, 7, 5, 9]
The popped and smallest element is : 1

درخت یک ساختمان داده سلسله‌مراتبی است.

 tree
     ----
      j    <-- root
    /   \
   f      k  
 /   \      \
a     h      z    <-- leaves

گره بالاترین درخت به نام ریشه «Root» شناخته می‌شود، در حالی که گره‌های پایین‌ترین سطح یا گره‌هایی که فرزند ندارند به نام گره‌های برگ «Leaf nodes» شناخته می‌شوند. گره‌هایی که مستقیما زیر یک گره قرار دارند، به نام فرزند «Children» آن گره شناخته می‌شوند و گره‌هایی که مستقیما بالای یک گره قرار دارند، به نام والد «Parent» آن گره شناخته می‌شوند.

درخت دودویی درختی است که در آن هر عنصر می‌تواند حداکثر دو فرزند داشته باشد. در درخت دودویی، معمولاً این دو فرزند به نام‌های فرزند چپ و فرزند راست شناخته می‌شوند. هر گره در درخت دودویی شامل بخش‌های زیر است:

• داده
• اشاره‌گر به فرزند چپ
• اشاره‌گر به فرزند راست

# A Python class that represents an individual node
# in a Binary Tree
class Node:
    def __init__(self,key):
        self.left = None
        self.right = None
        self.val = key

خروجی:

tree
    ----
     ۱    <-- root
   /   \
  ۲     ۳  
 /  
۴

برای افزودن داده به درخت، ابتدا باید بررسی کنیم که آیا درخت خالی است یا خیر. اگر درخت خالی باشد، داده به ریشه اختصاص داده می‌شود. در غیر این صورت، داده باید به درستی در موقعیت مناسب در درخت قرار گیرد.

# Python program to introduce Binary Tree

# A class that represents an individual node in a
# Binary Tree
class Node:
    def __init__(self,key):
        self.left = None
        self.right = None
        self.val = key


# create root
root = Node(1)
''' following is the tree after above statement
        ۱
    / \
    None None'''

root.left     = Node(2);
root.right     = Node(3);

''' ۲ and 3 become left and right children of 1
        ۱
        / \
        ۲     ۳
    / \ / \
None None None None'''


root.left.left = Node(4);
'''۴ becomes left child of 2
        ۱
    /     \
    ۲         ۳
    / \     / \
۴ None None None
/ \
None None'''

عبور از درخت

درخت‌ها می‌توانند به روش‌های مختلفی پیمایش شوند. در زیر روش‌های معمول برای پیمایش درخت‌ها آورده شده است. فرض کنید درخت زیر را در نظر بگیریم

tree
    ----
     ۱    <-- root
   /   \
  ۲     ۳  
 / \
۴   ۵

عبور از درخت به روش عمقی:

• درون‌تر (چپ، ریشه، راست): ۴ ۲ ۵ ۱ ۳
• پری‌درون‌تر (ریشه، چپ، راست): ۱ ۲ ۴ ۵ ۳
• پست‌درون‌تر (چپ، راست، ریشه): ۴ ۵ ۲ ۳ ۱

الگوریتم درون‌تر(tree):

• زیر درخت چپ را پیمایش کن، یعنی فراخوانی درون‌تر برای زیر درخت چپ.
• ریشه را بازدید کن.
• زیر درخت راست را پیمایش کن، یعنی فراخوانی درون‌تر برای زیر درخت راست.

الگوریتم پری‌درون‌تر(tree):

• ریشه را بازدید کن.
• زیر درخت چپ را پیمایش کن، یعنی فراخوانی پری‌درون‌تر برای زیر درخت چپ.
• زیر درخت راست را پیمایش کن، یعنی فراخوانی پری‌درون‌تر برای زیر درخت راست.

الگوریتم پست‌درون‌تر(tree):

• زیر درخت چپ را پیمایش کن، یعنی فراخوانی پست‌درون‌تر برای زیر درخت چپ.
• زیر درخت راست را پیمایش کن، یعنی فراخوانی پست‌درون‌تر برای زیر درخت راست.
• ریشه را بازدید کن.

# Python program to for tree traversals

# A class that represents an individual node in a
# Binary Tree
class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key


# A function to do inorder tree traversal
def printInorder(root):

    if root:

        # First recur on left child
        printInorder(root.left)

        # then print the data of node
        print(root.val),

        # now recur on right child
        printInorder(root.right)


# A function to do postorder tree traversal
def printPostorder(root):

    if root:

        # First recur on left child
        printPostorder(root.left)

        # the recur on right child
        printPostorder(root.right)

        # now print the data of node
        print(root.val),


# A function to do preorder tree traversal
def printPreorder(root):

    if root:

        # First print the data of node
        print(root.val),

        # Then recur on left child
        printPreorder(root.left)

        # Finally recur on right child
        printPreorder(root.right)


# Driver code
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("Preorder traversal of binary tree is")
printPreorder(root)

print("\nInorder traversal of binary tree is")
printInorder(root)

print("\nPostorder traversal of binary tree is")
printPostorder(root)

خروجی:

Preorder traversal of binary tree is
۱
۲
۴
۵
۳

Inorder traversal of binary tree is
۴
۲
۵
۱
۳

Postorder traversal of binary tree is
۴
۵
۲
۳
۱

زمان پیچیدگی – O(n)

پیمایش به روش عرضی یا سطحی

پیمایش سطحی درخت همان پیمایش به روش عرضی است. پیمایش سطحی درخت بالا به این صورت است: ۱ ۲ ۳ ۴ ۵.

برای هر گره، ابتدا گره بازدید می‌شود و سپس فرزندان آن در یک صف FIFO قرار می‌گیرند. در زیر الگوریتم مربوطه آورده شده است:

• یک صف خالی q ایجاد کن.
• temp_node = root /* از ریشه شروع کن */
• حلقه را در حالی که temp_node برابر NULL نیست اجرا کن:
• داده temp_node را چاپ کن.
• فرزندان temp_node را (اول فرزند چپ و سپس فرزند راست) به صف اضافه کن.
• یک گره از صف خارج کن.

# Python program to print level
# order traversal using Queue

# A node structure
class Node:
  
    # A utility function to create a new node
    def __init__(self ,key):
        self.data = key
        self.left = None
        self.right = None

# Iterative Method to print the
# height of a binary tree
def printLevelOrder(root):
  
    # Base Case
    if root is None:
        return
    
    # Create an empty queue
    # for level order traversal
    queue = []

    # Enqueue Root and initialize height
    queue.append(root)

    while(len(queue) > 0):
    
        # Print front of queue and
        # remove it from queue
        print (queue[0].data)
        node = queue.pop(0)

        # Enqueue left child
        if node.left is not None:
            queue.append(node.left)

        # Enqueue right child
        if node.right is not None:
            queue.append(node.right)

# Driver Program to test above function
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print ("Level Order Traversal of binary tree is -")
printLevelOrder(root)

خروجی:

Level Order Traversal of binary tree is -
۱
۲
۳
۴
۵

زمان پیچیدگی: O(n)

ساختمان داده گراف در پایتون

ساختمان داده گراف در پایتون گراف یک ساختمان داده‌ غیرخطی است که از گره‌ها و یال‌ها تشکیل شده است. گره‌ها گاهی اوقات به عنوان راس «vertice» نیز شناخته می‌شوند و یال‌ها خطوط یا کمان‌هایی هستند که دو گره را در گراف به هم متصل می‌کنند. به طور رسمی‌تر، گراف به عنوان یک مجموعه شامل مجموعه‌ای از راس‌ها یا گره‌ها و مجموعه‌ای از یال‌ها تعریف می‌شود که یک جفت گره را به هم متصل می‌کنند.

در گراف بالا، مجموعه رئوس V = {۰، ۱، ۲، ۳، ۴} و مجموعه یال‌ها E = {۰۱، ۱۲، ۲۳، ۳۴، ۰۴، ۱۴، ۱۳} است.

دو نمایش معمول گراف به شرح زیر هستند:

ماتریس مجاورت در پایتون

ماتریس مجاورت یک آرایه دوبعدی با اندازه V x V است که V تعداد راس‌ها در گراف است. فرض کنید آرایه دوبعدی به نام [ ][ ]adj داشته باشیم، در این صورت اگر adj[i][j] = 1 باشد، به این معنی است که یک یال از راس i به راس j وجود دارد. ماتریس مجاورت برای گراف‌های بدون جهت همیشه متقارن است. ماتریس مجاورت همچنین برای نمایش گراف‌های وزنی استفاده می‌شود. اگر adj[i][j] = w باشد، به این معناست که یک یال از راس i به راس j با وزن w وجود دارد.

# A simple representation of graph using Adjacency Matrix
class Graph:
    def __init__(self,numvertex):
        self.adjMatrix = [[-1]*numvertex for x in range(numvertex)]
        self.numvertex = numvertex
        self.vertices = {}
        self.verticeslist =[0]*numvertex

    def set_vertex(self,vtx,id):
        if 0<=vtx<=self.numvertex:
            self.vertices[id] = vtx
            self.verticeslist[vtx] = id

    def set_edge(self,frm,to,cost=0):
        frm = self.vertices[frm]
        to = self.vertices[to]
        self.adjMatrix[frm][to] = cost
        
        # for directed graph do not add this
        self.adjMatrix[to][frm] = cost

    def get_vertex(self):
        return self.verticeslist

    def get_edges(self):
        edges=[]
        for i in range (self.numvertex):
            for j in range (self.numvertex):
                if (self.adjMatrix[i][j]!=-1):
                    edges.append((self.verticeslist[i],self.verticeslist[j],self.adjMatrix[i][j]))
        return edges
        
    def get_matrix(self):
        return self.adjMatrix

G =Graph(6)
G.set_vertex(0,'a')
G.set_vertex(1,'b')
G.set_vertex(2,'c')
G.set_vertex(3,'d')
G.set_vertex(4,'e')
G.set_vertex(5,'f')
G.set_edge('a','e',10)
G.set_edge('a','c',20)
G.set_edge('c','b',30)
G.set_edge('b','e',40)
G.set_edge('e','d',50)
G.set_edge('f','e',60)

print("Vertices of Graph")
print(G.get_vertex())

print("Edges of Graph")
print(G.get_edges())

print("Adjacency Matrix of Graph")
print(G.get_matrix())

خروجی:

Vertices of Graph


[‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’]


Edges of Graph


[(‘a’, ‘c’, ۲۰), (‘a’, ‘e’, ۱۰), (‘b’, ‘c’, ۳۰), (‘b’, ‘e’, ۴۰), (‘c’, ‘a’, ۲۰), (‘c’, ‘b’, ۳۰), (‘d’, ‘e’, ۵۰), (‘e’, ‘a’, ۱۰), (‘e’, ‘b’, ۴۰), (‘e’, ‘d’, ۵۰), (‘e’, ‘f’, ۶۰), (‘f’, ‘e’, ۶۰)]


Adjacency Matrix of Graph



[[-۱, -۱, ۲۰, -۱, ۱۰, -۱], [-۱, -۱, ۳۰, -۱, ۴۰, -۱], [۲۰, ۳۰, -۱, -۱, -۱, -۱], [-۱, -۱, -۱, -۱, ۵۰, -۱], [۱۰, ۴۰, -۱, ۵۰, -۱, ۶۰], [-۱, -۱, -۱, -۱, ۶۰, -۱]]

فهرست مجاورت در پایتون

از یک آرایه از لیست‌ها استفاده می‌شود. اندازه آرایه برابر با تعداد راس‌ها است. فرض کنید آرایه به نام [ ]array داشته باشیم. هر ورودی array[i] نمایانگر لیستی از راس‌ها مجاور به راس i است. این نمایش می‌تواند برای گراف‌های وزنی نیز استفاده شود. وزن‌های یال‌ها می‌توانند به عنوان لیست‌هایی از جفت‌ها (زوج‌های راس و وزن) نمایش داده شوند.

نمایش فهرست مجاورت گراف بالا به شرح زیر است:

• array[0] = {1, 4}
• array[1] = {0, 2, 4, 3}
• array[2] = {1, 3}
• array[3] = {2, 4, 1}
• array[4] = {0, 1, 3}

# A class to represent the adjacency list of the node
class AdjNode:
    def __init__(self, data):
        self.vertex = data
        self.next = None


# A class to represent a graph. A graph
# is the list of the adjacency lists.
# Size of the array will be the no. of the
# vertices "V"
class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [None] * self.V

    # Function to add an edge in an undirected graph
    def add_edge(self, src, dest):
      
        # Adding the node to the source node
        node = AdjNode(dest)
        node.next = self.graph[src]
        self.graph[src] = node

        # Adding the source node to the destination as
        # it is the undirected graph
        node = AdjNode(src)
        node.next = self.graph[dest]
        self.graph[dest] = node

    # Function to print the graph
    def print_graph(self):
        for i in range(self.V):
            print("Adjacency list of vertex {}\n head".format(i), end="")
            temp = self.graph[i]
            while temp:
                print(" -> {}".format(temp.vertex), end="")
                temp = temp.next
            print(" \n")


# Driver program to the above graph class
if __name__ == "__main__":
    V = 5
    graph = Graph(V)
    graph.add_edge(0, 1)
    graph.add_edge(0, 4)
    graph.add_edge(1, 2)
    graph.add_edge(1, 3)
    graph.add_edge(1, 4)
    graph.add_edge(2, 3)
    graph.add_edge(3, 4)

    graph.print_graph()

خروجی:

Adjacency list of vertex 0
 head -> 4 -> 1 

Adjacency list of vertex 1
 head -> 4 -> 3 -> 2 -> 0 

Adjacency list of vertex 2
 head -> 3 -> 1 

Adjacency list of vertex 3
 head -> 4 -> 2 -> 1 

Adjacency list of vertex 4
 head -> 3 -> 1 -> 0

پیمایش گراف

پیمایش به روش جستجوی اول عرضی (BFS)

پیمایش به روش عرضی برای یک گراف مشابه پیمایش عرضی درخت است. تنها تفاوت این است که برخلاف درخت‌ها، گراف‌ها ممکن است شامل چرخه‌ها باشند، بنابراین ممکن است دوباره به همان گره برسیم. برای جلوگیری از پردازش دوباره یک گره، از یک آرایه بولی visited استفاده می‌کنیم. برای سادگی، فرض می‌شود که همه راس‌ها از راس شروع قابل دسترسی هستند.

برای مثال، در گراف زیر، پیمایش را از راس ۲ شروع می‌کنیم. وقتی به راس ۰ می‌رسیم، تمام راس‌ها مجاور آن را بررسی می‌کنیم. راس ۲ نیز یک راس مجاور ۰ است. اگر راس‌هابازدید شده را علامت‌گذاری نکنیم، راس ۲ دوباره پردازش می‌شود و این باعث ایجاد یک فرآیند غیرپایان‌پذیر خواهد شد.
پیمایش به روش جستجوی اول عرضی (BFS) در گراف زیر به این صورت است: ۲، ۰، ۳، ۱.

# Python3 Program to print BFS traversal
# from a given source vertex. BFS(int s)
# traverses vertices reachable from s.
from collections import defaultdict

# This class represents a directed graph
# using adjacency list representation
class Graph:

    # Constructor
    def __init__(self):

        # default dictionary to store graph
        self.graph = defaultdict(list)

    # function to add an edge to graph
    def addEdge(self,u,v):
        self.graph[u].append(v)

    # Function to print a BFS of graph
    def BFS(self, s):

        # Mark all the vertices as not visited
        visited = [False] * (max(self.graph) + 1)

        # Create a queue for BFS
        queue = []

        # Mark the source node as
        # visited and enqueue it
        queue.append(s)
        visited[s] = True

        while queue:

            # Dequeue a vertex from
            # queue and print it
            s = queue.pop(0)
            print (s, end = " ")

            # Get all adjacent vertices of the
            # dequeued vertex s. If a adjacent
            # has not been visited, then mark it
            # visited and enqueue it
            for i in self.graph[s]:
                if visited[i] == False:
                    queue.append(i)
                    visited[i] = True

# Driver code

# Create a graph given in
# the above diagram
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)

print ("Following is Breadth First Traversal"
                " (starting from vertex 2)")
g.BFS(2)

# This code is contributed by Neelam Yadav

خروجی:

Following is Breadth First Traversal (starting from vertex 2)
۲ ۰ ۳ ۱

زمان پیچیدگی: O(V+E) که در آن V تعداد رئوس در گراف و E تعداد یال‌ها در گراف است.

جستجوی عمقی یا DFS

پیمایش به روش جستجوی عمقی برای یک گراف مشابه پیمایش عمقی درخت است. تنها تفاوت این است که برخلاف درخت‌ها، گراف‌ها ممکن است شامل چرخه‌ها باشند و یک گره ممکن است دو بار بازدید شود. برای جلوگیری از پردازش دوباره یک گره، از یک آرایه بولی visited استفاده می‌کنیم.

الگوریتم:

• یک تابع بازگشتی ایجاد کن که شاخص گره و آرایه visited را دریافت کند.
• گره فعلی را به عنوان بازدید شده علامت‌گذاری کرده و آن را چاپ کن.
• تمام گره‌های مجاور و علامت‌گذاری نشده را پیمایش کرده و تابع بازگشتی را برای گره‌های مجاور فراخوانی کن.

# Python3 program to print DFS traversal
# from a given graph
from collections import defaultdict

# This class represents a directed graph using
# adjacency list representation


class Graph:

    # Constructor
    def __init__(self):

        # default dictionary to store graph
        self.graph = defaultdict(list)

    # function to add an edge to graph
    def addEdge(self, u, v):
        self.graph[u].append(v)

    # A function used by DFS
    def DFSUtil(self, v, visited):

        # Mark the current node as visited
        # and print it
        visited.add(v)
        print(v, end=' ')

        # Recur for all the vertices
        # adjacent to this vertex
        for neighbour in self.graph[v]:
            if neighbour not in visited:
                self.DFSUtil(neighbour, visited)

    # The function to do DFS traversal. It uses
    # recursive DFSUtil()
    def DFS(self, v):

        # Create a set to store visited vertices
        visited = set()

        # Call the recursive helper function
        # to print DFS traversal
        self.DFSUtil(v, visited)

# Driver code


# Create a graph given
# in the above diagram
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)

print("Following is DFS from (starting from vertex 2)")
g.DFS(2)

خروجی:

Following is DFS from (starting from vertex 2)
۲ ۰ ۱ ۳

زمان پیچیدگی: O(V + E)، که در آن V تعداد رئوس و E تعداد یال‌ها در گراف است.

نتیجه گیری

درک مفاهیم ساختمان داده در پایتون برای سازمان‌دهی و مدیریت داده‌ها در برنامه‌ها لازم و ضروری است. این ساختارها با ارائه راه‌حل‌های بهینه برای ذخیره‌سازی و دسترسی به داده‌ها، به توسعه‌دهندگان کمک می‌کنند تا برنامه‌های کارآمدتر و مقیاس‌پذیرتری ایجاد کنند. پایتون با ویژگی‌های منحصر به‌فرد خود، مانند سادگی در استفاده و پیاده‌سازی، امکان استفاده از ساختارهای داده مختلف مانند لیست‌ها، دیکشنری‌ها و تاپل‌ها را به راحتی فراهم می‌آورد.

این زبان به‌ویژه برای یادگیری مفاهیم پایه‌ای ساختمان داده‌ ها مناسب است و به توسعه‌دهندگان امکان می‌دهد تا از این ساختمان داده در حل مسائل مختلف به‌طور بهینه استفاده کنند. علاوه بر این، توانایی پایتون در پشتیبانی از ساختمان داده‌های پیشرفته‌تری مانند درخت‌ها و گراف‌ها، انعطاف‌پذیری این زبان را برای پروژه‌های پیچیده‌تر بیشتر می‌کند. به طور کلی، پایتون با ارائه ساختمان داده‌ قدرتمند و کاربردی، ابزارهایی مناسب برای هر سطح از توسعه‌دهندگان فراهم می‌کند تا بتوانند به بهترین نحو ممکن نیازهای برنامه‌نویسی خود را برطرف کنند.