Tietorakenteet 101: Kaaviot - Visuaalinen esittely aloittelijoille

Tutustu päivittäin käyttämiisi tietorakenteisiin

? Tervetuloa! Aloitetaan joistakin elintavoista. Anna kun kysyn sinulta jotakin:

✅ Käytätkö Google-hakua?

✅ Käytätkö Google Mapsia?

✅ Käytätkö sosiaalisen median sivustoja?

Jos vastauksesi on "kyllä" mihinkään näistä kysymyksistä, olet ehdottomasti käyttänyt kaavioita etkä edes tiennyt sitä! Yllättynyt? ? minäkin olin! Tämä artikkeli antaa sinulle visuaalisen johdannon kaavioiden maailmaan, niiden tarkoitukseen, elementteihin ja tyyppeihin.

Nämä tietorakenteet todella kiinnittivät huomioni heidän hämmästyttävien ominaisuuksiensa vuoksi. Ne ovat niin voimakkaita, ettet edes osaa kuvitella, kuinka monipuoliset heidän todelliset sovelluksensa voivat olla. Aloitetaanpa! ?

? Reaalimaailman sovellukset - Taika alkaa!

Kaavioita käytetään eri toimialoilla ja aloilla:

  • GPS-järjestelmät ja Google Maps käyttävät kaavioiden avulla lyhintä reittiä määränpäästä toiseen.
  • Sosiaaliset verkostot käyttävät kaavioita käyttäjien välisten yhteyksien kuvaamiseen.
  • Google- hakualgoritmi määrittää kaavioiden avulla hakutulosten osuvuuden.
  • Operations Research on ala, joka etsii kaavioiden avulla optimaalisen reitin tuotteiden ja palvelujen kuljetus- ja toimituskustannusten alentamiseksi.
  • Jopa kemia käyttää kaavioitaedustamaan molekyylejä !!! ❤️

Heidän sovelluksensa ovat hämmästyttäviä, eikö?

Aloitetaan matkamme tämän maailman läpi! ?

? Tapaa kaaviot!

Nyt kun sinulla on jonkinlainen konteksti, aloitetaan puhumalla heidän päätarkoituksestaan ​​ja elementeistään.

Kaavioita käytetään elementtien (talot, lentokentät, sijainnit, käyttäjät, artikkelit jne.) Välisten yhteyksien kuvaamiseen, etsimiseen, analysointiin ja optimointiin.

Tämä on esimerkki siitä, miltä kaavio näyttää:

? Rakennuspalikat

Olen varma, että huomasit yllä olevassa kaaviossa kaksi pääelementtiä: ympyrät ja paksut viivat, jotka yhdistävät ne. Niitä kutsutaan vastaavasti solmuiksi ja reunoiksi .

Katsotaanpa ne tarkemmin! ?

  • Solmut: ne ovat elementtejä, jotka luovat verkon. Ne voivat edustaa taloja, sijainteja, lentokenttiä, satamia, bussipysäkkejä, rakennuksia, käyttäjiä, pohjimmiltaan mitä tahansa, jota voisit edustaa yhdistettynä muihin vastaaviin elementteihin verkossa.
  • Reunat: ne ovat yhteyksiä solmujen välillä. Ne voivat edustaa katuja, lentoja, bussireittejä, kahden käyttäjän välistä yhteyttä sosiaalisessa verkostossa tai mitä tahansa, mikä mahdollisesti edustaa yhteyttä solmujen välillä työskentelysi yhteydessä.

? Mitä tapahtuu, jos yhteyttä ei ole?

Jos kahta solmua ei ole yhdistetty reunalla, se tarkoittaa, että niiden välillä ei ole suoraa yhteyttä. Mutta älä paniikkia! ? Saatat silti pystyä siirtymään solmusta toiseen seuraamalla reunojen sarjaa, samalla tavalla kuin ajaessasi useita katuja lopulliseen määränpäähän. ?️ ? ?

Esimerkiksi alla olevassa kaaviossa, vaikka ei ole mitään suoraa yhteyttä ( reuna ) välinen violetti solmun (vasen) ja keltainen solmu (oikealla), voit siirtyä violetti solmusta oranssi solmuun, vaaleanpunainen solmu, vihreään solmuun ja saavuta lopulta keltainen solmu. ?

Tämä on kaavioiden keskeinen piirre, jonka avulla voit etsiä etsimääsi elementtiä seuraamalla käytettävissä olevia polkuja.

? Merkinnät ja terminologia

On erittäin tärkeää oppia muodollinen "kieli" toimimaan graafien kanssa:

  • |V|= Kaavion kärkipisteiden ( solmujen ) kokonaismäärä.
  • |E|= Kaavion liitosten ( reunojen ) kokonaismäärä.

