Структури даних це спосіб організації даних для більш ефективного доступу до них залежно від ситуації. Структури даних є основою будь-якої мови програмування, навколо якої будується програма. Python допомагає простіше вивчити основи цих структур даних порівняно з іншими мовами програмування.
У цій статті ми обговоримо структури даних у мові програмування Python і те, як вони пов’язані з деякими конкретними вбудованими структурами даних, як-от кортежі списків, словники тощо, а також деякі розширені структури даних, як-от дерева, графіки тощо.
списки
Списки Python схожі на масиви, оголошені в інших мовах, які є впорядкованою колекцією даних. Він дуже гнучкий, оскільки елементи в списку не обов’язково мають бути одного типу.
Реалізація списку Python подібна до Vectors у C++ або ArrayList у JAVA. Дорогою операцією є вставлення або видалення елемента з початку списку, оскільки всі елементи потрібно зсунути. Вставлення та видалення в кінці списку також може бути дорогим у випадку, коли попередньо виділена пам'ять стає повною.
Ми можемо створити список у Python, як показано нижче.
Приклад: створення списку Python
Python3
List> => [>1>,>2>,>3>,>'GFG'>,>2.3>]> print>(>List>)> |
>
>Вихід
[1, 2, 3, 'GFG', 2.3]>
До елементів списку можна отримати доступ за призначеним індексом. У python початковий індекс списку послідовність дорівнює 0, а кінцевий індекс – (якщо є N елементів) N-1.
Приклад: операції зі списками Python
Python3
# Creating a List with> # the use of multiple values> List> => [>'Geeks'>,>'For'>,>'Geeks'>]> print>(>'
List containing multiple values: '>)> print>(>List>)> # Creating a Multi-Dimensional List> # (By Nesting a list inside a List)> List2>=> [[>'Geeks'>,>'For'>], [>'Geeks'>]]> print>(>'
Multi-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>])> |
>
.наступний java
>Вихід
List containing multiple values: ['Geeks', 'For', 'Geeks'] Multi-Dimensional List: [['Geeks', 'For'], ['Geeks']] Accessing element from the list Geeks Geeks Accessing element using negative indexing Geeks Geeks>
Словник
Словник Python це як хеш-таблиці в будь-якій іншій мові з часовою складністю O(1). Це невпорядкована колекція значень даних, яка використовується для зберігання значень даних, як-от карта, яка, на відміну від інших типів даних, які містять лише одне значення як елемент, Словник містить пару ключ:значення. Ключ-значення надано в словнику, щоб зробити його більш оптимізованим.
Індексування словника Python здійснюється за допомогою ключів. Це будь-який хешований тип, тобто об’єкт, який ніколи не може змінюватися, як рядки, числа, кортежі тощо. Ми можемо створити словник за допомогою фігурних дужок ({}) або розуміння словника .
Приклад: операції словника Python
Python3
# Creating a Dictionary> Dict> => {>'Name'>:>'Geeks'>,>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': 'Geeks', 1: [1, 2, 3, 4]} Accessing a element using key: Geeks Accessing a element using get: [1, 2, 3, 4] {1: 1, 2: 4, 3: 9, 4: 16, 5: 25}> Кортеж
Python Tuple це набір об’єктів Python, схожий на список, але кортежі є незмінними за своєю природою, тобто елементи в кортежі не можна додавати або видаляти після створення. Як і список, кортеж також може містити елементи різних типів.
У Python кортежі створюються шляхом розміщення послідовності значень, розділених «комою» з використанням або без використання дужок для групування послідовності даних.
Примітка: Кортежі також можна створити з одного елемента, але це трохи складно. Наявності одного елемента в дужках недостатньо, має бути кінцева «кома», щоб зробити це кортежем.
Приклад: операції кортежу Python
Python3
# Creating a Tuple with> # the use of Strings> Tuple> => (>'Geeks'>,>'For'>)> print>(>'
Tuple with the use of String: '>)> print>(>Tuple>)> > # Creating a Tuple with> # the use of list> list1>=> [>1>,>2>,>4>,>5>,>6>]> print>(>'
Tuple using List: '>)> Tuple> => tuple>(list1)> # Accessing element using indexing> print>(>'First element of tuple'>)> print>(>Tuple>[>0>])> # Accessing element from last> # negative indexing> print>(>'
Last element of tuple'>)> print>(>Tuple>[>->1>])> > print>(>'
Third last element of tuple'>)> print>(>Tuple>[>->3>])> |
>
>Вихід
Tuple with the use of String: ('Geeks', 'For') Tuple using List: First element of tuple 1 Last element of tuple 6 Third last element of tuple 4> встановити
Набір Python це невпорядкована колекція даних, яка є змінною та не допускає повторення елементів. Набори в основному використовуються для тестування членства та усунення повторюваних записів. Структура даних, яка використовується в цьому, є хешуванням, популярною технікою для виконання вставки, видалення та обходу в середньому в O(1).
Якщо в одній позиції індексу присутні кілька значень, тоді значення додається до цієї позиції індексу, щоб сформувати зв’язаний список. У CPython Sets реалізовано за допомогою словника з фіктивними змінними, де ключові істоти є членами набору з більшою оптимізацією до часової складності.
Реалізація набору:
Набори з численними операціями на одній HashTable:
Приклад: Python Set Operations
Python3
# Creating a Set with> # a mixed type of values> # (Having numbers and strings)> Set> => set>([>1>,>2>,>'Geeks'>,>4>,>'For'>,>6>,>'Geeks'>])> print>(>'
Set with the use of Mixed Values'>)> print>(>Set>)> # Accessing element using> # for loop> print>(>'
Elements of set: '>)> for> i>in> Set>:> >print>(i, end>=>' '>)> print>()> # Checking the element> # using in keyword> print>(>'Geeks'> in> Set>)> |
>
>Вихід
Set with the use of Mixed Values {1, 2, 'Geeks', 4, 6, 'For'} Elements of set: 1 2 Geeks 4 6 For True> Заморожені набори
Закріплені набори в Python — це незмінні об’єкти, які підтримують лише методи й оператори, які створюють результат, не впливаючи на заморожений набір або набори, до яких вони застосовуються. Хоча елементи набору можна змінити в будь-який час, елементи замороженого набору залишаються незмінними після створення.
Якщо параметри не передано, він повертає порожній заморожений набір.
Python3
# 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>(>'
Frozen 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'})> Рядок
Рядки Python — це масиви байтів, що представляють символи Unicode. Простіше кажучи, рядок — це незмінний масив символів. Python не має символьного типу даних, окремий символ є просто рядком довжиною 1.
Примітка: Оскільки рядки незмінні, зміна рядка призведе до створення нової копії.
Приклад: операції над рядками Python
Python3
String>=> 'Welcome to GeeksForGeeks'> print>(>'Creating String: '>)> print>(String)> > # Printing First character> print>(>'
First character of String is: '>)> print>(String[>0>])> > # Printing Last character> print>(>'
Last character of String is: '>)> print>(String[>->1>])> |
>
>Вихід
Creating String: Welcome to GeeksForGeeks First character of String is: W Last character of String is: s>
Масив байтів
Python Bytearray дає змінну послідовність цілих чисел у діапазоні 0 <= x < 256.
Приклад: операції Python Bytearray
Python3
# Creating bytearray> a>=> bytearray((>12>,>8>,>25>,>2>))> print>(>'Creating Bytearray:'>)> print>(a)> # accessing elements> print>(>'
Accessing Elements:'>, a[>1>])> # modifying elements> a[>1>]>=> 3> print>(>'
After Modifying:'>)> print>(a)> # Appending elements> a.append(>30>)> print>(>'
After Adding Elements:'>)> print>(a)> |
>
>Вихід
Creating Bytearray: bytearray(b'x0cx08x19x02') Accessing Elements: 8 After Modifying: bytearray(b'x0cx03x19x02') After Adding Elements: bytearray(b'x0cx03x19x02x1e')>
Дотепер ми вивчили всі структури даних, вбудовані в ядро Python. Тепер давайте глибше зануримося в Python і подивимося на модуль колекцій, який надає деякі контейнери, корисні в багатьох випадках і надають більше функцій, ніж визначені вище функції.
Модуль колекцій
Модуль колекції Python був представлений для покращення функціональності вбудованих типів даних. Він містить різні контейнери, давайте розглянемо кожен з них докладніше.
Лічильники
Лічильник є підкласом словника. Він використовується для збереження підрахунку елементів у ітерації у формі невпорядкованого словника, де ключ представляє елемент у ітерації, а значення — кількість цього елемента в ітерації. Це еквівалентно пакету або мультинабору інших мов.
Приклад: операції лічильника Python
Python3
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 також є підкласом словника, але на відміну від словника, він запам’ятовує порядок, у якому було вставлено ключі.
Приклад: операції Python OrderedDict
Python3
from> collections>import> OrderedDict> print>(>'Before deleting:
'>)> od>=> OrderedDict()> od[>'a'>]>=> 1> od[>'b'>]>=> 2> od[>'c'>]>=> 3> od[>'d'>]>=> 4> for> key, value>in> od.items():> >print>(key, value)> print>(>'
After deleting:
'>)> od.pop(>'c'>)> for> key, value>in> od.items():> >print>(key, value)> print>(>'
After re-inserting:
'>)> 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(), передаючи тип даних як аргумент.
Примітка: default_factory — це функція, яка надає значення за замовчуванням для створеного словника. Якщо цей параметр відсутній, виникає KeyError.
Приклад: операції Python DefaultDict
Python3
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(, {1: 2, 2: 3, 3: 1, 4: 2})> ChainMap
ChainMap інкапсулює багато словників в один блок і повертає список словників. Коли потрібно знайти ключ, пошук виконується один за одним у всіх словниках, доки ключ не буде знайдено.
Приклад: операції Python ChainMap
Python3
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}) 1> KeyError: 'g'>
NamedTuple
А NamedTuple повертає об’єкт кортежу з іменами для кожної позиції, яких бракує звичайним кортежам. Наприклад, розглянемо кортеж імен student, де перший елемент представляє fname, другий представляє lname, а третій елемент представляє DOB. Припустімо, що для виклику fname замість запам’ятовування позиції індексу ви можете викликати елемент за допомогою аргументу fname, тоді отримати доступ до елемента кортежів буде дуже легко. Ця функція надається NamedTuple.
Приклад: операції Python NamedTuple
Python3
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 (двостороння черга) це оптимізований список для швидшого додавання та висування з обох боків контейнера. Він забезпечує O(1) часову складність для операцій додавання та висунення порівняно зі списком із O(n) часовою складністю.
Python Deque реалізовано за допомогою подвійно зв’язаних списків, тому продуктивність для довільного доступу до елементів становить O(n).
Приклад: операції Python Deque
Python3
# 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 — це контейнер, схожий на словник, який діє як обгортка навколо об’єктів словника. Цей контейнер використовується, коли хтось хоче створити власний словник із зміненими або новими функціями.
Приклад: Python UserDict
Python3
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 — це контейнер, схожий на список, який діє як обгортка навколо об’єктів списку. Це корисно, коли хтось хоче створити власний список із зміненими чи додатковими функціями.
Приклади: Python UserList
Python3
# 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 [1, 2, 3, 4] After Insertion [1, 2, 3, 4, 5]>
RuntimeError: Deletion not allowed>
UserString
UserString — це рядковий контейнер, і так само, як UserDict і UserList, він діє як обгортка навколо рядкових об’єктів. Він використовується, коли хтось хоче створити власні рядки з деякими зміненими чи додатковими функціями.
Приклад: Python UserString
Python3
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(>'Geeks'>)> 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: Geeks String After Appending: Geekss String after Removing: Gkss>
Тепер, після вивчення всіх структур даних, давайте розглянемо деякі розширені структури даних, такі як стек, черга, графік, пов’язаний список тощо, які можна використовувати в мові Python.
Зв'язаний список
Зв’язаний список — це лінійна структура даних, у якій елементи не зберігаються в безперервних розташуваннях пам’яті. Елементи у зв’язаному списку зв’язуються за допомогою вказівників, як показано на зображенні нижче:
Зв’язаний список представлений вказівником на перший вузол зв’язаного списку. Перший вузол називається головкою. Якщо пов’язаний список порожній, тоді значення заголовка дорівнює NULL. Кожен вузол у списку складається щонайменше з двох частин:
- Дані
- Покажчик (або посилання) на наступний вузол
Приклад: визначення пов’язаного списку в Python
Python3
# 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> |
>
>
Давайте створимо простий зв’язаний список із 3 вузлами.
Python3
# 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> >| | |> >| | |> >+----+------+ +----+------+ +----+------+> >| 1 | 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> >| | |> >| | |> >+----+------+ +----+------+ +----+------+> >| 1 | o-------->| 2 | нуль | | 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> >| | |> >| | |> >+----+------+ +----+------+ +----+------+> >| 1 | o-------->| 2 | о-------->| 3 | null |> >+----+------+ +----+------+ +----+------+> >'''> |
>
>
Обхід пов’язаного списку
У попередній програмі ми створили простий зв’язаний список із трьома вузлами. Переглянемо створений список і надрукуємо дані кожного вузла. Для обходу давайте напишемо функцію загального призначення printList(), яка друкує будь-який заданий список.
Python3
# 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()> |
>
>Вихід
1 2 3>
Стек
А стек це лінійна структура даних, яка зберігає елементи за принципом 'останній прийшов/перший вийшов' (LIFO) або 'перший прийшов/останній вийшов' (FILO). У стеку новий елемент додається на одному кінці, а елемент видаляється лише з цього кінця. Операції вставки та видалення часто називають push і pop.
Функції, пов’язані зі стеком:
- empty() – Повертає, чи стек порожній – Часова складність: O(1) size() – Повертає розмір стеку – Часова складність: O(1) top() – Повертає посилання на найвищий елемент стеку – Часова складність: O(1) push(a) – Вставляє елемент «a» у верхній частині стека – Часова складність: O(1) pop() – Видаляє найвищий елемент стеку – Часова складність: O( 1)
Реалізація стеку Python
Стек у Python можна реалізувати такими способами:
- список
- Collections.deque
- queue.LifoQueue
Реалізація за допомогою List
Вбудований список структур даних Python можна використовувати як стек. Замість push(), append() використовується для додавання елементів у верхню частину стека, тоді як pop() видаляє елемент у порядку LIFO.
Python3
stack>=> []> # append() function to push> # element in the stack> stack.append(>'g'>)> stack.append(>'f'>)> stack.append(>'g'>)> print>(>'Initial stack'>)> print>(stack)> # pop() function to pop> # element from stack in> # LIFO order> print>(>'
Elements popped from stack:'>)> print>(stack.pop())> print>(stack.pop())> print>(stack.pop())> print>(>'
Stack after elements are popped:'>)> print>(stack)> # uncommenting print(stack.pop())> # will cause an IndexError> # as the stack is now empty> |
>
>Вихід
Initial stack ['g', 'f', 'g'] Elements popped from stack: g f g Stack after elements are popped: []>
Реалізація за допомогою collections.deque:
Стек Python можна реалізувати за допомогою класу deque з модуля collections. Deque є кращим над списком у випадках, коли нам потрібні швидші операції додавання та висунення з обох кінців контейнера, оскільки deque забезпечує O(1) часову складність для операцій додавання та вискакування порівняно зі списком, який забезпечує O(n) часова складність.
Python3
from> collections>import> deque> stack>=> deque()> # append() function to push> # element in the stack> stack.append(>'g'>)> stack.append(>'f'>)> stack.append(>'g'>)> print>(>'Initial stack:'>)> print>(stack)> # pop() function to pop> # element from stack in> # LIFO order> print>(>'
Elements popped from stack:'>)> print>(stack.pop())> print>(stack.pop())> print>(stack.pop())> print>(>'
Stack after elements are popped:'>)> print>(stack)> # uncommenting print(stack.pop())> # will cause an IndexError> # as the stack is now empty> |
>
>Вихід
Initial stack: deque(['g', 'f', 'g']) Elements popped from stack: g f g Stack after elements are popped: deque([])>
Реалізація з використанням модуля черги
Модуль черги також має чергу LIFO, яка в основному є стеком. Дані вставляються в чергу за допомогою функції put(), а get() вилучає дані з черги.
Python3
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(>'g'>)> stack.put(>'f'>)> stack.put(>'g'>)> print>(>'Full: '>, stack.full())> print>(>'Size: '>, stack.qsize())> # get() function to pop> # element from stack in> # LIFO order> print>(>'
Elements popped from the stack'>)> print>(stack.get())> print>(stack.get())> print>(stack.get())> print>(>'
Empty: '>, stack.empty())> |
>
>Вихід
0 Full: True Size: 3 Elements popped from the stack g f g Empty: True>
Черга
Як стек, черга це лінійна структура даних, яка зберігає елементи в порядку FIFO (First In First Out). У черзі спочатку видаляється останній нещодавно доданий елемент. Хорошим прикладом черги є будь-яка черга споживачів для ресурсу, де споживач, який був першим, обслуговується першим.
Операції, пов’язані з чергою:
- Поставити в чергу: додає елемент до черги. Якщо черга заповнена, це вважається умовою переповнення – Часова складність: O(1) Вилучення з черги: видаляє елемент із черги. Елементи висуваються в тому самому порядку, в якому вони натискаються. Якщо черга порожня, це означає, що це умова недостатнього переповнення – Часова складність: O(1) Передня частина: отримати передній елемент із черги – Часова складність: O(1) Задня частина: отримати останній елемент із черги – Часова складність : O(1)
Реалізація черги Python
Черга в Python може бути реалізована такими способами:
- список
- колекції.deque
- хвіст.хвіст
Реалізація за допомогою списку
Замість enqueue() і dequeue() використовуються функції append() і pop().
Python3
# Initializing a queue> queue>=> []> # Adding elements to the queue> queue.append(>'g'>)> queue.append(>'f'>)> queue.append(>'g'>)> print>(>'Initial queue'>)> print>(queue)> # Removing elements from the queue> print>(>'
Elements dequeued from queue'>)> print>(queue.pop(>0>))> print>(queue.pop(>0>))> print>(queue.pop(>0>))> print>(>'
Queue 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 g f g Queue after removing elements []>
Реалізація за допомогою collections.deque
Deque є кращим над списком у випадках, коли нам потрібні швидші операції додавання та висунення з обох кінців контейнера, оскільки deque забезпечує O(1) часову складність для операцій додавання та вискакування порівняно зі списком, який забезпечує O(n) часова складність.
Python3
from> collections>import> deque> # Initializing a queue> q>=> deque()> # Adding elements to a queue> q.append(>'g'>)> q.append(>'f'>)> q.append(>'g'>)> print>(>'Initial queue'>)> print>(q)> # Removing elements from a queue> print>(>'
Elements dequeued from the queue'>)> print>(q.popleft())> print>(q.popleft())> print>(q.popleft())> print>(>'
Queue after removing elements'>)> print>(q)> # Uncommenting q.popleft()> # will raise an IndexError> # as queue is now empty> |
>
>Вихід
Initial queue deque(['g', 'f', 'g']) Elements dequeued from the queue g f g Queue after removing elements deque([])>
Реалізація за допомогою черги.Queue
символ до рядка java
queue.Queue(maxsize) ініціалізує змінну до максимального розміру maxsize. Максимальний розмір нуля «0» означає нескінченну чергу. Ця черга відповідає правилу FIFO.
Python3
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(>'g'>)> q.put(>'f'>)> q.put(>'g'>)> # Return Boolean for Full> # Queue> print>(>'
Full: '>, q.full())> # Removing element from queue> print>(>'
Elements dequeued from the queue'>)> print>(q.get())> print>(q.get())> print>(q.get())> # Return Boolean for Empty> # Queue> print>(>'
Empty: '>, q.empty())> q.put(>1>)> print>(>'
Empty: '>, q.empty())> print>(>'Full: '>, q.full())> # This would result into Infinite> # Loop as the Queue is empty.> # print(q.get())> |
>
>Вихід
0 Full: True Elements dequeued from the queue g f g Empty: True Empty: False Full: False>
Пріоритетна черга
Пріоритетні черги це абстрактні структури даних, де кожне дані/значення в черзі мають певний пріоритет. Наприклад, в авіакомпаніях багаж під назвою Business або First-class прибуває раніше за інших. Пріоритетна черга — це розширення черги з такими властивостями.
- Елемент з високим пріоритетом вилучається з черги перед елементом з низьким пріоритетом.
- Якщо два елементи мають однаковий пріоритет, вони обслуговуються відповідно до свого порядку в черзі.
Python3
# 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())> |
>
>Вихід
12 1 14 7 14 12 7 1>
Черга купи (або heapq)
модуль heapq у Python забезпечує структуру даних купи, яка в основному використовується для представлення пріоритетної черги. Властивість цієї структури даних у Python полягає в тому, що кожен раз, коли найменший елемент купи виривається (min-heap). Кожного разу, коли елементи штовхаються або висуваються, структура купи зберігається. Елемент heap[0] також кожного разу повертає найменший елемент.
Він підтримує витяг і вставку найменшого елемента в O(log n) разів.
Python3
# 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>
Найвищий вузол дерева називається коренем, тоді як найнижчі вузли або вузли без дітей називаються листовими вузлами. Вузли, які знаходяться безпосередньо під вузлом, називаються його дочірніми, а вузли, які знаходяться безпосередньо над чимось, називаються його батьківськими.
Бінарне дерево — це дерево, елементи якого можуть мати майже двох дочірніх елементів. Оскільки кожен елемент у бінарному дереві може мати лише 2 дочірні елементи, ми зазвичай називаємо їх лівими та правими дочірніми елементами. Вузол двійкового дерева містить такі частини.
- Дані
- Покажчик на ліву дитину
- Вказівник на праву дитину
Приклад: визначення класу вузла
Python3
# 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> |
>
>
Тепер давайте створимо дерево з 4 вузлами на Python. Припустімо, що структура дерева виглядає так:
tree ---- 1 <-- root / 2 3 / 4>
Приклад: додавання даних до дерева
Python3
# 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> >1> >/> >None None'''> root.left>=> Node(>2>);> root.right>=> Node(>3>);> ''' 2 and 3 become left and right children of 1> >1> >/> >2 3> >/ /> None None None None'''> root.left.left>=> Node(>4>);> '''4 becomes left child of 2> >1> >/> >2 3> >/ /> 4 None None None> /> None None'''> |
>
>
Обхід дерева
Дерева можна обійти різними способами. Нижче наведені способи, які зазвичай використовуються для обходу дерев. Давайте розглянемо дерево нижче –
tree ---- 1 <-- root / 2 3 / 4 5>
Перші обходи глибини:
- У порядку (ліворуч, корінь, праворуч): 4 2 5 1 3
- Попереднє замовлення (Root, Left, Right): 1 2 4 5 3
- Постпорядок (ліворуч, праворуч, корінь): 4 5 2 3 1
Алгоритм у порядку (дерево)
- Перейти до лівого піддерева, тобто викликати Inorder(left-subtree)
- Відвідайте корінь.
- Перейти до правого піддерева, тобто викликати Inorder(right-subtree)
Попереднє замовлення алгоритму (дерево)
- Відвідайте корінь.
- Перейти до лівого піддерева, тобто викликати Preorder(left-subtree)
- Перейти до правого піддерева, тобто викликати Preorder(right-subtree)
Алгоритм Поштовий переказ (дерево)
- Перейти до лівого піддерева, тобто викликати Postorder(left-subtree)
- Перейти до правого піддерева, тобто викликати Postorder(right-subtree)
- Відвідайте корінь.
Python3
# 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>(>'
Inorder traversal of binary tree is'>)> printInorder(root)> print>(>'
Postorder traversal of binary tree is'>)> printPostorder(root)> |
>
>Вихід
Preorder traversal of binary tree is 1 2 4 5 3 Inorder traversal of binary tree is 4 2 5 1 3 Postorder traversal of binary tree is 4 5 2 3 1>
Часова складність – O(n)
Обхід порядку в ширину або рівня
Обхід порядку рівня дерева — це обхід дерева в ширину. Порядок обходу рівня вищевказаного дерева 1 2 3 4 5.
Для кожного вузла спочатку відвідується вузол, а потім його дочірні вузли поміщаються в чергу FIFO. Нижче наведено алгоритм для того ж –
- Створіть порожню чергу q
- temp_node = root /*почати з кореня*/
- Цикл, поки temp_node не NULL
- надрукувати temp_node->data.
- Поставте в чергу дочірніх елементів temp_node (спочатку лівих, а потім правих) до q
- Виключити вузол із q
Python3
# 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 - 1 2 3 4 5>
Часова складність: O(n)
Графік
А графік це нелінійна структура даних, що складається з вузлів і ребер. Вузли іноді також називають вершинами, а ребра — лініями або дугами, які з’єднують будь-які два вузли в графі. Більш формально граф можна визначити як граф, що складається зі скінченного набору вершин (або вузлів) і набору ребер, які з’єднують пару вузлів.
У наведеному вище графіку множина вершин V = {0,1,2,3,4} і множина ребер E = {01, 12, 23, 34, 04, 14, 13}.
Наступні два представлення графа є найбільш часто використовуваними.
- Матриця суміжності
- Список суміжності
Матриця суміжності
Матриця суміжності — це двовимірний масив розміром V x V, де V — кількість вершин у графі. Нехай двовимірний масив буде adj[][], слот adj[i][j] = 1 вказує, що існує ребро від вершини i до вершини j. Матриця суміжності для неорієнтованого графа завжди симетрична. Матриця суміжності також використовується для представлення зважених графів. Якщо adj[i][j] = w, то існує ребро від вершини i до вершини j з вагою w.
Python3
# 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())> |
>
>
Вихід
Вершини графа
['a', 'b', 'c', 'd', 'e', 'f']
Ребра графа
[('a', 'c', 20), ('a', 'e', 10), ('b', 'c', 30), ('b', 'e', 40), ( 'c', 'a', 20), ('c', 'b', 30), ('d', 'e', 50), ('e', 'a', 10), ('e' ', 'b', 40), ('e', 'd', 50), ('e', 'f', 60), ('f', 'e', 60)]
Матриця суміжності графа
[[-1, -1, 20, -1, 10, -1], [-1, -1, 30, -1, 40, -1], [20, 30, -1, -1, -1 , -1], [-1, -1, -1, -1, 50, -1], [10, 40, -1, 50, -1, 60], [-1, -1, -1, -1, 60, -1]]
Список суміжності
Використовується масив списків. Розмір масиву дорівнює кількості вершин. Нехай масив буде масивом []. Масив записів [i] представляє список вершин, суміжних з i-ю вершиною. Це подання також можна використовувати для представлення зваженого графіка. Ваги ребер можна представити у вигляді списків пар. Нижче наведено представлення списку суміжності наведеного вище графіка.
Python3
# 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 {}
head'>.>format>(i), end>=>'')> >temp>=> self>.graph[i]> >while> temp:> >print>(>' ->{}'>.>format>(temp.vertex), end>=>'')> >temp>=> temp.>next> >print>(>'
'>)> # 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 Список суміжності голови вершини 1 -> 4 -> 3 -> 2 -> 0 Список суміжності голови вершини 2 -> 3 -> 1 Список суміжності голови вершини 3 -> 4 -> 2 -> 1 Суміжність список головок вершини 4 -> 3 -> 1 -> 0>>Обхід графа
Пошук у ширину або BFS
Обхід у ширину для графа схоже на обхід дерева в ширину. Єдина заковика тут полягає в тому, що на відміну від дерев, графи можуть містити цикли, тож ми можемо знову прийти до того самого вузла. Щоб уникнути обробки вузла більше одного разу, ми використовуємо булевий відвіданий масив. Для простоти передбачається, що всі вершини досяжні з початкової вершини.
Наприклад, у наступному графі ми починаємо обхід з вершини 2. Коли ми приходимо до вершини 0, ми шукаємо всі суміжні з нею вершини. 2 також є суміжною вершиною 0. Якщо ми не позначаємо відвідані вершини, тоді 2 буде оброблено знову, і це стане незавершеним процесом. Обхід у ширину наступного графіка дорівнює 2, 0, 3, 1.
Python3
# 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) 2 0 3 1>
Часова складність: O(V+E), де V — кількість вершин у графі, а E — кількість ребер у графі.
Пошук за глибиною або DFS
Перший обхід глибини для графа схоже на обхід дерева за глибиною. Єдина заковика тут полягає в тому, що на відміну від дерев, графи можуть містити цикли, вузол можна відвідати двічі. Щоб уникнути обробки вузла більше одного разу, використовуйте булевий відвіданий масив.
Алгоритм:
- Створіть рекурсивну функцію, яка приймає індекс вузла та відвіданого масиву.
- Позначте поточний вузол як відвіданий і надрукуйте вузол.
- Перейдіть по всіх суміжних і непозначених вузлах і викличте рекурсивну функцію з індексом сусіднього вузла.
Python3
# 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) 2 0 1 3>
Часова складність: O(V + E), де V — кількість вершин, а E — кількість ребер у графі.