Tietorakenteet ovat tapa järjestää tietoja niin, että niitä voidaan käyttää tehokkaammin tilanteesta riippuen. Tietorakenteet ovat minkä tahansa ohjelmointikielen perusta, jonka ympärille ohjelma rakennetaan. Python auttaa oppimaan näiden tietorakenteiden perusteet yksinkertaisemmalla tavalla muihin ohjelmointikieliin verrattuna.
Tässä artikkelissa keskustelemme Python-ohjelmointikielen tietorakenteista ja siitä, miten ne liittyvät joihinkin tiettyihin sisäänrakennettuihin tietorakenteisiin, kuten listatupleihin, sanakirjoihin jne., sekä joihinkin edistyneisiin tietorakenteisiin, kuten puihin, kaavioihin jne.
Luettelot
Python-listat ovat aivan kuten taulukot, ilmoitettu muilla kielillä, mikä on järjestetty datakokoelma. Se on erittäin joustava, koska luettelon kohteiden ei tarvitse olla samaa tyyppiä.
Python Listin toteutus on samanlainen kuin Vectors C++:ssa tai ArrayList JAVA:ssa. Kallis toiminto on elementin lisääminen tai poistaminen luettelon alusta, koska kaikkia elementtejä on siirrettävä. Listan lopusta lisääminen ja poistaminen voi myös tulla kalliiksi, jos esivarattu muisti täyttyy.
Voimme luoda luettelon pythonissa alla olevan kuvan mukaisesti.
Esimerkki: Python-luettelon luominen
Python 3
List> => [>1>,>2>,>3>,>'GFG'>,>2.3>]> print>(>List>)> |
>
>Lähtö
[1, 2, 3, 'GFG', 2.3]>
Luettelon elementtejä voi käyttää määritetyllä indeksillä. Listan python-aloitusindeksissä sekvenssi on 0 ja loppuindeksi (jos siinä on N elementtiä) N-1.
Esimerkki: Python List Operations
Python 3
# 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>])> |
>
koneella päivämäärä ja aika
>Lähtö
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>
Sanakirja
Python-sanakirja on kuin hash-taulukot missä tahansa muussa kielessä, jonka aikamonimutkaisuus on O(1). Se on järjestämätön tietoarvojen kokoelma, jota käytetään data-arvojen, kuten kartan, tallentamiseen. Sanakirja sisältää avain:arvo-parin, toisin kuin muut tietotyypit, joissa on vain yksi arvo elementtinä. Avainarvo on annettu sanakirjassa, jotta se olisi optimoitu.
Python-sanakirjan indeksointi tapahtuu avainten avulla. Nämä ovat mitä tahansa tiivistettävää tyyppiä eli objekteja, jotka eivät voi koskaan muuttua, kuten merkkijonot, numerot, monikot jne. Voimme luoda sanakirjan käyttämällä kiharaa aaltosuluja ({}) tai sanakirjan ymmärtäminen .
Esimerkki: Python-sanakirjatoiminnot
Python 3
# 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)> |
>
>Lähtö
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 on kokoelma Python-objekteja, kuten luettelo, mutta monikot ovat luonteeltaan muuttumattomia, eli monikossa olevia elementtejä ei voi lisätä tai poistaa luomisen jälkeen. Kuten luettelo, myös Tuple voi sisältää erityyppisiä elementtejä.
Pythonissa monikot luodaan sijoittamalla arvosarja, joka on erotettu 'pilkulla' joko sulkuilla tai ilman datasekvenssin ryhmittelyä.
Huomautus: Tuples voidaan luoda myös yhdestä elementistä, mutta se on hieman hankalaa. Yksi elementti sulkeissa ei riitä, vaan sen lopussa on oltava pilkku, jotta siitä tulee monikko.
Esimerkki: Python Tuple Operations
Python 3
# 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>])> |
>
>Lähtö
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> Aseta
Python-sarja on järjestämätön kokoelma dataa, joka on muuttuva ja joka ei salli päällekkäisiä elementtejä. Sarjoja käytetään periaatteessa jäsentestaukseen ja päällekkäisten merkintöjen poistamiseen. Tässä käytetty tietorakenne on Hashing, suosittu tekniikka lisätä, poistaa ja kulkea keskimäärin O(1):ssä.
Jos samassa indeksikohdassa on useita arvoja, arvo liitetään kyseiseen indeksipaikkaan linkitettyjen listan muodostamiseksi. Vuonna CPython Sets on toteutettu käyttämällä sanakirjaa, jossa on valemuuttujia, joissa avainolennot jäsenet asettavat suuremmilla optimoinnilla ajan monimutkaisuuteen.
Aseta toteutus:
Sarjat, joissa on useita toimintoja yhdessä hash-taulukossa:
Esimerkki: Python Set Operations
Python 3
# 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>)> |
>
>Lähtö
Set with the use of Mixed Values {1, 2, 'Geeks', 4, 6, 'For'} Elements of set: 1 2 Geeks 4 6 For True> Jäädytetyt sarjat
Pythonin jäädytetyt joukot ovat muuttumattomia objekteja, jotka tukevat vain menetelmiä ja operaattoreita, jotka tuottavat tuloksen vaikuttamatta jäädytettyyn joukkoon tai sarjoihin, joihin niitä käytetään. Vaikka joukon elementtejä voidaan muokata milloin tahansa, jäädytetyn joukon elementit pysyvät samoina luomisen jälkeen.
Jos parametreja ei välitetä, se palauttaa tyhjän jäädytetyn joukon.
Python 3
# 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')> |
>
>Lähtö
Normal Set {'a', 'c', 'b'} Frozen Set frozenset({'g', 'e', 'f'})> merkkijono
Python-merkkijonot ovat Unicode-merkkejä edustavia tavutaulukoita. Yksinkertaisemmin sanottuna merkkijono on muuttumaton merkkijono. Pythonilla ei ole merkkitietotyyppiä, yksi merkki on yksinkertaisesti merkkijono, jonka pituus on 1.
Huomautus: Koska merkkijonot ovat muuttumattomia, merkkijonon muokkaaminen johtaa uuden kopion luomiseen.
Esimerkki: Python-merkkijonotoiminnot
Python 3
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>])> |
>
>Lähtö
Creating String: Welcome to GeeksForGeeks First character of String is: W Last character of String is: s>
Bytearray
Python Bytearray antaa muuttuvan kokonaislukujonon välillä 0 <= x < 256.
Esimerkki: Python Bytearray -toiminnot
Python 3
# 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)> |
>
>Lähtö
Creating Bytearray: bytearray(b'x0cx08x19x02') Accessing Elements: 8 After Modifying: bytearray(b'x0cx03x19x02') After Adding Elements: bytearray(b'x0cx03x19x02x1e')>
Tähän mennessä olemme tutkineet kaikkia Python-ytimen sisäänrakennettuja tietorakenteita. Sukella nyt syvemmälle Pythoniin ja katso kokoelmamoduuli, joka tarjoaa joitain säiliöitä, jotka ovat hyödyllisiä monissa tapauksissa ja tarjoavat enemmän ominaisuuksia kuin yllä määritellyt toiminnot.
Kokoelmat moduuli
Python-kokoelmamoduuli otettiin käyttöön parantamaan sisäänrakennettujen tietotyyppien toimivuutta. Se tarjoaa erilaisia säiliöitä, katsotaanpa jokainen niistä yksityiskohtaisesti.
Laskurit
Laskuri on sanakirjan alaluokka. Sitä käytetään pitämään iteroitavissa olevien elementtien lukumäärä järjestämättömän sanakirjan muodossa, jossa avain edustaa iteroitavissa olevaa elementtiä ja arvo edustaa iteroitavan elementin määrää. Tämä vastaa pussia tai muita kieliä.
Esimerkki: Python-laskuritoiminnot
Python 3
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)> |
>
>Lähtö
Counter({'B': 5, 'A': 3, 'C': 2}) Counter({'B': 5, 'A': 3, 'C': 2}) Counter({'B': 5, 'A': 4, 'C': 2, 1: 1})> TilattuDict
An TilattuDict on myös sanakirjan alaluokka, mutta toisin kuin sanakirja, se muistaa järjestyksen, jossa avaimet lisättiin.
Esimerkki: Python OrderedDict Operations
Python 3
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)> |
>
>Lähtö
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>
OletusDict
OletusDict käytetään antamaan joitakin oletusarvoja avaimelle, jota ei ole olemassa ja joka ei koskaan aiheuta avainvirhettä. Sen objektit voidaan alustaa DefaultDict()-menetelmällä välittämällä tietotyyppi argumenttina.
Huomautus: default_factory on funktio, joka tarjoaa oletusarvon luodulle sanakirjalle. Jos tämä parametri puuttuu, KeyError nostetaan.
Esimerkki: Python DefaultDict -toiminnot
Python 3
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)> |
>
>Lähtö
defaultdict(, {1: 2, 2: 3, 3: 1, 4: 2})> Ketjukartta
ChainMap kapseloi useita sanakirjoja yhdeksi yksiköksi ja palauttaa luettelon sanakirjoista. Kun avain on löydettävä, kaikkia sanakirjoja etsitään yksitellen, kunnes avain löytyy.
Esimerkki: Python ChainMap -toiminnot
Python 3
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'>])> |
>
>
Lähtö
ChainMap({'a': 1, 'b': 2}, {'c': 3, 'd': 4}, {'e': 5, 'f': 6}) 1> KeyError: 'g'>
Nimetty Tuple
A Nimetty Tuple palauttaa monikkoobjektin, jossa on nimet jokaiselle sijainnille, joka tavallisilta monikoilta puuttuu. Ajatellaan esimerkiksi tuple names opiskelijaa, jossa ensimmäinen elementti edustaa fname, toinen edustaa lname ja kolmas elementti edustaa DOB. Oletetaan, että kutsuttaessa fname sen sijaan, että muistaisit indeksipaikan, voit itse kutsua elementtiä käyttämällä fname-argumenttia, niin tuples-elementin käyttäminen on todella helppoa. Tämän toiminnon tarjoaa NamedTuple.
Esimerkki: Python NamedTuple -toiminnot
Python 3
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)> |
>
>Lähtö
The Student age using index is : 19 The Student name using keyname is : Nandini>
Mistä
Deque (kaksinkertainen jono) on optimoitu luettelo nopeampiin lisäys- ja pop-toimintoihin säilön molemmilta puolilta. Se tarjoaa O(1)-aikaisen monimutkaisuuden liittämis- ja pop-operaatioille verrattuna O(n)-aikaisen monimutkaisuuden luetteloon.
Python Deque on toteutettu käyttämällä kaksoislinkitettyjä listoja, joten elementtien satunnaisen käytön suorituskyky on O(n).
Esimerkki: Python Deque -toiminnot
Python 3
# 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)> |
linkitetty lista
>
>Lähtö
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 on sanakirjamainen säilö, joka toimii kääreenä sanakirjaobjektien ympärillä. Tätä säilöä käytetään, kun joku haluaa luoda oman sanakirjan, jossa on joitain muokattuja tai uusia toimintoja.
Esimerkki: Python UserDict
Python 3
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>)> |
>
>
Lähtö
Original Dictionary {'a': 1, 'b': 2, 'c': 3}> RuntimeError: Deletion not allowed>
Käyttäjälista
UserList on luettelomainen säilö, joka toimii luetteloobjektien ympärillä olevana kääreenä. Tästä on hyötyä, kun joku haluaa luoda oman luettelonsa muokatuilla tai lisätoiminnoilla.
Esimerkkejä: Python UserList
Python 3
# 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()> |
>
>
Lähtö
Original List [1, 2, 3, 4] After Insertion [1, 2, 3, 4, 5]>
RuntimeError: Deletion not allowed>
UserString
UserString on merkkijonomainen säiliö ja aivan kuten UserDict ja UserList, se toimii kääreenä merkkijonoobjektien ympärillä. Sitä käytetään, kun joku haluaa luoda omia merkkijonoja muokatuilla tai lisätoiminnoilla.
Esimerkki: Python UserString
Python 3
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)> |
>
>Lähtö
Original String: Geeks String After Appending: Geekss String after Removing: Gkss>
Nyt kun olet tutkinut kaikki tietorakenteet, katsotaanpa joitain edistyneitä tietorakenteita, kuten pino, jono, kaavio, linkitetty luettelo jne., joita voidaan käyttää Python-kielessä.
Linkitetty lista
Linkitetty lista on lineaarinen tietorakenne, jossa elementtejä ei ole tallennettu vierekkäisiin muistipaikkoihin. Linkitetyn luettelon elementit linkitetään osoittimilla alla olevan kuvan mukaisesti:
Linkitettyä luetteloa edustaa osoitin linkitetyn luettelon ensimmäiseen solmuun. Ensimmäistä solmua kutsutaan pääksi. Jos linkitetty lista on tyhjä, pään arvo on NULL. Jokainen listan solmu koostuu vähintään kahdesta osasta:
- Data
- Osoitin (tai viittaus) seuraavaan solmuun
Esimerkki: Linkitetyn luettelon määrittäminen Pythonissa
Python 3
# 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> |
>
>
Luodaan yksinkertainen linkitetty luettelo, jossa on 3 solmua.
Python 3
# 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 | nolla | | 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 |> >+----+------+ +----+------+ +----+------+> >'''> |
>
>
Linked List Traversal
Edellisessä ohjelmassa olemme luoneet yksinkertaisen linkitetyn luettelon, jossa on kolme solmua. Käydään läpi luotu lista ja tulostetaan kunkin solmun tiedot. Läpikulkua varten kirjoitetaan yleiskäyttöinen funktio printList(), joka tulostaa minkä tahansa listan.
Python 3
# 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()> |
>
>Lähtö
1 2 3>
Pino
A pino on lineaarinen tietorakenne, joka tallentaa kohteita Last-In/First-Out (LIFO) tai First-In/Last-Out (FILO) tavalla. Pinossa uusi elementti lisätään toiseen päähän ja elementti poistetaan vain siitä päästä. Lisää- ja poistotoimintoja kutsutaan usein push- ja pop-toiminnoiksi.
Pinoon liittyvät toiminnot ovat:
- tyhjä() – Palauttaa onko pino tyhjä – Aika monimutkaisuus: O(1) size() – Palauttaa pinon koon – Aika monimutkaisuus: O(1) top() – Palauttaa viittauksen pinon ylimpään elementtiin – Aika monimutkaisuus: O(1) push(a) – Lisää elementin 'a' pinon yläosaan – Aika monimutkaisuus: O(1) pop() – Poistaa pinon ylimmän elementin – Aika monimutkaisuus: O( 1)
Python Stack -toteutus
Pino Pythonissa voidaan toteuttaa seuraavilla tavoilla:
- lista
- Collections.deque
- jono.LifoQueue
Toteutus listalla
Pythonin sisäänrakennettua tietorakennelistaa voidaan käyttää pinona. Kommentin push() sijaan append()-funktiota käytetään lisäämään elementtejä pinon yläosaan, kun taas pop() poistaa elementin LIFO-järjestyksessä.
Python 3
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> |
>
>Lähtö
Initial stack ['g', 'f', 'g'] Elements popped from stack: g f g Stack after elements are popped: []>
Käyttöönotto collections.dequen avulla:
Python-pino voidaan toteuttaa käyttämällä deque-luokkaa kokoelmamoduulista. Deque on suositeltavampi kuin luettelo tapauksissa, joissa tarvitsemme nopeampia liite- ja pop-operaatioita säilön molemmista päistä, koska deque tarjoaa O(1)-ajan monimutkaisuuden liittämis- ja pop-operaatioille verrattuna luetteloon, joka tarjoaa O(n) aika monimutkaisuus.
Python 3
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> |
>
>Lähtö
Initial stack: deque(['g', 'f', 'g']) Elements popped from stack: g f g Stack after elements are popped: deque([])>
Toteutus jonomoduulilla
Jonomoduulissa on myös LIFO-jono, joka on periaatteessa pino. Data lisätään jonoon put()-funktiolla ja get() ottaa tiedot pois jonosta.
Python 3
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())> |
>
>Lähtö
0 Full: True Size: 3 Elements popped from the stack g f g Empty: True>
Jonottaa
Pinona, jonottaa on lineaarinen tietorakenne, joka tallentaa kohteet FIFO (First In First Out) -tavalla. Jonossa viimeksi lisätty kohde poistetaan ensin. Hyvä esimerkki jonosta on mikä tahansa kuluttajien jono resurssille, jossa ensin palvellaan ensin tullutta kuluttajaa.
Jonoon liittyvät toiminnot ovat:
- Jono: Lisää kohteen jonoon. Jos jono on täynnä, sen sanotaan olevan ylivuotoehto – Aika monimutkaisuus: O(1) Dequeue: Poistaa kohteen jonosta. Kohteet pompataan samassa järjestyksessä, jossa ne työnnetään. Jos jono on tyhjä, sen sanotaan olevan alivuotoehto – Ajan monimutkaisuus: O(1) Etuosa: Hae jonosta etuosa – Aika monimutkaisuus: O(1) Takana: Hae viimeinen kohde jonosta – Aika monimutkaisuus : O(1)
Python-jonon toteutus
Pythonin jono voidaan toteuttaa seuraavilla tavoilla:
- lista
- kokoelmat.deque
- häntä.häntä
Toteutus listan avulla
Funktioiden enqueue() ja dequeue() sijasta käytetään append()- ja pop()-funktioita.
Python 3
# 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> |
>
>Lähtö
Initial queue ['g', 'f', 'g'] Elements dequeued from queue g f g Queue after removing elements []>
Toteutus collections.dequen avulla
Deque on suositeltavampi kuin luettelo tapauksissa, joissa tarvitsemme nopeampia liite- ja pop-operaatioita säilön molemmista päistä, koska deque tarjoaa O(1)-ajan monimutkaisuuden liittämis- ja pop-operaatioille verrattuna luetteloon, joka tarjoaa O(n) aika monimutkaisuus.
Python 3
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> |
>
>Lähtö
Initial queue deque(['g', 'f', 'g']) Elements dequeued from the queue g f g Queue after removing elements deque([])>
Toteutus käyttäen queue.Queue
muuntaa str int:ksi
queue.Queue(maxsize) alustaa muuttujan enimmäiskoon maksimikokoon. Maksimikoko nolla '0' tarkoittaa ääretöntä jonoa. Tämä jono noudattaa FIFO-sääntöä.
Python 3
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())> |
>
>Lähtö
0 Full: True Elements dequeued from the queue g f g Empty: True Empty: False Full: False>
Prioriteettijono
Prioriteettijonot ovat abstrakteja tietorakenteita, joissa jokaisella jonon tiedolla/arvolla on tietty prioriteetti. Esimerkiksi lentoyhtiöillä matkatavarat, joiden otsikko on Business tai First Class, saapuvat aikaisemmin kuin muut. Priority Queue on jonon laajennus seuraavilla ominaisuuksilla.
- Korkean prioriteetin elementti poistetaan jonosta ennen matalan prioriteetin elementtiä.
- Jos kahdella elementillä on sama prioriteetti, ne toimitetaan niiden järjestyksen mukaan jonossa.
Python 3
# 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]>>>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())> |
>
>Lähtö
12 1 14 7 14 12 7 1>
Keon jono (tai kasoq)
heapq-moduuli Pythonissa tarjoaa keon tietorakenteen, jota käytetään pääasiassa edustamaan prioriteettijonoa. Tämän Pythonin tietorakenteen ominaisuus on, että joka kerta kun pienin kasoelementti pompataan (min-heap). Aina kun elementtejä työnnetään tai poksetaan, kasarakenne säilyy. Hep[0]-elementti palauttaa myös pienimmän elementin joka kerta.
Se tukee pienimmän elementin poistamista ja lisäämistä O(log n)-ajoissa.
Python 3
# 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))> |
>
>Lähtö
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ääripuu
Puu on hierarkkinen tietorakenne, joka näyttää alla olevasta kuvasta -
tree ---- j <-- root / f k / a h z <-- leaves>
Puun ylintä solmua kutsutaan juureksi, kun taas alimpia solmuja tai solmuja, joissa ei ole lapsia, kutsutaan lehtisolmuiksi. Solmuja, jotka ovat suoraan solmun alla, kutsutaan sen lapsiksi ja solmuja, jotka ovat suoraan jonkin solmun yläpuolella, kutsutaan sen yläpääksi.
Binääripuu on puu, jonka elementeillä voi olla melkein kaksi lasta. Koska jokaisella binääripuun elementillä voi olla vain 2 alaosaa, annamme yleensä nimet vasemmalle ja oikealle lapselle. Binaaripuusolmu sisältää seuraavat osat.
- Data
- Osoitin vasemmalle lapselle
- Osoita oikeaa lasta
Esimerkki: Solmuluokan määrittäminen
Python 3
# 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> |
>
>
Luodaan nyt puu, jossa on 4 solmua Pythonissa. Oletetaan, että puurakenne näyttää alla olevalta -
tree ---- 1 <-- root / 2 3 / 4>
Esimerkki: Tietojen lisääminen puuhun
Python 3
# 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'''> |
>
>
Puun läpikulku
Puut voidaan ajella eri tavoin. Seuraavassa on yleisesti käytettyjä tapoja puiden ylittämiseen. Tarkastellaanpa alla olevaa puuta -
tree ---- 1 <-- root / 2 3 / 4 5>
Syvyys ensimmäiset matkat:
- Järjestys (vasen, juuri, oikea): 4 2 5 1 3
- Ennakkotilaus (juuri, vasen, oikea): 1 2 4 5 3
- Postorder (vasen, oikea, juuri): 4 5 2 3 1
Algoritmin järjestys(puu)
- Kävele vasemman alipuun läpi, eli kutsu Inorder(vasen-alipuu)
- Vieraile juurella.
- Kulje oikeanpuoleisen alipuun läpi, eli kutsu Inorder(oikea-alipuu)
Algoritmin ennakkotilaus (puu)
- Vieraile juurella.
- Kävele vasemman alipuun läpi, eli kutsu Preorder(left-subtree)
- Kulje oikeanpuoleisen alipuun läpi, eli kutsu Preorder(oikea-alipuu)
Algoritmi Postimääräys (puu)
- Kävele vasemman alipuun läpi, eli kutsu Postorder(vasen-alipuu)
- Kulje oikeanpuoleisen alipuun läpi, eli kutsu Postorder(oikea-alipuu)
- Vieraile juurella.
Python 3
# 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)> |
>
>Lähtö
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>
Aika monimutkaisuus – O(n)
Leveys-First tai Level Order Traversal
Tasotilauksen läpikulku puu on leveys-ensimmäinen läpikulku puulle. Yllä olevan puun tasojärjestyksen läpikulku on 1 2 3 4 5.
Jokaisen solmun kohdalla käydään ensin solmussa ja sitten sen lapsisolmut asetetaan FIFO-jonoon. Alla on algoritmi samalle -
- Luo tyhjä jono q
- temp_node = juuri /*aloita juuresta*/
- Silmukka kun temp_node ei ole NULL
- tulosta temp_node-> data.
- Jonota temp_node:n lapset (ensin vasen ja sitten oikea lapsi) kohtaan q
- Pura solmu q:sta
Python 3
# 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)>>> > ># 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)> |
>
>Lähtö
Level Order Traversal of binary tree is - 1 2 3 4 5>
Aika monimutkaisuus: O(n)
Kaavio
A kaavio on epälineaarinen tietorakenne, joka koostuu solmuista ja reunoista. Solmuja kutsutaan joskus myös kärkipisteiksi ja reunat ovat viivoja tai kaaria, jotka yhdistävät mitä tahansa kahta graafin solmua. Muodollisemmin Graafi voidaan määritellä kuvaajaksi, joka koostuu äärellisestä joukosta pisteitä (tai solmuja) ja joukosta reunoja, jotka yhdistävät solmuparin.
Yllä olevassa kaaviossa kärkijoukko V = {0,1,2,3,4} ja reunojen joukko E = {01, 12, 23, 34, 04, 14, 13}.
Seuraavat kaksi ovat graafin yleisimmin käytettyjä esityksiä.
- Vierekkäisyysmatriisi
- Vierekkäisten kohteiden luettelo
Vierekkäisyysmatriisi
Vierekkäisyysmatriisi on 2D-taulukko, jonka koko on V x V, jossa V on graafin kärkien lukumäärä. Olkoon 2D-taulukko adj[][], väli adj[i][j] = 1 osoittaa, että kärjestä i kärkeen j on reuna. Suuntaamattoman graafin viereisyysmatriisi on aina symmetrinen. Vierekkäisyysmatriisia käytetään myös painotettujen kuvaajien esittämiseen. Jos adj[i][j] = w, niin kärjestä i kärkeen j on reuna, jonka paino on w.
Python 3
# 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())> |
>
>
Lähtö
Graafin pisteet
['A B C D E F']
Graafin reunat
[('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)]
Graafin vierekkäisyysmatriisi
[[-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]]
Vierekkäisten kohteiden luettelo
Käytössä on joukko luetteloita. Taulukon koko on yhtä suuri kuin pisteiden lukumäärä. Olkoon taulukko taulukko[]. Syöttötaulukko[i] edustaa listaa i:nnen kärjen viereisistä pisteistä. Tätä esitystä voidaan käyttää myös painotetun graafin esittämiseen. Reunojen painot voidaan esittää pariluetteloina. Seuraavassa on vierekkäisyysluetteloesitys yllä olevasta kaaviosta.
Python 3
# 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()> |
>
>Lähtö
Adjacency list of vertex 0 head ->4 -> 1 vierekkäisyyslista kärjestä 1 pää -> 4 -> 3 -> 2 -> 0 vierekkäisyyslista kärjestä 2 pää -> 3 -> 1 vierekkäinen luettelo kärjestä 3 pää -> 4 -> 2 -> 1 vierekkäisyys lista kärjestä 4 head -> 3 -> 1 -> 0>>Kaavion läpikulku
Breadth-First Search tai BFS
Breadth-First Traversal kaavio on samanlainen kuin puun leveys-ensimmäinen läpikulku. Ainoa saalis tässä on, toisin kuin puut, graafit voivat sisältää syklejä, joten voimme päästä samaan solmuun uudelleen. Jotta vältytään käsittelemästä solmua useammin kuin kerran, käytämme boolen vierailtua taulukkoa. Yksinkertaisuuden vuoksi oletetaan, että kaikki kärjet ovat saavutettavissa aloituspisteestä.
Esimerkiksi seuraavassa graafissa aloitamme kulkemisen kärjestä 2. Kun saavumme kärkeen 0, etsimme sen kaikki vierekkäiset kärjet. 2 on myös 0:n viereinen kärkipiste. Jos emme merkitse vierailtuja pisteitä, 2 käsitellään uudelleen ja siitä tulee ei-päättyvä prosessi. Seuraavan kaavion Leveys-First Traversal on 2, 0, 3, 1.
Python 3
# 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> |
>Lähtö
Following is Breadth First Traversal (starting from vertex 2) 2 0 3 1>
Aika monimutkaisuus: O(V+E) missä V on graafin kärkien lukumäärä ja E on graafin reunojen lukumäärä.
Syvyys ensimmäinen haku tai DFS
Syvyys ensimmäinen läpikulku kaavio on samanlainen kuin puun syvyys ensimmäinen läpikulku. Ainoa saalis tässä on, toisin kuin puut, kaaviot voivat sisältää jaksoja, solmussa voidaan käydä kahdesti. Voit välttää solmun käsittelyn useammin kuin kerran käyttämällä loogista vierailtua taulukkoa.
Algoritmi:
- Luo rekursiivinen funktio, joka ottaa solmun indeksin ja vieraillun taulukon.
- Merkitse nykyinen solmu vierailluksi ja tulosta solmu.
- Käy läpi kaikki viereiset ja merkitsemättömät solmut ja kutsu rekursiivista funktiota viereisen solmun indeksillä.
Python 3
# 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>)> |
>
>Lähtö
Following is DFS from (starting from vertex 2) 2 0 1 3>
Aikamonimutkaisuus: O(V + E), jossa V on graafin kärkien lukumäärä ja E on graafin reunojen lukumäärä.