Datové struktury představují způsob organizace dat tak, aby k nim bylo možné přistupovat efektivněji v závislosti na situaci. Datové struktury jsou základy jakéhokoli programovacího jazyka, kolem kterého je program postaven. Python pomáhá naučit se základy těchto datových struktur jednodušším způsobem ve srovnání s jinými programovacími jazyky.
V tomto článku budeme diskutovat o datových strukturách v programovacím jazyce Python a o tom, jak souvisejí s některými konkrétními vestavěnými datovými strukturami, jako jsou n-tice seznamů, slovníky atd., a také s některými pokročilými datovými strukturami, jako jsou stromy, grafy atd.
Seznamy
Seznamy Pythonu jsou stejně jako pole deklarované v jiných jazycích, což je uspořádaná kolekce dat. Je velmi flexibilní, protože položky v seznamu nemusí být stejného typu.
Implementace Python Listu je podobná jako Vectors v C++ nebo ArrayList v JAVA. Nákladnou operací je vložení nebo odstranění prvku ze začátku seznamu, protože je potřeba posunout všechny prvky. Vkládání a mazání na konci seznamu může být také nákladné v případě, že se předem přidělená paměť zaplní.
Můžeme vytvořit seznam v pythonu, jak je uvedeno níže.
Příklad: Vytvoření seznamu Python
Python3
List> => [> 1> ,> 2> ,> 3> ,> 'GFG'> ,> 2.3> ]> print> (> List> )> |
>
>Výstup
[1, 2, 3, 'GFG', 2.3]>
Prvky seznamu jsou přístupné pomocí přiřazeného indexu. V pythonu počátečním indexu seznamu je sekvence 0 a koncový index je (pokud je tam N prvků) N-1.
Příklad: Operace seznamu v Pythonu
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> ])> |
>
jaké jsou rozměry obrazovky mého počítače
>Výstup
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 jako hashovací tabulky v jakémkoli jiném jazyce s časovou složitostí O(1). Je to neuspořádaná kolekce datových hodnot, která se používá k ukládání datových hodnot jako mapa, která na rozdíl od jiných datových typů, které obsahují pouze jednu hodnotu jako prvek, Dictionary obsahuje pár klíč:hodnota. Pro lepší optimalizaci je ve slovníku uveden pár klíč–hodnota.
Indexování Python Dictionary se provádí pomocí klíčů. Jsou libovolného hašovatelného typu, tj. objekt, který se nikdy nemůže změnit jako řetězce, čísla, n-tice atd. Můžeme vytvořit slovník pomocí složených závorek ({}) nebo porozumění slovníku .
Příklad: Operace slovníku Pythonu
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ýstup
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 sbírka objektů Pythonu podobně jako seznam, ale n-tice jsou svou podstatou neměnné, tj. prvky v n-tice nelze po vytvoření přidat ani odebrat. Stejně jako seznam může i Tuple obsahovat prvky různých typů.
V Pythonu se n-tice vytvářejí umístěním posloupnosti hodnot oddělených „čárkou“ s nebo bez použití závorek pro seskupování posloupnosti dat.
Poznámka: N-tice lze vytvořit i s jediným prvkem, ale je to trochu složitější. Mít jeden prvek v závorce nestačí, musí tam být koncová ,čárka‘, aby to byla n-tice.
Pří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ýstup
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>
Soubor
Sada Python je neuspořádaná kolekce dat, která je proměnlivá a neumožňuje žádný duplicitní prvek. Sady se v zásadě používají k testování členství a eliminaci duplicitních záznamů. Datová struktura použitá v tomto je hashování, populární technika k provádění vkládání, mazání a procházení v průměru v O(1).
Pokud je na stejné pozici indexu přítomno více hodnot, pak se hodnota připojí k této pozici indexu a vytvoří se propojený seznam. V sadách CPythonu jsou implementovány pomocí slovníku s fiktivními proměnnými, kde klíčové bytosti nastavují členové s větší optimalizací na časovou složitost.
Implementace sady:
Sady s mnoha operacemi v jedné hashTable:
Příklad: Operace sady Python
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ýstup
Set with the use of Mixed Values {1, 2, 'Geeks', 4, 6, 'For'} Elements of set: 1 2 Geeks 4 6 For True>
Mražené sady
Zamrzlé sady v Pythonu jsou neměnné objekty, které podporují pouze metody a operátory, které vytvářejí výsledek, aniž by ovlivnily zmrazenou sadu nebo sady, na které jsou aplikovány. Zatímco prvky sady lze kdykoli upravit, prvky zmrazené sady zůstanou po vytvoření stejné.
Pokud nejsou předány žádné parametry, vrátí prázdnou sadu zmrazených hodnot.
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ýstup
Normal Set {'a', 'c', 'b'} Frozen Set frozenset({'g', 'e', 'f'})>
Tětiva
Řetězce Pythonu jsou pole bajtů představující znaky Unicode. Jednodušeji řečeno, řetězec je neměnné pole znaků. Python nemá datový typ znak, jeden znak je prostě řetězec o délce 1.
Poznámka: Protože řetězce jsou neměnné, úprava řetězce povede k vytvoření nové kopie.
Příklad: Operace s řetězci Pythonu
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ýstup
Creating String: Welcome to GeeksForGeeks First character of String is: W Last character of String is: s>
Bytearray
Python Bytearray poskytuje proměnlivou sekvenci celých čísel v rozsahu 0 <= x < 256.
Příklad: Operace 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ýstup
Creating Bytearray: bytearray(b'x0cx08x19x02') Accessing Elements: 8 After Modifying: bytearray(b'x0cx03x19x02') After Adding Elements: bytearray(b'x0cx03x19x02x1e')>
Doposud jsme studovali všechny datové struktury, které jsou integrovány do jádra Pythonu. Nyní se ponořte hlouběji do Pythonu a podívejte se na modul kolekcí, který poskytuje některé kontejnery, které jsou v mnoha případech užitečné a poskytují více funkcí než výše definované funkce.
Modul sbírek
Modul sběru Pythonu byl představen pro zlepšení funkčnosti vestavěných datových typů. Poskytuje různé kontejnery, podívejme se na každý z nich podrobně.
Počítadla
Počítadlo je podtřídou slovníku. Používá se k udržení počtu prvků v iterovateli ve formě neuspořádaného slovníku, kde klíč představuje prvek v iterovateli a hodnota představuje počet tohoto prvku v iterovateli. To je ekvivalentní sáčku nebo více sadě jiných jazyků.
Příklad: Operace čítače 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ýstup
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 také podtřídou slovníku, ale na rozdíl od slovníku si pamatuje pořadí, ve kterém byly klíče vloženy.
Příklad: Operace 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ýstup
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 používá k poskytnutí některých výchozích hodnot pro klíč, který neexistuje a nikdy nevyvolá chybu KeyError. Jeho objekty lze inicializovat pomocí metody DefaultDict() předáním datového typu jako argumentu.
Poznámka: default_factory je funkce, která poskytuje výchozí hodnotu pro vytvořený slovník. Pokud tento parametr chybí, je aktivována chyba KeyError.
Příklad: Operace 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ýstup
defaultdict(, {1: 2, 2: 3, 3: 1, 4: 2})>
Řetězová mapa
ChainMap zapouzdřuje mnoho slovníků do jedné jednotky a vrací seznam slovníků. Když je potřeba najít klíč, prohledají se všechny slovníky jeden po druhém, dokud není klíč nalezen.
Pří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ýstup
ChainMap({'a': 1, 'b': 2}, {'c': 3, 'd': 4}, {'e': 5, 'f': 6}) 1>
KeyError: 'g'>
PojmenovanéTuple
A PojmenovanéTuple vrací objekt n-tice se jmény pro každou pozici, které běžné n-tice postrádají. Zvažte například n-tici jmen student, kde první prvek představuje fname, druhý představuje lname a třetí prvek představuje DOB. Předpokládejme, že pro volání fname namísto zapamatování pozice indexu můžete prvek skutečně zavolat pomocí argumentu fname, pak bude pro přístup k prvku n-tice opravdu snadný. Tuto funkci poskytuje NamedTuple.
Pří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ýstup
The Student age using index is : 19 The Student name using keyname is : Nandini>
O čem
Deque (dvojitě ukončená fronta) je seznam optimalizovaný pro rychlejší operace připojení a otevření z obou stran kontejneru. Poskytuje časovou složitost O(1) pro operace připojení a pop ve srovnání se seznamem s časovou složitostí O(n).
Python Deque je implementován pomocí dvojitě propojených seznamů, takže výkon pro náhodný přístup k prvkům je O(n).
Příklad: 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)> |
řazení seznamů java
>
>Výstup
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 kontejner podobný slovníku, který funguje jako obal kolem objektů slovníku. Tento kontejner se používá, když si někdo chce vytvořit svůj vlastní slovník s nějakou upravenou nebo novou funkcí.
Pří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ýstup
Original Dictionary {'a': 1, 'b': 2, 'c': 3}>
RuntimeError: Deletion not allowed>
Seznam uživatelů
UserList je kontejner podobný seznamu, který funguje jako obal kolem objektů seznamu. To je užitečné, když si někdo chce vytvořit svůj vlastní seznam s nějakou upravenou nebo dodatečnou funkcí.
Pří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ýstup
Original List [1, 2, 3, 4] After Insertion [1, 2, 3, 4, 5]>
RuntimeError: Deletion not allowed>
UserString
UserString je kontejner podobný řetězci a stejně jako UserDict a UserList funguje jako obal kolem řetězcových objektů. Používá se, když si někdo chce vytvořit vlastní řetězce s nějakou upravenou nebo doplňkovou funkcí.
Pří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ýstup
Original String: Geeks String After Appending: Geekss String after Removing: Gkss>
Nyní po prostudování všech datových struktur se podívejme na některé pokročilé datové struktury, jako je zásobník, fronta, graf, propojený seznam atd., které lze použít v jazyce Python.
Spojový seznam
Propojený seznam je lineární datová struktura, ve které nejsou prvky uloženy na souvislých paměťových místech. Prvky v propojeném seznamu jsou propojeny pomocí ukazatelů, jak je znázorněno na obrázku níže:
Propojený seznam je reprezentován ukazatelem na první uzel propojeného seznamu. První uzel se nazývá hlava. Pokud je propojený seznam prázdný, pak je hodnota hlavičky NULL. Každý uzel v seznamu se skládá alespoň ze dvou částí:
- Data
- Ukazatel (nebo odkaz) na další uzel
Příklad: Definování propojeného seznamu 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> |
>
>
Vytvořme jednoduchý propojený seznam se 3 uzly.
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 |> > +----+------+ +----+------+ +----+------+> > '''> |
>
>
Procházení propojeného seznamu
V předchozím programu jsme vytvořili jednoduchý propojený seznam se třemi uzly. Projdeme vytvořený seznam a vytiskneme data každého uzlu. Pro procházení si napišme obecnou funkci printList(), která vytiskne libovolný daný 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()> |
>
>Výstup
1 2 3>
Zásobník
A zásobník je lineární datová struktura, která ukládá položky způsobem Last-In/First-Out (LIFO) nebo First-In/Last-Out (FILO). V zásobníku je nový prvek přidán na jeden konec a prvek je odstraněn pouze z tohoto konce. Operace vložení a odstranění se často nazývají push a pop.
Funkce spojené se zásobníkem jsou:
- empty() – Vrátí, zda je zásobník prázdný – Časová složitost: O(1) size() – Vrátí velikost zásobníku – Časová složitost: O(1) top() – Vrátí odkaz na nejvyšší prvek zásobníku – Časová složitost: O(1) push(a) – Vloží prvek „a“ na vrchol zásobníku – Časová složitost: O(1) pop() – Odstraní nejvyšší prvek zásobníku – Časová složitost: O( 1)
Implementace Python Stack
Stack v Pythonu lze implementovat pomocí následujících způsobů:
- seznam
- Collections.deque
- fronta.LifoQueue
Implementace pomocí Seznam
Vestavěný seznam datových struktur Pythonu lze použít jako zásobník. Místo push() se append() používá k přidávání prvků na vrchol zásobníku, zatímco pop() odstraňuje prvek v pořadí 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ýstup
Initial stack ['g', 'f', 'g'] Elements popped from stack: g f g Stack after elements are popped: []>
Implementace pomocí collections.deque:
Zásobník Pythonu lze implementovat pomocí třídy deque z modulu collections. Deque je preferováno před seznamem v případech, kdy potřebujeme rychlejší operace připojení a pop z obou konců kontejneru, protože deque poskytuje časovou složitost O(1) pro operace připojení a pop ve srovnání se seznamem, který poskytuje O(n) časovou složitost.
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ýstup
Initial stack: deque(['g', 'f', 'g']) Elements popped from stack: g f g Stack after elements are popped: deque([])>
Implementace pomocí modulu front
Modul fronty má také frontu LIFO, což je v podstatě zásobník. Data se vkládají do fronty pomocí funkce put() a get() odebírá data z fronty.
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ýstup
0 Full: True Size: 3 Elements popped from the stack g f g Empty: True>
Fronta
Jako zásobník, fronta je lineární datová struktura, která ukládá položky způsobem First In First Out (FIFO). U fronty je jako první odstraněna nejméně nedávno přidaná položka. Dobrým příkladem fronty je jakákoli fronta spotřebitelů pro zdroj, kde je jako první obsluhován spotřebitel, který přišel jako první.
Operace spojené s frontou jsou:
- Zařadit do fronty: Přidá položku do fronty. Pokud je fronta plná, jedná se o podmínku přetečení – Časová složitost: O(1) Dequeue: Odebere položku z fronty. Položky se vyskakují ve stejném pořadí, v jakém jsou posouvány. Pokud je fronta prázdná, pak se říká, že jde o podmínku podtečení – Časová složitost: O(1) Přední: Získání přední položky z fronty – Časová složitost: O(1) Zadní: Získání poslední položky z fronty – Časová složitost : O(1)
Implementace fronty Pythonu
Fronta v Pythonu může být implementována následujícími způsoby:
- seznam
- sbírky.deque
- ocas.ocas
Implementace pomocí seznamu
Místo enqueue() a dequeue() se používá funkce 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ýstup
Initial queue ['g', 'f', 'g'] Elements dequeued from queue g f g Queue after removing elements []>
Implementace pomocí collections.deque
Deque je preferováno před seznamem v případech, kdy potřebujeme rychlejší operace připojení a pop z obou konců kontejneru, protože deque poskytuje časovou složitost O(1) pro operace připojení a pop ve srovnání se seznamem, který poskytuje O(n) časovou složitost.
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ýstup
Initial queue deque(['g', 'f', 'g']) Elements dequeued from the queue g f g Queue after removing elements deque([])>
Implementace pomocí queue.Queue
jak spustit skript v linuxu
queue.Queue(maxsize) inicializuje proměnnou na maximální velikost maxsize. Maximální velikost nula „0“ znamená nekonečnou frontu. Tato fronta se řídí pravidlem 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ýstup
0 Full: True Elements dequeued from the queue g f g Empty: True Empty: False Full: False>
Prioritní fronta
Prioritní fronty jsou abstraktní datové struktury, kde každá data/hodnota ve frontě má určitou prioritu. Například u leteckých společností dorazí zavazadla s názvem Business nebo First-class dříve než ostatní. Prioritní fronta je rozšířením fronty s následujícími vlastnostmi.
- Prvek s vysokou prioritou je vyřazen z fronty před prvkem s nízkou prioritou.
- Pokud mají dva prvky stejnou prioritu, jsou obsluhovány podle pořadí ve frontě.
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ýstup
12 1 14 7 14 12 7 1>
Fronta haldy (nebo haldaq)
modul heapq v Pythonu poskytuje datovou strukturu haldy, která se používá hlavně k reprezentaci prioritní fronty. Vlastností této datové struktury v Pythonu je, že pokaždé, když je vyskakován nejmenší prvek haldy (min-heap). Kdykoli jsou prvky zatlačeny nebo vyskočeny, struktura haldy je zachována. Prvek haldy[0] také pokaždé vrátí nejmenší prvek.
Podporuje extrakci a vložení nejmenšího prvku v časech 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))> |
>
>Výstup
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ární strom
Strom je hierarchická datová struktura, která vypadá jako na obrázku níže –
tree ---- j <-- root / f k / a h z <-- leaves>
Nejvyšší uzel stromu se nazývá kořen, zatímco nejspodnější uzly nebo uzly bez potomků se nazývají listové uzly. Uzly, které jsou přímo pod uzlem, se nazývají jeho potomci a uzly, které jsou přímo nad něčím, se nazývají jeho rodiče.
Binární strom je strom, jehož prvky mohou mít téměř dvě děti. Protože každý prvek v binárním stromě může mít pouze 2 potomky, obvykle je pojmenováváme jako levé a pravé potomky. Uzel binárního stromu obsahuje následující části.
- Data
- Ukazatel na levé dítě
- Ukazatel na správné dítě
Příklad: Definování třídy uzlu
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> |
>
>
Nyní vytvoříme strom se 4 uzly v Pythonu. Předpokládejme, že stromová struktura vypadá níže –
tree ---- 1 <-- root / 2 3 / 4>
Příklad: Přidání dat 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'''> |
>
>
Procházení stromů
Stromy lze přecházet v různých cestách. Následují obecně používané způsoby procházení stromů. Podívejme se na níže uvedený strom -
tree ---- 1 <-- root / 2 3 / 4 5>
První procházení hloubky:
- Pořadí (vlevo, kořen, vpravo): 4 2 5 1 3
- Předobjednávka (kořen, vlevo, vpravo): 1 2 4 5 3
- Postorder (levý, pravý, kořenový) : 4 5 2 3 1
Algoritmus Inorder (strom)
- Projděte levý podstrom, tj. zavolejte Inorder (levý podstrom)
- Navštivte kořen.
- Projděte pravý podstrom, tj. zavolejte Inorder (pravý podstrom)
Předobjednávka algoritmu (strom)
- Navštivte kořen.
- Projděte levý podstrom, tj. zavolejte Preorder (levý podstrom)
- Projděte pravý podstrom, tj. zavolejte Preorder (pravý podstrom)
Algoritmus Poštovní poukázka (strom)
- Projděte levý podstrom, tj. zavolejte Postorder (levý podstrom)
- Projděte pravý podstrom, tj. zavolejte Postorder (pravý podstrom)
- Navštivte kořen.
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ýstup
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á složitost – O(n)
Procházení pořadím do šířky nebo úrovně
Průchod úrovňovým příkazem stromu je pro strom projížděním napřed na šířku. Procházení pořadí úrovní výše uvedeného stromu je 1 2 3 4 5.
Pro každý uzel je nejprve navštíven uzel a poté jsou jeho podřízené uzly umístěny do fronty FIFO. Níže je algoritmus pro totéž -
- Vytvořte prázdnou frontu q
- temp_node = root /*začít od root*/
- Smyčka, zatímco temp_node není NULL
- vytisknout temp_node->data.
- Zařaďte potomky temp_node (nejprve levé potom pravé potomky) do q
- Seřadit uzel 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ýstup
Level Order Traversal of binary tree is - 1 2 3 4 5>
Časová složitost: O(n)
Graf
A graf je nelineární datová struktura sestávající z uzlů a hran. Uzly jsou někdy také označovány jako vrcholy a hrany jsou čáry nebo oblouky, které spojují libovolné dva uzly v grafu. Formálněji lze graf definovat jako graf skládající se z konečné množiny vrcholů (nebo uzlů) a množiny hran, které spojují dvojici uzlů.
Ve výše uvedeném grafu je množina vrcholů V = {0,1,2,3,4} a množina hran E = {01, 12, 23, 34, 04, 14, 13}.
Následující dva jsou nejběžněji používané reprezentace grafu.
- Matice sousedství
- Seznam sousedství
Matice sousedství
Matice sousedství je 2D pole o velikosti V x V, kde V je počet vrcholů v grafu. Nechť je 2D pole adj[][], slot adj[i][j] = 1 znamená, že od vrcholu i k vrcholu j existuje hrana. Matice sousedství pro neorientovaný graf je vždy symetrická. Matice sousedství se také používá k reprezentaci vážených grafů. Pokud adj[i][j] = w, pak z vrcholu i do vrcholu 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ýstup
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)]
Matice sousedství 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]]
Seznam sousedství
Používá se řada seznamů. Velikost pole se rovná počtu vrcholů. Nechť pole je pole[]. Vstupní pole[i] představuje seznam vrcholů sousedících s i-tým vrcholem. Tuto reprezentaci lze také použít k reprezentaci váženého grafu. Váhy hran mohou být reprezentovány jako seznamy dvojic. Následuje znázornění seznamu sousedství výše 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ýstup
Adjacency list of vertex 0 head ->4 -> 1 Seznam sousedství hlavy 1 hlavy -> 4 -> 3 -> 2 -> 0 Seznam sousedství hlavy 2 -> 3 -> 1 Seznam sousedství hlavy 3 -> 4 -> 2 -> 1 seznam vertex 4 head -> 3 -> 1 -> 0>
Procházení grafu
Breadth-First Search nebo BFS
Přechod do šířky protože graf je podobný přechodu stromu do šířky. Jediný háček je v tom, že na rozdíl od stromů mohou grafy obsahovat cykly, takže se můžeme znovu dostat do stejného uzlu. Abychom se vyhnuli zpracování uzlu více než jednou, používáme booleovské navštívené pole. Pro jednoduchost se předpokládá, že všechny vrcholy jsou dosažitelné z počátečního vrcholu.
Například v následujícím grafu začneme procházení od vrcholu 2. Když dojdeme k vrcholu 0, hledáme všechny jeho sousední vrcholy. 2 je také sousedním vrcholem 0. Pokud neoznačíme navštívené vrcholy, pak se 2 zpracuje znovu a stane se neukončujícím procesem. Průchod do šířky následujícího 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ýstup
Following is Breadth First Traversal (starting from vertex 2) 2 0 3 1>
Časová složitost: O(V+E) kde V je počet vrcholů v grafu a E je počet hran v grafu.
Depth First Search nebo DFS
Hloubka první průchod protože graf je podobný jako Hloubka prvního průchodu stromu. Jediný háček je, že na rozdíl od stromů mohou grafy obsahovat cykly, uzel lze navštívit dvakrát. Chcete-li se vyhnout zpracování uzlu více než jednou, použijte booleovské navštívené pole.
Algoritmus:
- Vytvořte rekurzivní funkci, která vezme index uzlu a navštívené pole.
- Označte aktuální uzel jako navštívený a vytiskněte uzel.
- Projděte všechny sousední a neoznačené uzly a zavolejte rekurzivní funkci s indexem sousedního uzlu.
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ýstup
Following is DFS from (starting from vertex 2) 2 0 1 3>
Časová složitost: O(V + E), kde V je počet vrcholů a E je počet hran v grafu.