Duomenų struktūros yra būdas tvarkyti duomenis taip, kad juos būtų galima pasiekti efektyviau, atsižvelgiant į situaciją. Duomenų struktūros yra bet kurios programavimo kalbos, pagal kurią kuriama programa, pagrindai. Python padeda išmokti šių duomenų struktūrų pagrindus paprasčiau, palyginti su kitomis programavimo kalbomis.

Šiame straipsnyje aptarsime duomenų struktūras Python programavimo kalboje ir kaip jos susijusios su tam tikromis įmontuotomis duomenų struktūromis, tokiomis kaip sąrašų eilutės, žodynai ir kt., taip pat kai kurios išplėstinės duomenų struktūros, pvz., medžiai, grafikai ir kt.

Sąrašai

Python sąrašai yra kaip masyvai, deklaruojami kitomis kalbomis, o tai yra tvarkingas duomenų rinkinys. Tai labai lanksti, nes sąraše esantys elementai nebūtinai turi būti to paties tipo.

Python List įgyvendinimas yra panašus į Vectors C++ arba ArrayList JAVA. Brangi operacija yra elemento įterpimas arba ištrynimas iš sąrašo pradžios, nes visus elementus reikia perkelti. Įterpimas ir ištrynimas sąrašo pabaigoje taip pat gali kainuoti, jei iš anksto paskirstyta atmintis prisipildo.

Mes galime sukurti sąrašą python, kaip parodyta žemiau.

Pavyzdys: Python sąrašo kūrimas

Python3

List> => [> 1> ,> 2> ,> 3> ,> 'GFG'> ,> 2.3> ]> print> (> List> )>

Išvestis

[1, 2, 3, 'GFG', 2.3] 

Sąrašo elementus galima pasiekti naudojant priskirtą indeksą. Python sąrašo pradžios indekse seka yra 0, o pabaigos indeksas (jei yra N elementų) N-1.

Pavyzdys: Python sąrašo operacijos

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> ])>

Išvestis

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 

Žodynas

Python žodynas yra kaip maišos lentelės bet kuria kita kalba, kurios laiko sudėtingumas yra O(1). Tai netvarkingas duomenų reikšmių rinkinys, naudojamas duomenų reikšmėms, pvz., žemėlapiui, saugoti. Žodynas, skirtingai nei kiti duomenų tipai, kurių elementas turi tik vieną reikšmę, turi rakto:reikšmės porą. Rakto reikšmė pateikiama žodyne, kad ji būtų labiau optimizuota.

Python žodyno indeksavimas atliekamas raktų pagalba. Jie yra bet kokio tipo maišos, t. y. objektai, kurie niekada negali keistis, pvz., eilutės, skaičiai, eilutės ir kt. Žodyną galime sukurti naudodami riestinius skliaustus ({}) arba žodyno supratimas .

Pavyzdys: Python žodyno operacijos

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)>

Išvestis

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} 

Tuple

Python Tuple yra Python objektų rinkinys, panašus į sąrašą, tačiau kortelių pobūdis yra nekintantis, t. Kaip ir sąraše, sekcijoje taip pat gali būti įvairių tipų elementų.

„Python“ programoje eilutės sukuriamos pateikiant reikšmių seką, atskirtą „kableliais“, naudojant skliaustus duomenų sekos grupavimui arba be jų.

Pastaba: Korteles taip pat galima sukurti su vienu elementu, tačiau tai yra šiek tiek sudėtinga. Vieno elemento skliausteliuose neužtenka, turi būti „kablelis“, kad jis būtų eilutė.

Pavyzdys: Python Tuple operacijos

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> ])>

Išvestis

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 

Nustatyti

Python rinkinys yra netvarkingas duomenų rinkinys, kuris yra kintamas ir neleidžia pasikartoti elementų. Rinkiniai iš esmės naudojami narystės testavimui ir pasikartojančių įrašų pašalinimui. Čia naudojama duomenų struktūra yra maišos apdorojimas, populiarus metodas, skirtas vidutiniškai įterpti, ištrinti ir pereiti O(1).

