Kaavion tietorakenne on kokoelma solmut yhdistänyt reunat . Sitä käytetään edustamaan eri entiteettien välisiä suhteita. Graafialgoritmit ovat menetelmiä, joita käytetään käsittelemään ja analysoimaan kuvaajia, ratkaisemaan erilaisia ​​​​ongelmia, kuten löytää lyhimmän polun tai syklien havaitseminen.

lisäyslajittelualgoritmit

Sisällysluettelo

• Graafin komponentit
• Graafeiden perustoiminnot
• Graafin sovellukset
• Graafin perusteet
• BFS ja DFS kaaviossa
• Syklit kaaviossa
• Lyhin polku kaaviossa
• Vähintään virittävä puu
• Topologinen lajittelu
• Yhteydet kaaviossa
• Maksimivirtaus kaaviossa
• Joidenkin täytyy tehdä ongelmia kaaviossa
• Jotkut tietokilpailut

Graafin osat:

• Vertices: Vertices ovat graafin perusyksiköitä. Joskus kärkipisteitä kutsutaan myös pisteiksi tai solmuiksi. Jokainen solmu/kärkipiste voi olla merkitty tai merkitsemätön.
• Reunat: Reunat piirretään tai niitä käytetään yhdistämään kaavion kaksi solmua. Sen voi tilata solmuparin suunnatussa graafissa. Reunat voivat yhdistää mitkä tahansa kaksi solmua millä tahansa mahdollisella tavalla. Ei ole sääntöjä. Joskus reunat tunnetaan myös kaareina. Jokainen reuna voidaan merkitä / poistaa.

Graafeiden perustoiminnot:

Alla on kaavion perustoiminnot:

• Solmujen/reunojen lisääminen kaavioon – Lisää solmu kuvaajaan.
• Solmujen/reunojen poistaminen kaaviosta – Poista solmu kaaviosta.
• Haku kaavioista – Hae kaavion kokonaisuutta.
• Kuvaajien läpikulku – Kaikkien kaavion solmujen läpikulku.

Graafin sovellukset:

Seuraavat ovat tosielämän sovelluksia:

• Kaaviotietorakenteita voidaan käyttää kuvaamaan joukkueen pelaajien välistä vuorovaikutusta, kuten syöttejä, laukauksia ja taklauksia. Näiden vuorovaikutusten analysointi voi antaa oivalluksia tiimin dynamiikasta ja parannusalueista.
• Käytetään yleisesti edustamaan sosiaalisia verkostoja, kuten ystäväverkostoja sosiaalisessa mediassa.
• Graafeja voidaan käyttää kuvaamaan tietokoneverkkojen topologiaa, kuten reitittimien ja kytkimien välisiä yhteyksiä.
• Graafeja käytetään kuvaamaan yhteyksiä liikenneverkon eri paikkojen, kuten teiden ja lentokenttien, välillä.
• Graafeja käytetään hermoverkoissa, joissa kärjet edustavat neuroneja ja reunat edustavat niiden välisiä synapseja. Neuroverkkoja käytetään ymmärtämään, kuinka aivomme toimivat ja kuinka yhteydet muuttuvat oppiessamme. Ihmisen aivoissa on noin 10^11 neuronia ja lähes 10^15 synapsia.

Graafin perusteet:

• Johdatus graafisiin
• Graafi ja sen esitykset
• Graafityypit ja esimerkkejä
• Graafin perusominaisuudet
• Grafin sovellukset, edut ja haitat
• Transponoi kaavio
• Ero kuvaajan ja puun välillä

BFS ja DFS kaaviossa:

• Leveys ensimmäinen läpikäynti kaaviota varten
• Syvyys Ensimmäinen läpikäynti kaaviota varten
• Ensimmäisen syvyyshaun sovellukset
• Breadth First Traversalin sovellukset
• Iteratiivinen syvyys ensimmäinen haku
• BFS katkaistua kuvaajaa varten
• Kuvaajan transitiivinen sulkeminen DFS:n avulla
• Ero BFS:n ja DFS:n välillä

Syklit kaaviossa:

