Podatkovne strukture so način organiziranja podatkov, tako da je do njih mogoče učinkoviteje dostopati glede na situacijo. Podatkovne strukture so osnova vsakega programskega jezika, okoli katerega je zgrajen program. Python pomaga pri učenju osnov teh podatkovnih struktur na preprostejši način v primerjavi z drugimi programskimi jeziki.
V tem članku bomo razpravljali o podatkovnih strukturah v programskem jeziku Python in o tem, kako so povezane z nekaterimi posebnimi vgrajenimi podatkovnimi strukturami, kot so nizi seznamov, slovarji itd., kot tudi z nekaterimi naprednimi podatkovnimi strukturami, kot so drevesa, grafi itd.
Seznami
Seznami Python so tako kot polja, deklarirana v drugih jezikih, ki so urejena zbirka podatkov. Je zelo prilagodljiv, saj ni treba, da so elementi na seznamu iste vrste.
Implementacija Python List je podobna Vectors v C++ ali ArrayList v JAVA. Draga operacija je vstavljanje ali brisanje elementa z začetka seznama, saj je treba vse elemente premakniti. Vstavljanje in brisanje na koncu seznama lahko postane drago tudi v primeru, ko je vnaprej dodeljeni pomnilnik poln.
V pythonu lahko ustvarimo seznam, kot je prikazano spodaj.
Primer: Ustvarjanje seznama Python
Python3
List> => [>1>,>2>,>3>,>'GFG'>,>2.3>]> print>(>List>)> |
>
>Izhod
[1, 2, 3, 'GFG', 2.3]>
Do elementov seznama lahko dostopate z dodeljenim indeksom. V pythonu je začetni indeks seznama zaporedje 0 in končni indeks (če je N elementov) N-1.
Primer: operacije seznama 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>])> |
>
poiščite blokirane številke v sistemu Android
>Izhod
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>
Slovar
Slovar Python je kot zgoščene tabele v katerem koli drugem jeziku s časovno kompleksnostjo O(1). Je neurejena zbirka podatkovnih vrednosti, ki se uporablja za shranjevanje podatkovnih vrednosti, kot je zemljevid, ki za razliko od drugih podatkovnih vrst, ki vsebujejo samo eno vrednost kot element, slovar vsebuje par ključ:vrednost. Ključna vrednost je na voljo v slovarju, da je bolj optimiziran.
Indeksiranje slovarja Python poteka s pomočjo tipk. Ti so katerega koli tipa, ki ga je mogoče razpršiti, tj. objekt, ki se nikoli ne more spremeniti, kot so nizi, števila, tuple itd. Slovar lahko ustvarimo z uporabo zavitih oklepajev ({}) ali slovarsko razumevanje .
Primer: operacije slovarja 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)> |
>
>Izhod
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 je zbirka predmetov Python, ki je zelo podobna seznamu, vendar so Tuples po naravi nespremenljivi, tj. elementov v tupleu ni mogoče dodati ali odstraniti, ko so ustvarjeni. Tako kot seznam lahko tudi Tuple vsebuje elemente različnih vrst.
V Pythonu so tuple ustvarjene z umestitvijo zaporedja vrednosti, ločenih z 'vejico' z ali brez uporabe oklepajev za združevanje zaporedja podatkov.
Opomba: Tuple je mogoče ustvariti tudi z enim samim elementom, vendar je to nekoliko težavno. En element v oklepaju ne zadošča, na koncu mora biti vejica, da je torka.
Primer: Python Tuple Operations
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>])> |
>
>Izhod
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> Set
Python Set je neurejena zbirka podatkov, ki je spremenljiva in ne dovoljuje nobenega podvojenega elementa. Kompleti se v bistvu uporabljajo za vključitev testiranja članstva in odpravljanje podvojenih vnosov. Pri tem uporabljena podatkovna struktura je zgoščevanje, priljubljena tehnika za izvajanje vstavljanja, brisanja in prečkanja v povprečju O(1).
Če je na istem mestu indeksa prisotnih več vrednosti, je vrednost dodana temu položaju indeksa, da se oblikuje povezan seznam. V CPython Sets so implementirani z uporabo slovarja z navideznimi spremenljivkami, kjer so ključna bitja člani niza z večjo optimizacijo časovne kompleksnosti.
Nastavite implementacijo:
Nabori s številnimi operacijami na eni HashTable:
Primer: 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>)> |
>
>Izhod
Set with the use of Mixed Values {1, 2, 'Geeks', 4, 6, 'For'} Elements of set: 1 2 Geeks 4 6 For True> Zamrznjeni kompleti
Zamrznjeni nizi v Pythonu so nespremenljivi objekti, ki podpirajo samo metode in operaterje, ki ustvarijo rezultat, ne da bi vplivali na zamrznjeni niz ali nize, za katere so uporabljeni. Medtem ko je elemente niza mogoče kadar koli spremeniti, elementi zamrznjenega niza po ustvarjanju ostanejo enaki.
Če ni posredovan noben parameter, vrne prazen zamrznjen niz.
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')> |
>
>Izhod
Normal Set {'a', 'c', 'b'} Frozen Set frozenset({'g', 'e', 'f'})> Vrvica
Python nizi so nizi bajtov, ki predstavljajo znake Unicode. Preprosteje povedano, niz je nespremenljiv niz znakov. Python nima znakovnega podatkovnega tipa, en znak je preprosto niz z dolžino 1.
Opomba: Ker so nizi nespremenljivi, bo sprememba niza povzročila ustvarjanje nove kopije.
Primer: operacije nizov 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>])> |
>
>Izhod
Creating String: Welcome to GeeksForGeeks First character of String is: W Last character of String is: s>
Bytearray
Python Bytearray daje spremenljivo zaporedje celih števil v območju 0 <= x < 256.
Primer: operacije 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)> |
>
>Izhod
Creating Bytearray: bytearray(b'x0cx08x19x02') Accessing Elements: 8 After Modifying: bytearray(b'x0cx03x19x02') After Adding Elements: bytearray(b'x0cx03x19x02x1e')>
Do sedaj smo preučili vse podatkovne strukture, ki so vgrajene v jedro Pythona. Zdaj pa se poglobimo v Python in si oglejte modul zbirk, ki ponuja nekaj vsebnikov, ki so uporabni v številnih primerih in nudijo več funkcij kot zgoraj definirane funkcije.
Modul zbirk
Zbiralni modul Python je bil predstavljen za izboljšanje funkcionalnosti vgrajenih podatkovnih tipov. Zagotavlja različne vsebnike, poglejmo vsakega od njih podrobneje.
Števci
Števec je podrazred slovarja. Uporablja se za vodenje števila elementov v iterabli v obliki neurejenega slovarja, kjer ključ predstavlja element v iterabli, vrednost pa število tega elementa v iterabli. To je enakovredno vrečki ali množici drugih jezikov.
Primer: Python Counter Operations
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)> |
>
>Izhod
Counter({'B': 5, 'A': 3, 'C': 2}) Counter({'B': 5, 'A': 3, 'C': 2}) Counter({'B': 5, 'A': 4, 'C': 2, 1: 1})> OrderedDict
An OrderedDict je tudi podrazred slovarja, vendar si za razliko od slovarja zapomni vrstni red, v katerem so bili vstavljeni ključi.
Primer: operacije 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)> |
>
>Izhod
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 se uporablja za zagotavljanje nekaterih privzetih vrednosti za ključ, ki ne obstaja in nikoli ne sproži KeyError. Njegove objekte je mogoče inicializirati z uporabo metode DefaultDict() s podajanjem podatkovnega tipa kot argumenta.
Opomba: default_factory je funkcija, ki zagotavlja privzeto vrednost za ustvarjeni slovar. Če tega parametra ni, se sproži KeyError.
Primer: operacije 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)> |
>
>Izhod
defaultdict(, {1: 2, 2: 3, 3: 1, 4: 2})> ChainMap
ChainMap enkapsulira veliko slovarjev v eno enoto in vrne seznam slovarjev. Ko je treba najti ključ, se preiščejo vsi slovarji enega za drugim, dokler se ključ ne najde.
Primer: operacije 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'>])> |
>
>
Izhod
ChainMap({'a': 1, 'b': 2}, {'c': 3, 'd': 4}, {'e': 5, 'f': 6}) 1> KeyError: 'g'>
NamedTuple
A NamedTuple vrne predmet tuple z imeni za vsako pozicijo, ki jih navadne tuple nimajo. Na primer, pomislite na torko, ki poimenuje študenta, kjer prvi element predstavlja fname, drugi predstavlja lname in tretji element predstavlja DOB. Recimo, da lahko za klic fname, namesto da bi si zapomnili položaj indeksa, dejansko pokličete element z uporabo argumenta fname, potem bo zelo enostavno dostopati do elementa tuples. To funkcionalnost zagotavlja NamedTuple.
Primer: Python NamedTuple Operations
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)> |
>
>Izhod
The Student age using index is : 19 The Student name using keyname is : Nandini>
O čem
Deque (dvojno končana čakalna vrsta) je optimiziran seznam za hitrejše operacije dodajanja in izpiranja z obeh strani vsebnika. Zagotavlja O(1) časovno kompleksnost za operacije dodajanja in izpiranja v primerjavi s seznamom z O(n) časovno kompleksnostjo.
Python Deque je implementiran z uporabo dvojno povezanih seznamov, zato je zmogljivost za naključni dostop do elementov O(n).
Primer: Python Deque Operations
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)> |
zanke java
>
>Izhod
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 je vsebnik, podoben slovarju, ki deluje kot ovoj okoli slovarskih predmetov. Ta vsebnik se uporablja, ko želi nekdo ustvariti svoj lasten slovar z neko spremenjeno ali novo funkcionalnostjo.
Primer: 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>)> |
>
>
Izhod
Original Dictionary {'a': 1, 'b': 2, 'c': 3}> RuntimeError: Deletion not allowed>
Uporabniški seznam
UserList je seznamu podoben vsebnik, ki deluje kot ovoj okoli predmetov seznama. To je uporabno, ko želi nekdo ustvariti svoj seznam z nekaj spremenjenimi ali dodatnimi funkcijami.
Primeri: 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()> |
>
>
Izhod
Original List [1, 2, 3, 4] After Insertion [1, 2, 3, 4, 5]>
RuntimeError: Deletion not allowed>
UserString
UserString je nizu podoben vsebnik in tako kot UserDict in UserList deluje kot ovoj okrog objektov niza. Uporablja se, ko želi nekdo ustvariti lastne nize z neko spremenjeno ali dodatno funkcionalnostjo.
Primer: 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)> |
>
>Izhod
Original String: Geeks String After Appending: Geekss String after Removing: Gkss>
Zdaj, ko smo preučili vse podatkovne strukture, si oglejmo nekaj naprednih podatkovnih struktur, kot so sklad, čakalna vrsta, graf, povezani seznam itd., ki jih je mogoče uporabiti v jeziku Python.
Povezan seznam
Povezan seznam je linearna podatkovna struktura, v kateri elementi niso shranjeni na sosednjih pomnilniških lokacijah. Elementi na povezanem seznamu so povezani s kazalci, kot je prikazano na spodnji sliki:
Povezani seznam je predstavljen s kazalcem na prvo vozlišče povezanega seznama. Prvo vozlišče se imenuje glava. Če je povezan seznam prazen, je vrednost glave NULL. Vsako vozlišče na seznamu je sestavljeno iz vsaj dveh delov:
- podatki
- Kazalec (ali sklic) na naslednje vozlišče
Primer: Definiranje povezanega seznama v Pythonu
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> |
>
>
Ustvarimo preprost povezan seznam s 3 vozlišči.
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 | nič | | 3 | nič |> >+----+------+ +----+------+ +----+------+> >'''> >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 | nič |> >+----+------+ +----+------+ +----+------+> >'''> |
>
>
Prehod povezanega seznama
V prejšnjem programu smo ustvarili preprost povezan seznam s tremi vozlišči. Preletimo ustvarjeni seznam in natisnemo podatke vsakega vozlišča. Za prečkanje napišimo splošno uporabno funkcijo printList(), ki natisne poljuben seznam.
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()> |
>
>Izhod
1 2 3>
Stack
A kup je linearna podatkovna struktura, ki shranjuje elemente na način Zadnji vstop/prvi ven (LIFO) ali Prvi vstop/Zadnji ven (FILO). V skladu je nov element dodan na enem koncu in element je odstranjen samo s tega konca. Operaciji vstavljanja in brisanja se pogosto imenujeta push in pop.
Funkcije, povezane s skladom, so:
- empty() – Vrne, ali je sklad prazen – Časovna kompleksnost: O(1) size() – Vrne velikost sklada – Časovna kompleksnost: O(1) top() – Vrne sklic na najvišji element sklada – Časovna kompleksnost: O(1) push(a) – Vstavi element 'a' na vrh sklada – Časovna kompleksnost: O(1) pop() – Izbriše najvišji element sklada – Časovna kompleksnost: O( 1)
Implementacija sklada Python
Stack v Pythonu je mogoče implementirati na naslednje načine:
- seznam
- Zbirke.deque
- čakalna vrsta.LifoQueue
Izvedba z uporabo seznama
Pythonov vgrajen seznam struktur podatkov se lahko uporablja kot sklad. Namesto push() se append() uporablja za dodajanje elementov na vrh sklada, medtem ko pop() odstrani element v vrstnem redu 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> |
>
>Izhod
Initial stack ['g', 'f', 'g'] Elements popped from stack: g f g Stack after elements are popped: []>
Izvedba z uporabo collections.deque:
Sklad Python je mogoče implementirati z uporabo razreda deque iz modula zbirk. Deque ima prednost pred seznamom v primerih, ko potrebujemo hitrejše operacije dodajanja in izpiranja z obeh koncev vsebnika, saj deque zagotavlja časovno kompleksnost O(1) za operacije dodajanja in izpiranja v primerjavi s seznamom, ki zagotavlja O(n) časovna kompleksnost.
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> |
>
>Izhod
Initial stack: deque(['g', 'f', 'g']) Elements popped from stack: g f g Stack after elements are popped: deque([])>
Izvedba z modulom čakalne vrste
Modul čakalne vrste ima tudi čakalno vrsto LIFO, ki je v bistvu sklad. Podatki se vstavijo v čakalno vrsto s funkcijo put(), get() pa vzame podatke iz čakalne vrste.
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())> |
>
>Izhod
0 Full: True Size: 3 Elements popped from the stack g f g Empty: True>
Čakalna vrsta
Kot kup, čakalna vrsta je linearna podatkovna struktura, ki shranjuje elemente na način First In First Out (FIFO). Pri čakalni vrsti se najprej odstrani nazadnje dodan element. Dober primer čakalne vrste je katera koli čakalna vrsta porabnikov za vir, kjer je porabnik, ki je bil prvi, postrežen prvi.
Operacije, povezane s čakalno vrsto, so:
- V čakalno vrsto: doda element v čakalno vrsto. Če je čakalna vrsta polna, potem gre za stanje prelivanja – Časovna zapletenost: O(1) Odstranitev iz čakalne vrste: Odstrani element iz čakalne vrste. Predmeti se prikažejo v istem vrstnem redu, kot so potisnjeni. Če je čakalna vrsta prazna, potem gre za pogoj Underflow – Časovna zapletenost: O(1) Spredaj: Pridobite prvi element iz čakalne vrste – Časovna zapletenost: O(1) Zadaj: Pridobite zadnji element iz čakalne vrste – Časovna zapletenost : O(1)
Implementacija čakalne vrste Python
Čakalno vrsto v Pythonu je mogoče implementirati na naslednje načine:
- seznam
- zbirke.deque
- rep.rep
Izvedba z uporabo seznama
Namesto enqueue() in dequeue() se uporablja funkcija append() in 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> |
>
>Izhod
Initial queue ['g', 'f', 'g'] Elements dequeued from queue g f g Queue after removing elements []>
Izvedba z uporabo collections.deque
Deque ima prednost pred seznamom v primerih, ko potrebujemo hitrejše operacije dodajanja in izpiranja z obeh koncev vsebnika, saj deque zagotavlja časovno kompleksnost O(1) za operacije dodajanja in izpiranja v primerjavi s seznamom, ki zagotavlja O(n) časovna kompleksnost.
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> |
>
>Izhod
Initial queue deque(['g', 'f', 'g']) Elements dequeued from the queue g f g Queue after removing elements deque([])>
Implementacija s pomočjo čakalne vrste.Čakalna vrsta
java povezava mysql
queue.Queue(maxsize) inicializira spremenljivko na največjo velikost maxsize. Največja velikost nič '0' pomeni neskončno čakalno vrsto. Ta čakalna vrsta sledi pravilu 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())> |
>
>Izhod
0 Full: True Elements dequeued from the queue g f g Empty: True Empty: False Full: False>
Prednostna čakalna vrsta
Prednostne čakalne vrste so abstraktne podatkovne strukture, kjer ima vsak podatek/vrednost v čakalni vrsti določeno prioriteto. Na primer, pri letalskih družbah prtljaga z naslovom Business ali First-class prispe prej kot ostala. Prednostna čakalna vrsta je razširitev čakalne vrste z naslednjimi lastnostmi.
- Element z visoko prioriteto je izključen iz čakalne vrste pred elementom z nizko prioriteto.
- Če imata dva elementa enako prioriteto, se strežeta glede na njihov vrstni red v čakalni vrsti.
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())> |
>
>Izhod
12 1 14 7 14 12 7 1>
Čakalna vrsta kopice (ali heapq)
modul heapq v Pythonu zagotavlja podatkovno strukturo kopice, ki se večinoma uporablja za predstavitev prednostne čakalne vrste. Lastnost te podatkovne strukture v Pythonu je, da se vsakič, ko se izstreli najmanjši element kopice (min-heap). Kadarkoli se elementi potisnejo ali izskočijo, se struktura kopice ohrani. Element heap[0] prav tako vsakič vrne najmanjši element.
Podpira ekstrakcijo in vstavljanje najmanjšega elementa v časih 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))> |
>
>Izhod
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>
Binarno drevo
Drevo je hierarhična podatkovna struktura, ki izgleda kot spodnja slika –
tree ---- j <-- root / f k / a h z <-- leaves>
Najvišje vozlišče drevesa se imenuje koren, medtem ko se najnižja vozlišča ali vozlišča brez otrok imenujejo listna vozlišča. Vozlišča, ki so neposredno pod vozliščem, se imenujejo njegovi otroci, vozlišča, ki so neposredno nad nečim, pa se imenujejo njegov nadrejeni.
Binarno drevo je drevo, katerega elementi imajo lahko skoraj dva otroka. Ker ima lahko vsak element v binarnem drevesu samo 2 otroka, ju običajno imenujemo levi in desni otrok. Vozlišče binarnega drevesa vsebuje naslednje dele.
- podatki
- Kazalec na levega otroka
- Kazalec na pravega otroka
Primer: Definiranje razreda vozlišča
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> |
>
>
Zdaj pa ustvarimo drevo s 4 vozlišči v Pythonu. Predpostavimo, da je drevesna struktura videti spodaj –
tree ---- 1 <-- root / 2 3 / 4>
Primer: dodajanje podatkov v drevo
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'''> |
>
>
Prehod drevesa
Drevesa je mogoče prečkati na različne načine. Sledijo običajno uporabljeni načini za prečenje dreves. Oglejmo si spodnje drevo –
tree ---- 1 <-- root / 2 3 / 4 5>
Prvi prehodi globine:
- Vrstni red (levo, koren, desno): 4 2 5 1 3
- Prednaročilo (Root, Left, Right): 1 2 4 5 3
- Po naročilu (levo, desno, koren): 4 5 2 3 1
Algoritem po vrstnem redu (drevo)
- Prečkaj levo poddrevo, tj. pokliči Inorder(left-subtree)
- Obiščite koren.
- Prečkaj desno poddrevo, tj. pokliči Inorder(right-subtree)
Prednaročilo algoritma (drevo)
- Obiščite koren.
- Prečkaj levo poddrevo, tj. pokliči Preorder(left-subtree)
- Prečkaj desno poddrevo, tj. pokliči Preorder(right-subtree)
Algoritem Poštna nakaznica (drevo)
- Prečkajte levo poddrevo, tj. pokličite Postorder(left-subtree)
- Prečkaj desno poddrevo, tj. pokliči Postorder(right-subtree)
- Obiščite koren.
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)> |
>
>Izhod
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>
Časovna kompleksnost – O(n)
Prehod vrstnega reda prve stopnje ali ravni
Prehod ravni vrstnega reda drevesa je prehod drevesa v širino. Vrstni red prečkanja zgornjega drevesa je 1 2 3 4 5.
Za vsako vozlišče se najprej obišče vozlišče, nato pa se njegova podrejena vozlišča postavijo v čakalno vrsto FIFO. Spodaj je algoritem za isto –
- Ustvarite prazno čakalno vrsto q
- temp_node = koren /*začetek od korena*/
- Zanka, medtem ko temp_node ni NULL
- natisni temp_node->data.
- Postavite otroke temp_node (najprej leve in nato desne otroke) v q
- Odstranitev vozlišča iz vrste 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)> |
>
>Izhod
Level Order Traversal of binary tree is - 1 2 3 4 5>
Časovna zahtevnost: O(n)
Graf
A graf je nelinearna podatkovna struktura, sestavljena iz vozlišč in robov. Vozlišča se včasih imenujejo tudi vozlišča, robovi pa so črte ali loki, ki povezujejo kateri koli dve vozlišči v grafu. Bolj formalno lahko graf definiramo kot graf, sestavljen iz končne množice vozlišč (ali vozlišč) in niza robov, ki povezujejo par vozlišč.
V zgornjem grafu je množica vozlišč V = {0,1,2,3,4} in množica robov E = {01, 12, 23, 34, 04, 14, 13}.
Naslednji dve sta najpogosteje uporabljeni predstavitvi grafa.
- Matrika sosednosti
- Seznam sosednosti
Matrika sosednosti
Matrika sosednosti je 2D niz velikosti V x V, kjer je V število vozlišč v grafu. Naj bo 2D niz adj[][], reža adj[i][j] = 1 označuje, da obstaja rob od točke i do točke j. Matrika sosednosti za neusmerjen graf je vedno simetrična. Matrika sosednosti se uporablja tudi za predstavitev tehtanih grafov. Če je adj[i][j] = w, potem obstaja rob od točke i do točke j s težo 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())> |
>
>
Izhod
Oglišča grafa
['a', 'b', 'c', 'd', 'e', 'f']
Robovi grafa
[('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)]
Matrika sosednosti grafa
[[-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]]
Seznam sosednosti
Uporablja se niz seznamov. Velikost matrike je enaka številu oglišč. Naj bo matrika matrika[]. Vnosna matrika[i] predstavlja seznam tock, ki mejijo na i-to tocko. To predstavitev lahko uporabite tudi za predstavitev uteženega grafa. Uteži robov so lahko predstavljene kot seznami parov. Sledi predstavitev seznama sosednosti zgornjega grafa.
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()> |
>
>Izhod
Adjacency list of vertex 0 head ->4 -> 1 Seznam sosednosti glave tocke 1 -> 4 -> 3 -> 2 -> 0 Seznam sosednosti glave tocke 2 -> 3 -> 1 Seznam sosednosti glave tocke 3 -> 4 -> 2 -> 1 Sosednost seznam vrhov 4 glave -> 3 -> 1 -> 0>>Prehod grafa
Breadth-First Search ali BFS
Prehod v širino za graf je podoben prehodu drevesa v širino. Edina težava pri tem je, da za razliko od dreves lahko grafi vsebujejo cikle, tako da lahko spet pridemo do istega vozlišča. Da bi se izognili večkratni obdelavi vozlišča, uporabimo logično obiskano matriko. Zaradi enostavnosti se predpostavlja, da so vsa oglišča dosegljiva iz začetnega oglišča.
Na primer, v naslednjem grafu začnemo prečkanje iz točke 2. Ko pridemo do točke 0, poiščemo vse sosednje točke. 2 je tudi sosednja vozlišča 0. Če ne označimo obiskanih vozlišč, bo 2 ponovno obdelan in bo postal proces brez zaključka. Prehod v širino naslednjega grafa je 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> |
>Izhod
Following is Breadth First Traversal (starting from vertex 2) 2 0 3 1>
Časovna kompleksnost: O(V+E), kjer je V število vozlišč v grafu, E pa število robov v grafu.
Depth First Search ali DFS
Prvo prečenje globine za graf je podoben prvemu prehodu globine drevesa. Edina težava pri tem je, da za razliko od dreves lahko grafi vsebujejo cikle, vozlišče pa je mogoče obiskati dvakrat. Če se želite izogniti večkratni obdelavi vozlišča, uporabite logično obiskano matriko.
Algoritem:
- Ustvarite rekurzivno funkcijo, ki vzame indeks vozlišča in obiskano matriko.
- Označite trenutno vozlišče kot obiskano in natisnite vozlišče.
- Prečkajte vsa sosednja in neoznačena vozlišča in pokličite rekurzivno funkcijo z indeksom sosednjega vozlišča.
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>)> |
>
>Izhod
Following is DFS from (starting from vertex 2) 2 0 1 3>
Časovna kompleksnost: O(V + E), kjer je V število vozlišč in E število robov v grafu.