Johdanto graafiseen tietorakenteeseen
Kaaviot ovat epälineaarisia tietorakenteita, jotka käsittävät rajallisen joukon solmuja ja reunoja. Solmut ovat elementtejä ja reunat on järjestetty pariksi kytkentäpariksi solmujen välillä.
Huomaa sana epälineaarinen. Epälineaarinen tietorakenne on sellainen, jossa elementtejä ei ole järjestetty peräkkäisessä järjestyksessä. Esimerkiksi taulukko on lineaarinen tietorakenne, koska elementit on järjestetty peräkkäin. Voit käydä läpi kaikki taulukon elementit yhdellä ajolla. Näin ei ole epälineaaristen tietorakenteiden tapauksessa. Epälineaarisen tietorakenteen elementit on järjestetty useille tasoille, usein hierarkkisen mallin mukaisesti. Kaaviot ovat epälineaarisia.
Seuraava sana, johon kiinnitetään huomiota, on äärellinen. Määrittelemme kuvaajan siten, että siinä on äärellinen ja laskettava määrä solmuja. Tämä on melko sopimaton termi. Pohjimmiltaan graafilla voi olla ääretön määrä solmuja ja se voi silti olla äärellinen. Esimerkiksi sukupuu, joka ulottuu Aadamiin ja Eevaan. Tämä on suhteellisen ääretön kuvaaja, mutta on silti luettavissa ja sitä pidetään siten äärellisenä.
Todellisen maailman esimerkki
Paras esimerkki reaalimaailman kaavioista on Facebook. Jokainen Facebookin henkilö on solmu ja on yhteydessä reunojen kautta. A on B.: n ystävä. B on C: n ystävä ja niin edelleen.
terminologiaa
Tässä on jäljempänä mainitut datarakenteen kaavion terminologiat
1. Kuvion esitys: Kaavio esitetään yleensä joukkona parina (V, E). V on kärkien tai solmujen joukko. E on reunajoukko. Yllä olevassa esimerkissä
V = (A, B, C, D, E)
E = (AB, AC, AD, BE, CD, DE)
2. Solmu tai Vertex: Graafin elementit on kytketty reunojen läpi.
3. Reunat: Polku tai viiva kuvaajan kahden kärkipisteen välillä.
4. Vierekkäiset solmut: Kaksi solmua kutsutaan vierekkäin, jos ne on kytketty reunan kautta. Yllä olevassa esimerkissä solmu A on lähellä solmuja B, C ja D, mutta ei solmua E.
5. Polku: Polku on sarja solmuja kahden solmun välillä. Se on olennaisesti poikkisuunta, joka alkaa yhdestä solmusta ja päättyy toiseen. Yllä olevassa esimerkissä on useita polkuja solmusta A solmuun E.
Polku (A, E) = (AB, BE)
TAI
Polku (A, E) = (AC, CD, DE)
TAI
Polku (A, E) = (AD, DE)
6. Suuntaamaton kuvaaja: Suuntaamaton kuvaaja on kaavio, jonka reunat eivät määritä tiettyä suuntaa. Reunat ovat kaksisuuntaisia.
esimerkki
Siten tässä esimerkissä reuna AC voidaan kuljettaa sekä A: sta C: ään että C: stä A: seen. Samanlainen kuin kaikki reunat. Polku solmusta B solmuun C olisi joko (BA, AC) tai (BD, DC).
7. Suunnattu kuvaaja: Suuntautunut kuvaaja on graafi, jossa reunat voidaan kulkea vain määrätyssä suunnassa.
esimerkki
Siten samassa esimerkissä reunat ovat nyt suunnattuja. Voit kulkea reunaa vain sen suuntaan. Ei ole polkua solmusta B solmuun C nyt.
8. Painotettu kuvaaja: Painotettu kuvaaja on graafi, jossa reunat liitetään painoon. Tämä on yleensä reunan kulkemisen kustannus.
esimerkki
Siten samassa esimerkissä reunoilla on nyt tietty paino niihin liittyvissä kohdissa. Solmun A ja solmun E välillä on kaksi mahdollista reittiä.
Polku1 = (AB, BD, DE), paino1 = 3 + 2 + 5 = 10
Polku2 = (AC, CD, DE), paino2 = 1 + 3 + 5 = 9
On selvää, että polku2 olisi parempi, jos tavoitteena on päästä solmuun E solmusta A pienin kustannuksin.
Graafin perustoiminnot
Tässä on alla mainitut kuvaajan perusoperaatiot
1. Lisää / poista Vertex
Tämä on kaavion yksinkertaisin toimenpide. Lisää vain kärki kuvaajaan. Sitä ei tarvitse kytkeä mihinkään muuhun kärkeen reunan kautta. Kun poistat kärkipisteen, sinun on poistettava kaikki poistetusta kärjestä lähtevät ja loppuvia reunat.
2. Lisää / poista reuna
Tämä toimenpide lisää tai poistaa reunan kahden kärkipisteen välillä. Kun kaikki reunat, jotka lähtevät kärjestä ja päättyvät siihen, poistetaan, kärjestä tulee eristetty kärkipiste.
3. Leveys ensimmäinen haku (BFS)
Tämä on käyräoperaatio kuvaajassa. BFS kulkee kuvaajan vaakatasossa. Tämä tarkoittaa, että se kulkee kaikki solmut yhdellä tasolla ennen siirtymistä seuraavalle tasolle.
BFS-algoritmi alkaa kuvaajan ensimmäisen solmun yläosasta ja kulkee sitten kaikki vierekkäiset solmut siihen. Kun kaikki vierekkäiset solmut on ohitettu, algoritmi toistaa saman toimenpiteen lapsisolmuille.
esimerkki
Yllä olevan kaavion siirtäminen BFS-tavalla johtaisi A -> B -> C -> D -> E -> F -> G. Algoritmi alkaa solmusta A ja kulkee kaikki vierekkäiset solmut B, C ja D. Se merkitsee. kaikki neljä solmua vierailtuina. Kun kaikki A: n vierekkäiset solmut on ohitettu, algoritmi siirtyy A: n ensimmäiseen viereiseen solmuun ja toistaa saman menettelyn. Tässä tapauksessa solmu on B ja B: n viereiset solmut ovat E ja F. Seuraavaksi C: n viereiset solmut kulkevat. Kun kaikki solmut on käyty, toiminta päättyy.
4. Syvyyshaku (DFS)
Ensimmäinen syvyyshaku tai DFS kulkee kuvaajaa pystysuunnassa. Se alkaa juurisolmulla tai kuvaajan ensimmäisellä solmulla ja kulkee kaikki lapsisolmut ennen siirtymistä viereisiin solmuihin.
esimerkki
Yllä olevan kaavion siirtäminen BFS-tavalla johtaisi A -> B -> E -> F -> C -> G -> D. Algoritmi alkaa solmusta A ja kulkee kaikki sen alaisolmut. Heti kun se kohtaa B: n, näyttää siltä, että sillä on lisää lapsisolmuja. Joten B: n lapsisolmut ohitetaan ennen siirtymistä A: n seuraavaan lapsisolmuun.
Kaavioiden reaalimaailman toteutukset
- Sähkövirtojen suunnittelu sähkönsiirtoa varten.
- Liitettyjen tietokoneiden verkon suunnittelu.
- Minkä tahansa aineen, esimerkiksi ihmisen DNA: n, molekyyli-, kemiallisen ja solurakenteen tutkiminen.
- Kaupunkien ja kaupunkien välisten kuljetusreittien suunnittelu.
Johtopäätös - kuvaaja tietorakenteessa
Kaaviot ovat erittäin hyödyllinen käsite tietorakenteissa. Sillä on käytännön toteutuksia melkein kaikilla aloilla. On erittäin tärkeää ymmärtää graafiteorian perusteet, kehittää ymmärrys graafin rakenteen algoritmeista.
Tämä artikkeli oli vain johdanto kaavioihin. Se on vain askel. Graafiteorian aiheeseen on suositeltavaa syventyä edelleen.
Suositellut artikkelit
Tämä on opas tietorakenteen kaavioon. Tässä keskustellaan termin rakenteista ja graafisista perustoiminnoista tietorakenteessa. Voit myös tarkastella seuraavaa artikkelia saadaksesi lisätietoja -
- Tietorakenteen haastattelua koskevat kysymykset
- Datamalli Cassandrassa
- Mikä on Data Mart?
- Mikä on tietoteknikko?