Jei toje pačioje indekso pozicijoje yra kelios reikšmės, tada vertė pridedama prie tos indekso pozicijos, kad būtų sudarytas susietasis sąrašas. „CPython Sets“ yra įdiegtas naudojant žodyną su netikrais kintamaisiais, kur pagrindiniai elementai nustatomi labiau optimizuodami laiko sudėtingumą.

Nustatyti įgyvendinimą:

Rinkiniai su daugybe operacijų vienoje maišos lentelėje:

Pavyzdys: Python rinkinio operacijos

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> )>

Išvestis

Set with the use of Mixed Values {1, 2, 'Geeks', 4, 6, 'For'} Elements of set: 1 2 Geeks 4 6 For True 

Užšaldyti rinkiniai

„Python“ fiksuoti rinkiniai yra nekintantys objektai, kurie palaiko tik metodus ir operatorius, kurie sukuria rezultatą, nepaveikdami fiksuoto rinkinio ar rinkinių, kuriems jie taikomi. Nors rinkinio elementus galima bet kada keisti, fiksuoto rinkinio elementai po sukūrimo išlieka tokie patys.

Jei nepateikiami jokie parametrai, jis grąžina tuščią fiksuotą rinkinį.

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')>

Išvestis

Normal Set {'a', 'c', 'b'} Frozen Set frozenset({'g', 'e', 'f'}) 

Styga

Python Strings yra baitų masyvai, vaizduojantys Unicode simbolius. Paprasčiau tariant, eilutė yra nekintantis simbolių masyvas. Python neturi simbolių duomenų tipo, vienas simbolis yra tiesiog eilutė, kurios ilgis yra 1.

Pastaba: Kadangi eilutės yra nekintamos, pakeitus eilutę bus sukurta nauja kopija.

Pavyzdys: Python stygų operacijos

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> ])>

Išvestis

Creating String: Welcome to GeeksForGeeks First character of String is: W Last character of String is: s 

Bytearray

Python Bytearray suteikia kintamą sveikųjų skaičių seką diapazone 0 <= x < 256.

Pavyzdys: Python Bytearray operacijos

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)>

Išvestis

Creating Bytearray: bytearray(b'x0cx08x19x02') Accessing Elements: 8 After Modifying: bytearray(b'x0cx03x19x02') After Adding Elements: bytearray(b'x0cx03x19x02x1e') 

Iki šiol ištyrėme visas duomenų struktūras, kurios yra integruotos į pagrindinį Python. Dabar pasinerkite į Python ir peržiūrėkite rinkinių modulį, kuriame pateikiami kai kurie konteineriai, kurie yra naudingi daugeliu atvejų ir suteikia daugiau funkcijų nei anksčiau apibrėžtos funkcijos.

Kolekcijos modulis

Python rinkimo modulis buvo pristatytas siekiant pagerinti integruotų duomenų tipų funkcionalumą. Jame pateikiami įvairūs konteineriai, pažiūrėkime kiekvieną iš jų išsamiai.

Skaitikliai

Skaitiklis yra žodyno poklasis. Jis naudojamas norint išlaikyti pakartojamo elementų skaičių netvarkingo žodyno pavidalu, kur raktas žymi elementą iteracijoje, o vertė – to elemento skaičių kartotinėje. Tai yra lygiavertis maišui ar kelių kitų kalbų rinkiniui.

Pavyzdys: Python skaitiklio operacijos

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)>

Išvestis

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

UžsakytasDiktas

An UžsakytasDiktas taip pat yra žodyno poklasis, tačiau skirtingai nei žodynas, jis prisimena klavišų įterpimo tvarką.

Pavyzdys: Python OrderedDict operacijos

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)>

Išvestis

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 naudojamas kai kurioms numatytosioms rakto reikšmėms pateikti, kurios neegzistuoja ir niekada nekelia KeyError. Jo objektus galima inicijuoti naudojant DefaultDict() metodą, perduodant duomenų tipą kaip argumentą.