Alla olevassa esimerkissä, |V| = 6koska solmuja (ympyröitä) ja kuutta on kuusi

|E| = 7koska reunoja (viivoja) on seitsemän.

? Kaavioiden tyypit

Kuvaajat luokitellaan niiden reunojen (yhteyksien) ominaisuuksien perusteella. Katsotaanpa niitä yksityiskohtaisesti! ?

1️⃣ Suunnatut kaaviot

Suunnatuissa kaavioissa reunoilla on suunta. He siirtyvät solmusta toiseen, eikä ole mitään tapaa palata alkuperäiseen solmuun tämän reunan kautta.

Kuten alla olevasta kaaviosta näet, reunoilla (liitännöillä) on nyt nuolet, jotka osoittavat tiettyyn suuntaan. Ajattele näitä reunoja yksisuuntaisina katuina. Voit mennä yhteen suuntaan ja saavuttaa määränpääsi, mutta et voi palata saman kadun kautta, joten sinun on löydettävä vaihtoehtoinen polku.

? Jos esimerkiksi luomme kaavion pizzan toimituspalvelulle, joka edustaa kaupunkia, kaksi taloa (solmua) voidaan yhdistää yksisuuntaisella kadulla (reuna). Voisit päästä talosta A taloon B tämän kadun kautta, mutta et voinut palata takaisin, joten sinun on valittava vaihtoehtoinen polku.

? Huomaa: Suunnatussa kuvaajassa et ehkä voi palata lainkaan alkuperäiseen sijaintiin, jollei polkua ole sopivilla suunilla. Below Alla olevasta kaaviosta näet, että voit siirtyä violetista solmusta vihreään solmuun, mutta huomaa, että vihreästä solmusta violettiin solmuun ei voida palata, koska reunat ovat "yksisuuntaisia ​​katuja. ”

2️⃣ Ohjaamattomat kaaviot

Tämän tyyppisessä kuvaajassa reunat ovat suuntaamattomia (niillä ei ole tiettyä suuntaa). Ajattele suuntaamattomia reunoja kaksisuuntaisina katuina. Voit siirtyä solmusta toiseen ja palata samalla "polulla".

? Huomaa: Kun näet kaavion kaaviosta, jossa reunoilla ei ole tiettyyn suuntaan osoittavia nuolia, voidaan olettaa, että kaaviota ei ole suunnattu.

? Pizzan toimituspalvelullemme tämä tarkoittaisi sitä, että toimitusmoottoripyörä voi kulkea lähteestä määränpäähän saman kadun tai polun kautta (heidän helpotuksekseen! ?).

Alla olevassa kaaviossa voit siirtyä violetista solmusta vihreään solmuun ja takaisin samalla polulla , joten et saavuta pisteitä, joista ei ole paluuta. ?

? Painot? - Kyllä, painot!

1️⃣ Painotetut kaaviot

Painotetuissa kaavioissa jokaisella reunalla on siihen liittyvä arvo (kutsutaan painoksi) . Tätä arvoa käytetään edustamaan tiettyä kvantifioitavaa suhdetta niiden yhdistämien solmujen välillä.

Painot voivat esimerkiksi edustaa etäisyyttä, aikaa, kahden käyttäjän välillä jaettujen yhteyksien määrää sosiaalisessa verkostossa tai mitä tahansa, jota voidaan käyttää kuvaamaan solmujen välistä yhteyttä kontekstissasi, jonka kanssa työskentelet.

Dijkstran algoritmi käyttää näitä painoja reittien optimointiin etsimällä lyhyimmät tai halvimmat polut verkon solmujen välillä. (Pysy kuulolla artikkelista Dijkstran algoritmista! ?).

2️⃣ Painottamattomat kaaviot

Sitä vastoin painottamattomien kuvaajien reunoihin ei ole liitetty painoja. Esimerkki tämän tyyppisestä kaaviosta löytyy sosiaalisista verkostoista, joissa reunat edustavat kahden käyttäjän välistä yhteyttä. Yhteyttä ei voida kvantifioida. Siksi reunalla ei ole painoa.

? Huomaa: Olet ehkä huomannut, että toistaiseksi kaavioissamme on vain yksi reuna, joka yhdistää jokaisen solmuparin . On luonnollista kysyä, voisiko solmuparin välillä olla enemmän kuin yksi reuna. Ctually, tämä on mahdollista M ultigraphs! T heillä voi olla useita reunoja, jotka yhdistävät saman solmuparin.

? Reunojen määrä! - tärkeä tekijä