• Havaitse sykli suunnatussa kaaviossa
• Havaitse sykli ohjaamattomassa kaaviossa
• Tunnista sykli suorassa kaaviossa värejä käyttämällä
• Havaitse negatiivinen sykli kaaviossa | (Bellman Ford)
• Suuntaamattoman ja yhdistetyn graafin syklit, joiden pituus on n
• Negatiivisen syklin havaitseminen Floyd Warshallin avulla
• Kloonaa suunnattu asyklinen kuvaaja
• Unioni sijoituksen mukaan ja polun pakkaus Union-Find-algoritmissa
• Lyhin polku kaaviossa:
  • Dijkstran lyhimmän polun algoritmi
  • Bellman-Ford-algoritmi
  • Floyd Warshall -algoritmi
  • Johnsonin algoritmi kaikkien parien lyhimmille poluille
  • Lyhin polku suunnatussa asyklisessä kaaviossa
  • Dial's Algorithm
  • Monivaiheinen kaavio (lyhyin polku)
  • Lyhin polku painottamattomassa kaaviossa
  • Karpin vähimmäiskeskimääräinen (tai keskimääräinen) painosyklin algoritmi
  • 0-1 BFS (lyhin reitti binääripainokaaviossa)
  • Etsi minimipainosykli ohjaamattomasta kaaviosta

  Minimi virityspuu:

  • Prim's Minimum Spanning Tree (MST)
  • Kruskalin minimivirittävän puun algoritmi
  • Ero Primin ja Kruskalin MST-algoritmin välillä
  • Vähimmäisvirittävän puun ongelman sovellukset
  • Vähimmäiskustannukset kaikkien kaupunkien yhdistämisestä
  • Kaavion virittävien puiden kokonaismäärä
  • Vähimmäistuotteen ulottuva puu
  • Käänteinen poistoalgoritmi vähimmäisvirityspuulle
  • Boruvkan algoritmi Minimum Spanning Tree

  Topologinen lajittelu:

  • Topologinen lajittelu
  • Kaikki topologiset suunnatut asykliset graafit
  • Kahnin algoritmi topologiselle lajittelulle
  • Maksimi reunat, jotka voidaan lisätä DAG: hen niin, että se on edelleen DAG
  • Pisin polku suunnatussa asyklisessä kaaviossa
  • Topologinen Graafin lajittelu käyttämällä kärjen lähtöaikaa

  Liitettävyys kaaviossa:

  • Artikulaatiopisteet (tai leikkauspisteet) kaaviossa
  • Kaksinkertaiset komponentit
  • Sillat kaaviossa
  • Eulerin polku ja piiri
  • Fleuryn algoritmi Eulerian polun tai piirin tulostamiseen
  • Vahvasti yhdistetyt komponentit
  • Laske kaikki mahdolliset kävelyt lähteestä määränpäähän tarkalleen k reunalla
  • Euler-piiri ohjatussa kaaviossa
  • Lyhimmän ketjun pituus kohdesanan saavuttamiseksi
  • Selvitä, voidaanko merkkijono ketjuttaa muodostamaan ympyrän
  • Tarjanin algoritmi vahvasti toisiinsa liittyvien komponenttien löytämiseksi
  • Polut kullekin solmulle kullekin reunalle (Seitsemän Königsbergin siltaa)
  • Dynaaminen liitettävyys | Sarja 1 (inkrementaalinen)

  Suurin virtaus kaaviossa:

  • Max Flow -ongelman esittely
  • Ford-Fulkerson-algoritmi maksimivirtausongelmaan
  • Etsi kahden kärjen välisten reunojen disjunktipolkujen enimmäismäärä
  • Etsi virtausverkon pienin s-t-leikkaus
  • Suurin kaksipuolinen vastaavuus
  • Kanavan määritysongelma
  • Johdatus Push Relabel -algoritmiin
  • Kargerin algoritmi - Joukko 1 - Johdanto ja toteutus
  • Dinicin algoritmi maksimivirtaukselle

  Joidenkin täytyy tehdä ongelmia kaaviossa:

  • Etsi Boolen matriisin suurimman alueen pituus
  • Laske puiden lukumäärä metsässä
  • Peterson-grafiikkaongelma
  • Kloonaa ohjaamaton kuvaaja
  • Kaavioiden väritys (johdanto ja sovellukset)
  • Travelling Salesman Problem (TSP) -toteutus
  • Vertex-kansiongelma | Sarja 1 (johdanto ja likimääräinen algoritmi)
  • K-keskusten ongelma | Sarja 1 (ahne likimääräinen algoritmi)
  • Erdos Renyl -malli (satunnaiskaavioiden luomiseen)
  • Kiinan postimies tai reittitarkastus | Sarja 1 (johdanto)
  • Hierholzerin algoritmi suunnatulle graafille
  • Tarkista, onko annettu graafi Bipartite vai ei
  • Käärme- ja tikapuuongelma
  • Boggle (Etsi kaikki mahdolliset sanat merkkitaulusta)
  • Hopcroft Karp -algoritmi maksimaaliseen yhteensovitukseen - Johdanto
  • Vähimmäisaika kaikkien appelsiinien mätänemiseen
  • Muodosta graafi kaikkien kärkien annetuista asteista
  • Selvitä, onko suunnatussa graafissa universaali nielu
  • Kaavion nielusolmujen lukumäärä
  • Kahden klikkin ongelma (tarkista, voidaanko kuvaaja jakaa kahdeksi klikkaukseksi)

  Muutamia tietokilpailuja:

  • Tietokilpailut Graph Traversalista
  • Tietokilpailut kaavion lyhyimmästä polusta
  • Tietokilpailut kaavion minimivirittävästä puusta
  • Tietokilpailut kaavioista

  Pikalinkit:

  • 10 suosituinta haastattelukysymystä syvällisestä ensimmäisestä hausta (DFS)
  • Mielenkiintoisia lyhimmän polun kysymyksiä
  • Videot Graphsissa

  Suositus:

  • Opi tietorakenne ja algoritmit | DSA opetusohjelma