Pastaba: default_factory yra funkcija, kuri suteikia numatytąją sukurto žodyno reikšmę. Jei šio parametro nėra, pakeliama KeyError.

Pavyzdys: Python DefaultDict operacijos

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)>

Išvestis

defaultdict(, {1: 2, 2: 3, 3: 1, 4: 2}) 

Grandininis žemėlapis

„ChainMap“ sujungia daugybę žodynų į vieną vienetą ir pateikia žodynų sąrašą. Kai reikia rasti raktą, po vieną ieškoma visuose žodynuose, kol randamas raktas.

Pavyzdys: Python ChainMap operacijos

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'> ])>

Išvestis

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

KeyError: 'g' 

Pavadinta Tuple

A Pavadinta Tuple grąžina kortelių objektą su pavadinimais kiekvienai pozicijai, kurios trūksta įprastoms kortelėms. Pavyzdžiui, apsvarstykite mokinio pavadinimų eilutę, kur pirmasis elementas reiškia fname, antrasis – lname, o trečiasis – DOB. Tarkime, kad norint iškviesti fname, o ne prisiminti rodyklės padėtį, iš tikrųjų galite iškviesti elementą naudodami argumentą fname, tada bus tikrai lengva pasiekti elementą eilės. Šią funkciją teikia NamedTuple.

Pavyzdys: Python NamedTuple operacijos

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)>

Išvestis

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

Apie ką

Deque (dviguba eilė) yra optimizuotas sąrašas, leidžiantis greičiau pridėti ir iškelti operacijas iš abiejų konteinerio pusių. Jame pateikiamas O(1) laiko sudėtingumas pridėjimo ir iššokimo operacijoms, palyginti su sąrašu su O(n) laiko sudėtingumu.

Python Deque yra įdiegtas naudojant dvigubai susietus sąrašus, todėl atsitiktinės prieigos prie elementų našumas yra O(n).

Pavyzdys: Python Deque operacijos

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)>

Išvestis

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 yra į žodyną panašus konteineris, kuris veikia kaip žodyno objektų įvyniojimas. Šis konteineris naudojamas, kai kas nors nori sukurti savo žodyną su tam tikromis pakeistomis ar naujomis funkcijomis.

Pavyzdys: 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> )>

Išvestis

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

RuntimeError: Deletion not allowed 

Vartotojų sąrašas

„UserList“ yra į sąrašą panašus konteineris, kuris veikia kaip sąrašo objektų apvyniojimas. Tai naudinga, kai kas nors nori sukurti savo sąrašą su tam tikromis pakeistomis ar papildomomis funkcijomis.

Pavyzdžiai: 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()>

Išvestis

Original List [1, 2, 3, 4] After Insertion [1, 2, 3, 4, 5] 

RuntimeError: Deletion not allowed 

UserString

„UserString“ yra į eilutę panašus konteineris ir, kaip ir „UserDict“ bei „UserList“, veikia kaip įvyniojimas aplink eilutės objektus. Jis naudojamas, kai kas nors nori sukurti savo eilutes su tam tikromis modifikuotomis ar papildomomis funkcijomis.

Pavyzdys: 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)>

Išvestis

Original String: Geeks String After Appending: Geekss String after Removing: Gkss 

Išnagrinėję visas duomenų struktūras, pažiūrėkime į kai kurias išplėstines duomenų struktūras, tokias kaip krūva, eilė, grafikas, susietas sąrašas ir kt., kurias galima naudoti Python kalboje.

Susietas sąrašas

Susietas sąrašas yra linijinė duomenų struktūra, kurios elementai nėra saugomi gretimose atminties vietose. Elementai susietame sąraše yra susieti naudojant nuorodas, kaip parodyta toliau pateiktame paveikslėlyje:

Susietą sąrašą rodo žymeklis į pirmąjį susieto sąrašo mazgą. Pirmasis mazgas vadinamas galva. Jei susietas sąrašas tuščias, tada antraštės reikšmė yra NULL. Kiekvienas sąrašo mazgas susideda iš mažiausiai dviejų dalių:

• Duomenys
• Rodyklė (arba nuoroda) į kitą mazgą

Pavyzdys: susieto sąrašo apibrėžimas 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>

Sukurkime paprastą susietą sąrašą su 3 mazgais.

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 | 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> > | | |> > | | |> > +----+------+ +----+------+ +----+------+> > | 1 | o-------->| 2 | o-------->| 3 | null |> > +----+------+ +----+------+ +----+------+> > '''>

Susieto sąrašo peržiūra

Ankstesnėje programoje sukūrėme paprastą susietą sąrašą su trimis mazgais. Pereikime sukurtą sąrašą ir atspausdinkime kiekvieno mazgo duomenis. Norėdami pereiti, parašykite bendros paskirties funkciją printList(), kuri spausdina bet kurį nurodytą sąrašą.

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()>

Išvestis

1 2 3 

Stack

A krūva yra linijinė duomenų struktūra, kurioje elementai saugomi paskutinio įvedimo/pirmo išvežimo (LIFO) arba pirmojo įvedimo/paskutinės išvežimo (FILO) būdu. Į krūvą naujas elementas pridedamas viename gale, o elementas pašalinamas tik iš to galo. Įterpimo ir ištrynimo operacijos dažnai vadinamos push ir pop.

Su kaminu susijusios funkcijos yra šios:

tuščias() – grąžina, ar krūva tuščia – Laiko sudėtingumas: O(1) dydis() – Grąžina krūvos dydį – Laiko sudėtingumas: O(1) top() – Grąžina nuorodą į viršutinį krūvos elementą – Laiko sudėtingumas: O(1) push(a) – Įterpia elementą „a“ krūvos viršuje – Laiko sudėtingumas: O(1) pop() – Ištrina aukščiausią krūvos elementą – Laiko sudėtingumas: O( 1)

Python Stack diegimas

Stack Python gali būti įdiegtas šiais būdais:

• sąrašą
• Kolekcijos.deque
• eilė.LifoQueue

Diegimas naudojant sąrašą

Python integruotas duomenų struktūros sąrašas gali būti naudojamas kaip krūva. Vietoj push(), append() naudojamas elementams pridėti prie krūvos viršaus, o pop() pašalina elementą LIFO tvarka.

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>

Išvestis

Initial stack ['g', 'f', 'g'] Elements popped from stack: g f g Stack after elements are popped: [] 

Diegimas naudojant collections.deque:

Python steką galima įdiegti naudojant deque klasę iš rinkinių modulio. Deque yra teikiama pirmenybė sąrašui tais atvejais, kai reikia greitesnių pridėjimo ir iššokimo operacijų abiejuose konteinerio galuose, nes deque suteikia O(1) laiko sudėtingumą pridėjimo ir iššokimo operacijoms, palyginti su sąrašu, kuriame pateikiama O(n) laiko sudėtingumas.

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>

Išvestis

Initial stack: deque(['g', 'f', 'g']) Elements popped from stack: g f g Stack after elements are popped: deque([]) 

Diegimas naudojant eilės modulį

Eilės modulis taip pat turi LIFO eilę, kuri iš esmės yra krūva. Duomenys įterpiami į eilę naudojant funkciją put() ir get() išima duomenis iš eilės.

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())>

Išvestis

0 Full: True Size: 3 Elements popped from the stack g f g Empty: True 

Eilė

Kaip krūva, eilė yra linijinė duomenų struktūra, kurioje elementai saugomi FIFO (First In First Out) būdu. Esant eilei, pirmiausia pašalinamas mažiausiai neseniai pridėtas elementas. Geras eilės pavyzdys yra bet kokia vartotojų eilė prie išteklių, kur pirmasis aptarnaujamas vartotojas, kuris buvo pirmasis.

Su eile susijusios operacijos yra šios:

Eilė: prideda elementą į eilę. Jei eilė pilna, vadinasi, tai yra perpildymo sąlyga – laiko sudėtingumas: O(1) Dequeue: pašalina elementą iš eilės. Elementai iššokami ta pačia tvarka, kuria jie stumiami. Jei eilė tuščia, vadinasi, tai yra nepakankamo srauto sąlyga – laiko sudėtingumas: O(1) priekis: gauti priekinį elementą iš eilės – laiko sudėtingumas: O(1) gale: gauti paskutinį elementą iš eilės – laiko sudėtingumas : O(1)

Python eilės įgyvendinimas

Eilė Python gali būti įdiegta šiais būdais:

• sąrašą
• kolekcijos.deque
• uodega.uodega

Įgyvendinimas naudojant sąrašą

Vietoj enqueue() ir dequeue(), naudojamos funkcijos append() ir 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>

Išvestis

Initial queue ['g', 'f', 'g'] Elements dequeued from queue g f g Queue after removing elements [] 

Įgyvendinimas naudojant kolekcijas.deque

Deque yra teikiama pirmenybė sąrašui tais atvejais, kai reikia greitesnių pridėjimo ir iššokimo operacijų abiejuose konteinerio galuose, nes deque suteikia O(1) laiko sudėtingumą pridėjimo ir iššokimo operacijoms, palyginti su sąrašu, kuriame pateikiama O(n) laiko sudėtingumas.

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>

Išvestis

Initial queue deque(['g', 'f', 'g']) Elements dequeued from the queue g f g Queue after removing elements deque([]) 

Diegimas naudojant eilę.Eilė

queue.Queue(maxsize) inicijuoja kintamąjį iki didžiausio maksimalaus dydžio. Didžiausias nulis „0“ reiškia begalinę eilę. Ši eilė atitinka FIFO taisyklę.

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())>

Išvestis

0 Full: True Elements dequeued from the queue g f g Empty: True Empty: False Full: False 

Prioritetinė eilė

Prioritetinės eilės yra abstrakčios duomenų struktūros, kuriose kiekvienas eilės duomenims/reikšmei suteikiamas tam tikras prioritetas. Pavyzdžiui, oro linijose bagažas, pavadintas Verslo arba Pirmos klasės, atkeliauja anksčiau nei kiti. Prioritetinė eilė yra eilės plėtinys su šiomis savybėmis.

• Aukšto prioriteto elementas ištraukiamas prieš elementą, kurio prioritetas žemas.
• Jei du elementai turi tą patį prioritetą, jie pateikiami pagal eilę.

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]>>> :> > myQueue> => PriorityQueue()> > myQueue.insert(> 12> )> > myQueue.insert(> 1> )> > myQueue.insert(> 14> )> > myQueue.insert(> 7> )> > print> (myQueue)> > while> not> myQueue.isEmpty():> > print> (myQueue.delete())>

Išvestis

12 1 14 7 14 12 7 1 

Krūvos eilė (arba krūva)

heapq modulis Python pateikia krūvos duomenų struktūrą, kuri daugiausia naudojama prioritetinei eilei atstovauti. Šios Python duomenų struktūros savybė yra ta, kad kiekvieną kartą iškyla mažiausia krūvos elementas (min-heap). Kai elementai stumiami arba iššokami, krūvos struktūra išlaikoma. Elementas heap[0] kiekvieną kartą taip pat grąžina mažiausią elementą.

Tai palaiko mažiausio elemento ištraukimą ir įterpimą per O (log n) laikus.

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))>

Išvestis

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 

Dvejetainis medis

Medis yra hierarchinė duomenų struktūra, kuri atrodo taip, kaip paveikslėlyje žemiau –

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

Viršutinis medžio mazgas vadinamas šakniu, o apatiniai mazgai arba mazgai be vaikų vadinami lapų mazgais. Mazgai, esantys tiesiai po mazgu, vadinami jo vaikais, o mazgai, esantys tiesiai virš kažko, vadinami pirminiais.

Dvejetainis medis yra medis, kurio elementai gali turėti beveik du vaikus. Kadangi kiekvienas dvejetainio medžio elementas gali turėti tik 2 vaikus, paprastai juos pavadiname kairiuoju ir dešiniuoju vaikais. Dvejetainio medžio mazgą sudaro šios dalys.

• Duomenys
• Rodyklė į kairį vaiką
• Nukreipkite į tinkamą vaiką

Pavyzdys: Mazgo klasės apibrėžimas

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>

Dabar „Python“ sukurkime medį su 4 mazgais. Tarkime, kad medžio struktūra atrodo taip:

 tree ---- 1  <-- root /  2 3 / 4 

Pavyzdys: duomenų įtraukimas į medį

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'''>