On erittäin tärkeää tietää, onko kaaviossa useita tai vähän reunoja, koska tämä on ratkaiseva tekijä päättää, miten edustat tätä tietorakennetta koodissasi. Katsotaanpa erilaisia ​​tyyppejä! ?

1️⃣ Tiheät kaaviot

Tiheillä kaavioilla on monia reunoja. Mutta odota! ⚠️ Tiedän mitä sinun on ajateltava, kuinka voit selvittää mikä on "monta reunaa"? Tämä on vähän liian subjektiivista, eikö? ? Olen kanssasi samaa mieltä, joten määrittelemme se hieman:

? Etsitään enimmäismäärä reunoja kohdennetusta kaaviosta. Jos |V|suunnatussa kaaviossa on solmuja (alla olevassa esimerkissä kuusi solmua), se tarkoittaa, että jokaisella solmulla voi olla enintään |v|yhteyksiä (alla olevassa esimerkissä kuusi yhteyttä).

Miksi? Koska kukin solmu voisi mahdollisesti muodostaa yhteyden kaikkiin muihin solmuihin ja itseensä (katso alla oleva silmukka) . Näin ollen, enimmäismäärä reunoja, että kuvaaja voi olla on , joka on olevien solmujen kokonaislukumäärä kerrottuna yhteyksien enimmäismäärä että kukin solmu voi olla.|V|*|V|

Kun kaavion reunojen määrä on lähellä enimmäismäärää, kaavio on tiheä. ?

? Huomaa: ”Silmukat” syntyvät, kun solmulla on reuna, joka yhdistää sen itseensä. Outoa ja mielenkiintoista, eikö? ?

2️⃣ Harvat kuvaajat

Harvoilla kuvaajilla on vähän reunoja. Kuten alla olevasta kaaviosta näet, solmujen välillä ei ole paljon yhteyksiä.

Kun kaavion reunojen määrä on huomattavasti pienempi kuin enimmäismäärä reunoja, kaavio on harvinainen. ?

Meet️ Tapaa syklit!

Katsotaan nyt elintärkeä käsite kaavioiden, syklien ymmärtämiseksi.

Luultavasti huomasit, että jos seuraat kaavion yhdistyssarjaa, saatat löytää polun, joka vie sinut takaisin samaan solmuun. Tämä on kuin "käveleminen ympyröissä", aivan kuin ajaisit kaupunkisi ympäri ja valitsisit polun, joka voisi viedä sinut takaisin alkuperäiseen sijaintisi.

Kaavioissa näitä "pyöreitä" polkuja kutsutaan "jaksoiksi". Ne ovat kelvollisia polkuja, jotka alkavat ja päättyvät samassa solmussa. Esimerkiksi alla olevasta kaaviosta näet, että jos aloitat mistä tahansa solmusta, voit palata samaan solmuun seuraamalla reunoja.

Syklit eivät ole aina "eristettyjä", koska ne voivat olla osa suurempaa kuvaajaa. Voit tunnistaa ne aloittamalla haun tietyltä solmulta ja etsimällä polun, joka vie sinut takaisin samaan solmuun.

? Yhteenvetona…

  • Kaaviot ovat mahtavia tietorakenteita , joita käytät päivittäin Google-haun, Google Mapsin, GPS: n ja sosiaalisen median kautta.
  • Niitä käytetään kuvaamaan elementtejä, jotka jakavat yhteyksiä .
  • Kaavion elementtejä kutsutaan solmuiksi ja niiden välisiä yhteyksiä reuniksi .
  • Kaaviot voidaan suunnata, kun niiden reunoilla on tietty suunta, samanlainen yksisuuntaisten katujen kanssa, tai suuntaamattomasti, kun niiden reunoilla ei ole erityistä suuntaa, samanlainen kuin kaksisuuntaisten katujen.
  • Reunoilla voi olla niihin liittyvä arvo, jota kutsutaan painoksi .
  • Jos kuvaajalla on useita reunoja, sitä kutsutaan tiheäksi kaaviona. Muuten, jos sillä on vähän reunoja, sitä kutsutaan harvaksi kaaviona.
  • Sarja yhteyksiä voi muodostaa jakson, jos ne luovat polun, jonka avulla voit palata samaan solmuun.

Jatka oppimista näistä hämmästyttävistä tietorakenteista! Se on täysin sen arvoista tulevaisuudelle kehittäjänä. Oppin tietorakenteista juuri nyt, ja pidän niitä täysin kiehtovina. ? ? ❤️

Tärkeää on olla lopettamatta kyseenalaistamista. Uteliaisuudella on oma syy olemassaoloon. - Albert Einstein

? Kiitos!

Toivon todella, että pidit artikkelistani. ❤️

Seuraa minuaViserrys. ?