Dátové štruktúry predstavujú spôsob organizácie údajov tak, aby k nim bolo možné pristupovať efektívnejšie v závislosti od situácie. Dátové štruktúry sú základom každého programovacieho jazyka, okolo ktorého je program postavený. Python pomáha naučiť sa základy týchto dátových štruktúr jednoduchším spôsobom v porovnaní s inými programovacími jazykmi.
V tomto článku budeme diskutovať o dátových štruktúrach v programovacom jazyku Python a o tom, ako súvisia s niektorými špecifickými vstavanými dátovými štruktúrami, ako sú n-tice zoznamov, slovníky atď., ako aj s niektorými pokročilými dátovými štruktúrami, ako sú stromy, grafy atď.
zoznamy
Zoznamy Pythonu sú rovnako ako polia, deklarované v iných jazykoch, čo je usporiadaná kolekcia údajov. Je veľmi flexibilný, pretože položky v zozname nemusia byť rovnakého typu.
Implementácia Python Listu je podobná ako Vectors v C++ alebo ArrayList v JAVA. Nákladnou operáciou je vloženie alebo odstránenie prvku zo začiatku zoznamu, pretože je potrebné presunúť všetky prvky. Vkladanie a vymazávanie na konci zoznamu môže byť tiež nákladné v prípade, že sa vopred pridelená pamäť zaplní.
Môžeme vytvoriť zoznam v pythone, ako je uvedené nižšie.
Príklad: Vytvorenie zoznamu Python
Python3
List> => [>1>,>2>,>3>,>'GFG'>,>2.3>]> print>(>List>)> |
>
>Výkon
[1, 2, 3, 'GFG', 2.3]>
Prvky zoznamu sú prístupné pomocou priradeného indexu. V python počiatočnom indexe zoznamu je sekvencia 0 a koncový index je (ak je tam N prvkov) N-1.
Príklad: Operácie zoznamu 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>])> |
>
aké sú rozmery obrazovky môjho počítača
>Výkon
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>
Slovník
Pythonský slovník je ako hašovacie tabuľky v akomkoľvek inom jazyku s časovou zložitosťou O(1). Ide o neusporiadanú kolekciu dátových hodnôt, ktorá sa používa na ukladanie dátových hodnôt ako mapa, ktorá na rozdiel od iných dátových typov, ktoré obsahujú iba jednu hodnotu ako prvok, Dictionary obsahuje pár kľúč:hodnota. Pár kľúč – hodnota je uvedený v slovníku, aby bol optimalizovaný.
Indexovanie Python Dictionary sa vykonáva pomocou kľúčov. Sú akéhokoľvek hašovateľného typu, t. j. objekt, ktorý sa nikdy nemôže meniť ako reťazce, čísla, n-tice atď. Slovník môžeme vytvoriť pomocou zložených zátvoriek ({}) alebo porozumenie slovníka .
Príklad: Operácie slovníka 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)> |
>
>Výkon
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}> Násobný
Python Tuple je zbierka objektov Pythonu podobne ako zoznam, ale n-tice sú svojou povahou nemenné, t. j. prvky v n-tici nie je možné pridávať ani odstraňovať po vytvorení. Rovnako ako zoznam, aj tuple môže obsahovať prvky rôznych typov.
V Pythone sa n-tice vytvárajú umiestnením sekvencie hodnôt oddelených „čiarkou“ s použitím alebo bez použitia zátvoriek na zoskupenie sekvencie údajov.
Poznámka: N-tice môžu byť vytvorené aj s jediným prvkom, ale je to trochu zložité. Jeden prvok v zátvorkách nestačí, musí tam byť koncová „čiarka“, aby sa z neho stala n-tica.
Príklad: 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>])> |
>
>Výkon
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
Sada Python je neusporiadaná zbierka údajov, ktorá je meniteľná a neumožňuje žiadny duplicitný prvok. Sady sa v podstate používajú na testovanie členstva a odstránenie duplicitných záznamov. Štruktúra údajov, ktorá sa tu používa, je hashovanie, populárna technika na vykonávanie vkladania, vymazania a prechodu v priemere v O(1).
Ak sa na rovnakej pozícii indexu nachádza viacero hodnôt, hodnota sa pripojí k tejto pozícii indexu a vytvorí sa tak prepojený zoznam. Sady CPython sú implementované pomocou slovníka s fiktívnymi premennými, kde kľúčové bytosti nastavujú členovia s väčšou optimalizáciou na časovú zložitosť.
Implementácia sady:
Sady s množstvom operácií na jednej HashTable:
Príklad: Operácie množiny Pythonu
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>)> |
>
>Výkon
Set with the use of Mixed Values {1, 2, 'Geeks', 4, 6, 'For'} Elements of set: 1 2 Geeks 4 6 For True> Mrazené súpravy
Zamrznuté množiny v Pythone sú nemenné objekty, ktoré podporujú iba metódy a operátory, ktoré vytvárajú výsledok bez ovplyvnenia zmrazenej množiny alebo množín, na ktoré sú aplikované. Zatiaľ čo prvky množiny možno kedykoľvek upraviť, prvky zamrznutej množiny zostanú po vytvorení rovnaké.
Ak nie sú zadané žiadne parametre, vráti prázdnu zmrazenú sadu.
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')> |
>
>Výkon
Normal Set {'a', 'c', 'b'} Frozen Set frozenset({'g', 'e', 'f'})> Reťazec
Reťazce Pythonu sú polia bajtov reprezentujúce znaky Unicode. Zjednodušene povedané, reťazec je nemenné pole znakov. Python nemá dátový typ znaku, jeden znak je jednoducho reťazec s dĺžkou 1.
Poznámka: Keďže reťazce sú nemenné, úprava reťazca povedie k vytvoreniu novej kópie.
Príklad: Python Strings Operations
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>])> |
>
>Výkon
Creating String: Welcome to GeeksForGeeks First character of String is: W Last character of String is: s>
Bytearray
Python Bytearray poskytuje meniteľnú sekvenciu celých čísel v rozsahu 0 <= x < 256.
Príklad: Operácie 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)> |
>
>Výkon
Creating Bytearray: bytearray(b'x0cx08x19x02') Accessing Elements: 8 After Modifying: bytearray(b'x0cx03x19x02') After Adding Elements: bytearray(b'x0cx03x19x02x1e')>
Doteraz sme študovali všetky dátové štruktúry, ktoré sú zabudované do jadra Pythonu. Teraz sa ponorte hlbšie do Pythonu a pozrite si modul kolekcií, ktorý poskytuje niektoré kontajnery, ktoré sú v mnohých prípadoch užitočné a poskytujú viac funkcií ako vyššie definované funkcie.
Kolekčný modul
Modul zberu Pythonu bol predstavený na zlepšenie funkčnosti vstavaných dátových typov. Poskytuje rôzne kontajnery, pozrime sa na každý z nich podrobne.
Počítadlá
Počítadlo je podtriedou slovníka. Používa sa na udržiavanie počtu prvkov v iterovateľnom prvku vo forme neusporiadaného slovníka, kde kľúč predstavuje prvok v iterovateľnom prvku a hodnota predstavuje počet tohto prvku v iterovateľnom prvku. To je ekvivalentné k vrecku alebo viacnásobnej súprave iných jazykov.
Príklad: Operácie počítadla Pythonu
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)> |
>
>Výkon
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 tiež podtriedou slovníka, ale na rozdiel od slovníka si pamätá poradie, v ktorom boli vložené kľúče.
Príklad: Operácie 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)> |
>
>Výkon
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 sa používa na poskytnutie niektorých predvolených hodnôt pre kľúč, ktorý neexistuje a nikdy nevyvoláva chybu KeyError. Jeho objekty možno inicializovať pomocou metódy DefaultDict() odovzdaním dátového typu ako argumentu.
Poznámka: default_factory je funkcia, ktorá poskytuje predvolenú hodnotu pre vytvorený slovník. Ak tento parameter chýba, zobrazí sa KeyError.
Príklad: Operácie 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)> |
>
>Výkon
defaultdict(, {1: 2, 2: 3, 3: 1, 4: 2})> ChainMap
ChainMap zapuzdruje veľa slovníkov do jednej jednotky a vracia zoznam slovníkov. Keď je potrebné nájsť kľúč, postupne sa prehľadávajú všetky slovníky, kým sa kľúč nenájde.
Príklad: Python ChainMap Operations
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'>])> |
>
>
Výkon
ChainMap({'a': 1, 'b': 2}, {'c': 3, 'd': 4}, {'e': 5, 'f': 6}) 1> KeyError: 'g'>
NamedTuple
A NamedTuple vráti objekt n-tice s menami pre každú pozíciu, ktoré bežným n-ticám chýbajú. Uvažujme napríklad študent n-ticových mien, kde prvý prvok predstavuje fname, druhý predstavuje lname a tretí prvok predstavuje dátum narodenia. Predpokladajme, že na volanie fname namiesto zapamätania si pozície indexu môžete prvok skutočne zavolať pomocou argumentu fname, potom bude prístup k prvku n-tice skutočne jednoduchý. Túto funkciu poskytuje NamedTuple.
Príklad: 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)> |
>
>Výkon
The Student age using index is : 19 The Student name using keyname is : Nandini>
O čom
Deque (dvojitá ukončená fronta) je optimalizovaný zoznam pre rýchlejšie operácie pridávania a otvárania z oboch strán kontajnera. Poskytuje časovú zložitosť O(1) pre operácie pripájania a otvárania v porovnaní so zoznamom s časovou zložitosťou O(n).
Python Deque je implementovaný pomocou dvojito prepojených zoznamov, takže výkon pre náhodný prístup k prvkom je O(n).
Príklad: Operácie Python Deque
Python3
# importing 'collections' for deque operations> import> collections> # initializing deque> de>=> collections.deque([>1>,>2>,>3>])> # using append() to insert element at right end> # inserts 4 at the end of deque> de.append(>4>)> # printing modified deque> print>(>'The deque after appending at right is : '>)> print>(de)> # using appendleft() to insert element at left end> # inserts 6 at the beginning of deque> de.appendleft(>6>)> # printing modified deque> print>(>'The deque after appending at left is : '>)> print>(de)> # using pop() to delete element from right end> # deletes 4 from the right end of deque> de.pop()> # printing modified deque> print>(>'The deque after deleting from right is : '>)> print>(de)> # using popleft() to delete element from left end> # deletes 6 from the left end of deque> de.popleft()> # printing modified deque> print>(>'The deque after deleting from left is : '>)> print>(de)> |
dátové typy java
>
>Výkon
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 kontajner podobný slovníku, ktorý funguje ako obal okolo objektov slovníka. Tento kontajner sa používa, keď si niekto chce vytvoriť vlastný slovník s nejakou upravenou alebo novou funkcionalitou.
Príklad: 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>)> |
>
>
Výkon
Original Dictionary {'a': 1, 'b': 2, 'c': 3}> RuntimeError: Deletion not allowed>
UserList
UserList je kontajner podobný zoznamu, ktorý funguje ako obal okolo objektov zoznamu. Je to užitočné, keď si niekto chce vytvoriť vlastný zoznam s nejakou upravenou alebo dodatočnou funkcionalitou.
Príklady: 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()> |
>
>
Výkon
Original List [1, 2, 3, 4] After Insertion [1, 2, 3, 4, 5]>
RuntimeError: Deletion not allowed>
UserString
UserString je kontajner podobný reťazcu a rovnako ako UserDict a UserList funguje ako obal okolo objektov reťazca. Používa sa, keď si niekto chce vytvoriť vlastné reťazce s nejakou upravenou alebo dodatočnou funkcionalitou.
Príklad: 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)> |
>
>Výkon
Original String: Geeks String After Appending: Geekss String after Removing: Gkss>
Teraz po preštudovaní všetkých dátových štruktúr sa pozrime na niektoré pokročilé dátové štruktúry, ako je zásobník, front, graf, prepojený zoznam atď., ktoré možno použiť v jazyku Python.
Prepojený zoznam
Prepojený zoznam je lineárna dátová štruktúra, v ktorej prvky nie sú uložené na súvislých pamäťových miestach. Prvky v prepojenom zozname sú prepojené pomocou ukazovateľov, ako je znázornené na obrázku nižšie:
Prepojený zoznam je reprezentovaný ukazovateľom na prvý uzol prepojeného zoznamu. Prvý uzol sa nazýva hlava. Ak je prepojený zoznam prázdny, hodnota hlavičky je NULL. Každý uzol v zozname pozostáva najmenej z dvoch častí:
- Údaje
- Ukazovateľ (alebo odkaz) na nasledujúci uzol
Príklad: Definovanie prepojeného zoznamu v Pythone
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> |
>
>
Vytvorme jednoduchý prepojený zoznam s 3 uzlami.
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 |> >+----+------+ +----+------+ +----+------+> >'''> |
>
>
Prechádzanie prepojeného zoznamu
V predchádzajúcom programe sme vytvorili jednoduchý prepojený zoznam s tromi uzlami. Prejdeme vytvorený zoznam a vytlačíme údaje každého uzla. Na prechod napíšme univerzálnu funkciu printList(), ktorá vypíše ľubovoľný daný zoznam.
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()> |
>
>Výkon
1 2 3>
Stoh
A stoh je lineárna dátová štruktúra, ktorá ukladá položky spôsobom Last-In/First-Out (LIFO) alebo First-In/Last-Out (FILO). V zásobníku sa nový prvok pridá na jeden koniec a prvok sa odstráni iba z tohto konca. Operácie vloženia a vymazania sa často nazývajú push a pop.
Funkcie spojené so zásobníkom sú:
- empty() – Vráti, či je zásobník prázdny – Časová zložitosť: O(1) size() – Vráti veľkosť zásobníka – Časová zložitosť: O(1) top() – Vráti odkaz na najvyšší prvok zásobníka – Časová zložitosť: O(1) push(a) – Vloží prvok „a“ na vrch zásobníka – Časová zložitosť: O(1) pop() – Vymaže najvyšší prvok zásobníka – Časová zložitosť: O( 1)
Implementácia balíka Python
Stack v Pythone je možné implementovať nasledujúcimi spôsobmi:
- zoznam
- Collections.deque
- fronta.LifoQueue
Implementácia pomocou zoznamu
Zoznam vstavaných dátových štruktúr Pythonu možno použiť ako zásobník. Namiesto push() sa append() používa na pridávanie prvkov do hornej časti zásobníka, zatiaľ čo pop() odstraňuje prvok v poradí 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> |
>
>Výkon
Initial stack ['g', 'f', 'g'] Elements popped from stack: g f g Stack after elements are popped: []>
Implementácia pomocou collections.deque:
Zásobník Pythonu je možné implementovať pomocou triedy deque z modulu kolekcií. Deque sa uprednostňuje pred zoznamom v prípadoch, keď potrebujeme rýchlejšie operácie pripojenia a pop z oboch koncov kontajnera, pretože deque poskytuje časovú zložitosť O(1) pre operácie pripojenia a pop v porovnaní so zoznamom, ktorý poskytuje O(n) časová zložitosť.
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> |
>
>Výkon
Initial stack: deque(['g', 'f', 'g']) Elements popped from stack: g f g Stack after elements are popped: deque([])>
Implementácia pomocou modulu frontu
Modul frontu má tiež front LIFO, čo je v podstate zásobník. Údaje sa vkladajú do frontu pomocou funkcie put() a get() vyberá údaje z frontu.
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())> |
>
>Výkon
0 Full: True Size: 3 Elements popped from the stack g f g Empty: True>
Fronta
Ako zásobník, frontu je lineárna dátová štruktúra, ktorá ukladá položky spôsobom First In First Out (FIFO). Pri fronte sa najskôr odstráni najmenej nedávno pridaná položka. Dobrým príkladom frontu je akýkoľvek rad spotrebiteľov pre zdroj, kde je prvý obsluhovaný spotrebiteľ, ktorý prišiel ako prvý.
Operácie spojené s frontom sú:
- Zaradiť: Pridá položku do frontu. Ak je front plný, potom ide o stav pretečenia – Časová zložitosť: O(1) Zoradiť: Odstráni položku z frontu. Položky sa vyskakujú v rovnakom poradí, v akom sa tlačia. Ak je front prázdny, potom sa hovorí, že ide o podmienku podtečenia – Časová zložitosť: O(1) Predná časť: Získanie prednej položky z frontu – Časová zložitosť: O(1) Zadná strana: Získanie poslednej položky z radu – Časová zložitosť : O(1)
Implementácia frontu Pythonu
Fronta v Pythone môže byť implementovaná nasledujúcimi spôsobmi:
- zoznam
- zbierky.deque
- chvost.chvost
Implementácia pomocou zoznamu
Namiesto enqueue() a dequeue() sa používa funkcia append() a 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> |
>
>Výkon
Initial queue ['g', 'f', 'g'] Elements dequeued from queue g f g Queue after removing elements []>
Implementácia pomocou collections.deque
Deque sa uprednostňuje pred zoznamom v prípadoch, keď potrebujeme rýchlejšie operácie pripojenia a pop z oboch koncov kontajnera, pretože deque poskytuje časovú zložitosť O(1) pre operácie pripojenia a pop v porovnaní so zoznamom, ktorý poskytuje O(n) časová zložitosť.
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> |
>
>Výkon
Initial queue deque(['g', 'f', 'g']) Elements dequeued from the queue g f g Queue after removing elements deque([])>
Implementácia pomocou queue.Queue
pripojenie java mysql
queue.Queue(maxsize) inicializuje premennú na maximálnu veľkosť maxsize. Maximálna veľkosť nula „0“ znamená nekonečný rad. Táto fronta sa riadi pravidlom 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())> |
>
>Výkon
0 Full: True Elements dequeued from the queue g f g Empty: True Empty: False Full: False>
Prioritný front
Prioritné fronty sú abstraktné dátové štruktúry, kde každý údaj/hodnota vo fronte má určitú prioritu. Napríklad v leteckých spoločnostiach prichádza batožina s názvom Business alebo First-class skôr ako ostatné. Prioritný front je rozšírenie frontu s nasledujúcimi vlastnosťami.
- Prvok s vysokou prioritou je vyradený pred prvok s nízkou prioritou.
- Ak majú dva prvky rovnakú prioritu, obslúžia sa podľa poradia vo fronte.
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())> |
>
>Výkon
12 1 14 7 14 12 7 1>
Front haldy (alebo heapq)
modul heapq v Pythone poskytuje štruktúru údajov haldy, ktorá sa používa hlavne na reprezentáciu prioritného frontu. Vlastnosťou tejto dátovej štruktúry v Pythone je, že zakaždým, keď sa objaví najmenší prvok haldy (min-heap). Vždy, keď sú prvky zatlačené alebo vyskočené, štruktúra haldy sa zachová. Prvok haldy[0] tiež zakaždým vráti najmenší prvok.
Podporuje extrakciu a vloženie najmenšieho prvku v O(log n) časoch.
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))> |
>
>Výkon
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>
Binárny strom
Strom je hierarchická dátová štruktúra, ktorá vyzerá ako na obrázku nižšie –
tree ---- j <-- root / f k / a h z <-- leaves>
Najvyšší uzol stromu sa nazýva koreň, zatiaľ čo najspodnejšie uzly alebo uzly bez potomkov sa nazývajú listové uzly. Uzly, ktoré sú priamo pod uzlom, sa nazývajú jeho potomkovia a uzly, ktoré sú priamo nad niečím, sa nazývajú jeho rodičia.
Binárny strom je strom, ktorého prvky môžu mať takmer dve deti. Keďže každý prvok v binárnom strome môže mať iba 2 potomkov, zvyčajne ich pomenujeme ľavé a pravé potomstvo. Uzol binárneho stromu obsahuje nasledujúce časti.
- Údaje
- Ukazovateľ na ľavé dieťa
- Ukazovateľ na správne dieťa
Príklad: Definovanie triedy uzla
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> |
>
>
Teraz vytvorte strom so 4 uzlami v Pythone. Predpokladajme, že stromová štruktúra vyzerá nižšie –
tree ---- 1 <-- root / 2 3 / 4>
Príklad: Pridávanie údajov do stromu
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'''> |
>
>
Prechádzanie stromom
Stromy sa dajú prechádzať rôznymi spôsobmi. Nasledujú všeobecne používané spôsoby prechodu cez stromy. Pozrime sa na nižšie uvedený strom -
tree ---- 1 <-- root / 2 3 / 4 5>
Hĺbkové prvé prechody:
- V poradí (vľavo, koreň, vpravo): 4 2 5 1 3
- Predobjednávka (koreň, vľavo, vpravo): 1 2 4 5 3
- Postorder (vľavo, vpravo, koreň) : 4 5 2 3 1
Algoritmus Inorder (strom)
- Prejdite ľavým podstromom, t.j. zavolajte Inorder (ľavý podstrom)
- Navštívte koreň.
- Prejdite pravým podstromom, t.j. zavolajte Inorder (pravý podstrom)
Predobjednávka algoritmu (strom)
- Navštívte koreň.
- Prejdite ľavým podstromom, t. j. zavolajte Predobjednávku (ľavý podstrom)
- Prejdite pravým podstromom, t.j. zavolajte Predobjednávku (pravý podstrom)
Algoritmus Poštová poukážka (strom)
- Prejdite ľavým podstromom, t.j. zavolajte Postorder (ľavý podstrom)
- Prejdite pravým podstromom, t.j. zavolajte Postorder (pravý podstrom)
- Navštívte koreň.
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)> |
>
>Výkon
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>
Časová zložitosť – O(n)
Priebeh poradia po šírke alebo úrovni
Priebeh objednávky úrovne stromu je prechod stromu na šírku. Prechod na úrovni vyššie uvedeného stromu je 1 2 3 4 5.
Pre každý uzol sa najprv navštívi uzol a potom sa jeho dcérske uzly zaradia do frontu FIFO. Nižšie je uvedený algoritmus pre to isté -
- Vytvorte prázdny rad q
- temp_node = root /*začať od root*/
- Slučka, zatiaľ čo temp_node nie je NULL
- vytlačiť temp_node->data.
- Zaraďte deti temp_node (prvé ľavé, potom pravé deti) do q
- Vyraďte uzol z 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)> |
>
>Výkon
Level Order Traversal of binary tree is - 1 2 3 4 5>
Časová zložitosť: O(n)
Graf
A graf je nelineárna dátová štruktúra pozostávajúca z uzlov a hrán. Uzly sa niekedy označujú aj ako vrcholy a hrany sú čiary alebo oblúky, ktoré spájajú ľubovoľné dva uzly v grafe. Formálnejšie možno graf definovať ako graf pozostávajúci z konečnej množiny vrcholov (alebo uzlov) a množiny hrán, ktoré spájajú pár uzlov.
Vo vyššie uvedenom grafe je množina vrcholov V = {0,1,2,3,4} a množina hrán E = {01, 12, 23, 34, 04, 14, 13}.
Nasledujúce dve sú najbežnejšie používané znázornenia grafu.
- Matica susedstva
- Zoznam susedstva
Matica susedstva
Matica susedstva je 2D pole veľkosti V x V, kde V je počet vrcholov v grafe. Nech je 2D pole adj[][], slot adj[i][j] = 1 znamená, že od vrcholu i k vrcholu j existuje hrana. Matica susednosti pre neorientovaný graf je vždy symetrická. Matica susedstva sa tiež používa na znázornenie vážených grafov. Ak adj[i][j] = w, potom od vrcholu i po vrchol j existuje hrana s váhou 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())> |
>
>
Výkon
Vrcholy grafu
['A b c d e f']
Okraje grafu
[('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)]
Matica susedstva grafu
[[-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]]
Zoznam susedstva
Používa sa celý rad zoznamov. Veľkosť poľa sa rovná počtu vrcholov. Nech pole je pole[]. Vstupné pole[i] predstavuje zoznam vrcholov susediacich s i-tým vrcholom. Toto znázornenie možno použiť aj na znázornenie váženého grafu. Váhy hrán môžu byť reprezentované ako zoznamy párov. Nasleduje znázornenie zoznamu susedstva vyššie uvedeného grafu.
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()> |
>
>Výkon
Adjacency list of vertex 0 head ->4 -> 1 Zoznam susedstva hlavy vrcholu 1 -> 4 -> 3 -> 2 -> 0 Zoznam susedstva hlavy vrcholu 2 -> 3 -> 1 Zoznam susedstva hlavy vrcholu 3 -> 4 -> 2 -> 1 Priľahlosť zoznam vertex 4 head -> 3 -> 1 -> 0>
Prechádzanie grafom
Breadth-First Search alebo BFS
Prechod do šírky pretože graf je podobný prechodu stromu do šírky. Jediným háčikom je, že na rozdiel od stromov môžu grafy obsahovať cykly, takže sa môžeme opäť dostať do toho istého uzla. Aby sme sa vyhli spracovaniu uzla viac ako raz, používame boolovské navštívené pole. Pre jednoduchosť sa predpokladá, že všetky vrcholy sú dosiahnuteľné z počiatočného vrcholu.
Napríklad v nasledujúcom grafe začneme prechádzať od vrcholu 2. Keď prídeme k vrcholu 0, hľadáme všetky jeho susedné vrcholy. 2 je tiež susedný vrchol 0. Ak neoznačíme navštívené vrcholy, potom sa 2 znova spracuje a stane sa neukončujúcim procesom. Prechod do šírky nasledujúceho grafu 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> |
>
>Výkon
Following is Breadth First Traversal (starting from vertex 2) 2 0 3 1>
Časová zložitosť: O(V+E) kde V je počet vrcholov v grafe a E je počet hrán v grafe.
Hĺbkové prvé vyhľadávanie alebo DFS
Prvý prechod do hĺbky pretože graf je podobný ako hĺbka prvého prechodu stromu. Jediným háčikom je, že na rozdiel od stromov môžu grafy obsahovať cykly, uzol možno navštíviť dvakrát. Ak sa chcete vyhnúť spracovaniu uzla viac ako raz, použite boolovské navštívené pole.
Algoritmus:
- Vytvorte rekurzívnu funkciu, ktorá vezme index uzla a navštívené pole.
- Označte aktuálny uzol ako navštívený a vytlačte ho.
- Prejdite všetky susedné a neoznačené uzly a zavolajte rekurzívnu funkciu s indexom susedného uzla.
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>)> |
>
>Výkon
Following is DFS from (starting from vertex 2) 2 0 1 3>
Časová zložitosť: O(V + E), kde V je počet vrcholov a E je počet hrán v grafe.