Medžių perėjimas

Medžius galima pervažiuoti įvairiais būdais. Toliau pateikiami dažniausiai naudojami medžių kirtimo būdai. Panagrinėkime žemiau esantį medį -

 tree ---- 1  <-- root /  2 3 /  4 5 

Pirmosios kelionės gyliu:

• Eilė (kairė, šaknis, dešinė): 4 2 5 1 3
• Išankstinis užsakymas (šaknis, kairė, dešinė): 1 2 4 5 3
• Postorder (kairėje, dešinėje, šaknyje): 4 5 2 3 1

Algoritmo eilės tvarka (medis)

• Pereikite kairįjį pomedį, t. y. iškvieskite Inorder(left-submedis)
• Aplankykite šaknį.
• Pereikite dešinįjį pomedį, t. y. iškvieskite Inorder (dešinė-submedis)

Algoritmo išankstinis užsakymas (medis)

• Aplankykite šaknį.
• Pereikite kairįjį pomedį, t. y. iškvieskite išankstinį užsakymą (left-submedis)
• Pereikite dešinįjį pomedį, t. y. iškvieskite išankstinį užsakymą (dešinė-submedis)

Algoritmas Pašto orderis (medis)

• Pereikite kairįjį pomedį, t. y. iškvieskite Postorder(left-submedis)
• Pereikite dešinįjį pomedį, t. y. iškvieskite Postorder (dešinysis pomedis)
• Aplankykite šaknį.

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)>

Išvestis

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 

Laiko sudėtingumas – O(n)

Pirmojo arba lygio užsakymo praėjimas

Lygio užsakymo perėjimas medžio yra pločio pirmas medžio apvažiavimas. Aukščiau pateikto medžio lygio eilės tvarka yra 1 2 3 4 5.

Kiekviename mazge pirmiausia aplankomas mazgas, o tada antriniai jo mazgai įtraukiami į FIFO eilę. Žemiau yra to paties algoritmas -

• Sukurkite tuščią eilę q
• temp_node = root /*pradėti nuo šaknies*/
• Ciklas, kol temp_node nėra NULL
  • spausdinti temp_node->data.
  • Į eilę įrašykite temp_node vaikus (pirma kairėje, tada dešinėje) į q
  • Nuimkite mazgą iš 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)>>> )> printLevelOrder(root)>

Išvestis

Level Order Traversal of binary tree is - 1 2 3 4 5 

Laiko sudėtingumas: O(n)

Grafikas

A grafiką yra netiesinė duomenų struktūra, susidedanti iš mazgų ir briaunų. Mazgai kartais taip pat vadinami viršūnėmis, o kraštai yra linijos arba lankai, jungiantys bet kuriuos du grafiko mazgus. Formaliau grafiką galima apibrėžti kaip grafiką, susidedantį iš baigtinės viršūnių (arba mazgų) rinkinio ir briaunų, jungiančių mazgų porą, rinkinio.

Aukščiau pateiktame grafike viršūnių rinkinys V = {0,1,2,3,4} ir briaunų rinkinys E = {01, 12, 23, 34, 04, 14, 13}.

Toliau pateikiami du dažniausiai naudojami grafiko atvaizdai.

• Gretimo matrica
• Gretimų sąrašas

Gretimo matrica

Gretumų matrica yra V x V dydžio 2D masyvas, kur V yra grafiko viršūnių skaičius. Tegul 2D masyvas yra adj[][], plyšys adj[i][j] = 1 rodo, kad yra briauna nuo viršūnės i iki viršūnės j. Nenukreipto grafo gretimų matrica visada yra simetriška. Gretumų matrica taip pat naudojama svertiniams grafikams pavaizduoti. Jei adj[i][j] = w, tai yra briauna nuo viršūnės i iki viršūnės j, kurios svoris 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())>

Išvestis

Grafo viršūnės

[„a“, „b“, „c“, „d“, „e“, „f“]

Grafo kraštai

[('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)]

Grafo gretimų matrica

[[-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]]

Gretimų sąrašas

Naudojamas sąrašų masyvas. Masyvo dydis lygus viršūnių skaičiui. Tegul masyvas yra masyvas []. Įvesties masyvas [i] reiškia viršūnių, esančių greta i-osios viršūnės, sąrašą. Šis vaizdas taip pat gali būti naudojamas svertiniam grafikui pavaizduoti. Kraštų svoriai gali būti pavaizduoti kaip porų sąrašai. Toliau pateikiamas aukščiau esančios diagramos gretimų vietų sąrašo vaizdas.

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()>

Išvestis

Adjacency list of vertex 0 head ->4 -> 1 viršūnių gretimų sąrašas 1 galva -> 4 -> 3 -> 2 -> 0 gretimų viršūnių sąrašas 2 galva -> 3 -> 1 gretimų viršūnių sąrašas 3 galva -> 4 -> 2 -> 1 gretimų viršūnių sąrašas viršūnių sąrašas 4 galva -> 3 -> 1 -> 0>>   
Grafiko perėjimas 
  
  Breadth-First Search arba BFS   
  
  Breadth-First Traversal nes grafikas yra panašus į medžio pločio apėjimą. Vienintelis dalykas yra tas, kad skirtingai nei medžiuose, diagramose gali būti ciklai, todėl galime vėl patekti į tą patį mazgą. Kad mazgas nebūtų apdorotas daugiau nei vieną kartą, naudojame loginį aplankytą masyvą. Paprastumo dėlei daroma prielaida, kad visos viršūnės pasiekiamos iš pradinės viršūnės. 
  
Pavyzdžiui, sekančiame grafike pradedame ėjimą nuo 2 viršūnės. Kai pasiekiame viršūnę 0, ieškome visų gretimų jos viršūnių. 2 taip pat yra gretima viršūnė, lygi 0. Jei nepažymėsime aplankytų viršūnių, tada 2 bus apdorojamas dar kartą ir tai taps nesibaigiančiu procesu. Šios grafikos skersmuo pirmas plotis yra 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>   
  
  
  
  
 
     
 
     
 
   
 
  Išvestis   
 
  
Following is Breadth First Traversal (starting from vertex 2) 2 0 3 1 
  
Laiko sudėtingumas: O(V+E), kur V – grafo viršūnių skaičius, o E – grafo briaunų skaičius. 
  
  Pirmoji gilumo paieška arba DFS   
  
  Pirmasis gylis nes grafikas yra panašus į medžio gylio pirmąjį apėjimą. Vienintelis dalykas čia yra tas, kad skirtingai nei medžiai, diagramose gali būti ciklai, mazgas gali būti aplankytas du kartus. Kad mazgas nebūtų apdorotas daugiau nei vieną kartą, naudokite loginį aplankytą masyvą. 
  
  Algoritmas:   
  
  
Sukurkite rekursinę funkciją, kuri paima mazgo ir aplankyto masyvo indeksą. 
  
Pažymėkite dabartinį mazgą kaip aplankytą ir atspausdinkite mazgą. 
  
Pereikite visus gretimus ir nepažymėtus mazgus ir iškvieskite rekursinę funkciją su gretimo mazgo indeksu. 
  
  
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>  )>   
  
  
  
  
 
     
 
   
 
     
 
   
 
  Išvestis   
 
  
Following is DFS from (starting from vertex 2) 2 0 1 3 
  
Laiko sudėtingumas: O(V + E), kur V – viršūnių skaičius, o E – kraštinių skaičius grafe.