Introduksjon til graf i datastruktur
Grafer er ikke-lineære datastrukturer som omfatter et begrenset sett med noder og kanter. Knutepunktene er elementene og kantene er bestilte par forbindelser mellom nodene.
Legg merke til ordet ikke-lineært. En ikke-lineær datastruktur er en der elementene ikke er ordnet i rekkefølge. For eksempel er en matrise en lineær datastruktur fordi elementene er ordnet etter hverandre. Du kan krysse av alle elementene i en gruppe i en enkelt kjøring. Slik er det ikke med ikke-lineære datastrukturer. Elementene i en ikke-lineær datastruktur er ordnet i flere nivåer, ofte etter et hierarkisk mønster. Grafer er ikke-lineære.
Det neste ordet å ta hensyn til er begrenset. Vi definerer grafen for å ha et begrenset og tellbart antall noder. Dette er et ganske ikke-behagelig begrep. I hovedsak kan en graf ha et uendelig antall noder og fremdeles være begrenset. For eksempel et slektstre som strekker seg tilbake til Adam og Eva. Dette er en relativt uendelig graf, men er fortsatt tellbar og regnes dermed som begrenset.
Virkelighetseksempel
Det beste eksemplet på grafer i den virkelige verden er Facebook. Hver person på Facebook er en node og er koblet gjennom kanter. A er en venn av B. B er en venn av C og så videre.
terminologier
Her er terminologiene for graf i datastruktur nevnt nedenfor
1. Grafrepresentasjon: Generelt er en graf representert som et par sett (V, E). V er settet med vertekser eller noder. E er settet Edges. I eksemplet ovenfor,
V = (A, B, C, D, E)
E = (AB, AC, AD, BE, CD, DE)
2. Node eller toppunkt: Elementene i en graf kobles gjennom kanter.
3. Kanter: En bane eller en linje mellom to hjørner i en graf.
4. Tilstøtende noder: To noder kalles tilstøtende hvis de er koblet gjennom en kant. I eksemplet ovenfor er node A tilstøtende til nodene B, C og D, men ikke til knutepunkt E.
5. Sti: Sti er en sekvens av kanter mellom to noder. Det er egentlig en gjennomgang som starter ved en node og slutter ved en annen. I eksemplet over er det flere stier fra knutepunkt A til knutepunkt E.
Sti (A, E) = (AB, BE)
ELLER
Sti (A, E) = (AC, CD, DE)
ELLER
Sti (A, E) = (AD, DE)
6. Ustyret graf: En rettet graf er en der kantene ikke spesifiserer en bestemt retning. Kantene er toveis.
Eksempel
I dette eksemplet kan kanten AC således krysses fra både A til C og C til A. Lignende på alle kantene. En bane fra node B til node C vil være enten (BA, AC) eller (BD, DC).
7. Rettet graf: En rettet graf er en der kantene bare kan krysses i en spesifisert retning.
Eksempel
I samme eksempel er nå kantene retningsgivende. Du kan bare krysse kanten langs dens retning. Det er ingen bane fra node B til node C nå.
8. Vektet graf: En vektet graf er en der kantene er assosiert med en vekt. Dette er vanligvis kostnadene for å krysse kanten.
Eksempel
I det samme eksempelet har nå kantene en viss vekt forbundet med dem. Det er to mulige stier mellom knutepunkt A til knutepunkt E.
Bane1 = (AB, BD, DE), Vekt1 = 3 + 2 + 5 = 10
Sti2 = (AC, CD, DE), Vekt2 = 1 + 3 + 5 = 9
Det er klart at man foretrekker Path2 hvis målet er å nå node E fra node A med minimumskostnader.
Grunnleggende operasjoner på graf
Her er grunnleggende operasjoner av grafen omtale nedenfor
1. Legg til / fjern Vertex
Dette er den enkleste operasjonen i grafen. Du legger ganske enkelt et toppunkt til en graf. Det trenger ikke være koblet til noe annet toppunkt gjennom en kant. Når du fjerner et toppunkt, må du fjerne alle kanter som stammer fra og slutter ved det slettede toppunktet.
2. Legg til / fjern kant
Denne operasjonen legger til eller fjerner en kant mellom to hjørner. Når alle kantene som stammer fra og slutter ved et toppunkt blir slettet, blir toppunktet et isolert toppunkt.
3. Breadth-First Search (BFS)
Dette er en gjennomgående operasjon i grafen. BFS går horisontalt gjennom grafen. Dette betyr at den krysser alle nodene på et enkelt nivå før du går videre til neste nivå.
BFS-algoritmen starter på toppen av den første noden i grafen og krysser deretter alle tilstøtende noder til den. Når alle tilstøtende noder er krysset, gjentar algoritmen den samme prosedyren for underordnede noder.
Eksempel
Å krysse grafen ovenfor på BFS-måte ville resultere fra A -> B -> C -> D -> E -> F -> G. Algoritmen starter fra node A og krysser alle tilstøtende noder B, C og D. Den markerer alle de fire nodene som besøkes. Når alle de tilstøtende nodene til A er krysset, beveger algoritmen seg til den første tilstøtende noden til A og gjentar den samme prosedyren. I dette tilfellet er noden B og de tilstøtende noder til B er E og F. Deretter krysses de tilstøtende noder til C. Når alle nodene er besøkt, avsluttes operasjonen.
4. Dybde første søk (DFS)
Deepth First Search eller DFS krysser grafen vertikalt. Det starter med rotnoden eller den første noden i grafen og krysser alle underordnede knutepunkter før du flytter til de tilstøtende nodene.
Eksempel
Å krysse grafen ovenfor på BFS-måte ville resultere fra A -> B -> E -> F -> C -> G -> D. Algoritmen starter fra knutepunkt A og krysser alle dens barneknuter. Så snart den møter B, ser det ut til at den har ytterligere barneknuter. Så krysses barneknuter av B før de går videre til neste barneknute av A.
Real-implementering av grafer
- Design av elektriske kretser for kraftoverføring.
- Design av nettverk av sammenkoblede datamaskiner.
- Studie av molekylær, kjemisk og cellulær struktur for ethvert stoff, f.eks. Humant DNA.
- Design av transportveier mellom byer og steder i en by.
Konklusjon - Graf i datastruktur
Grafer er et veldig nyttig konsept i datastrukturer. Den har praktiske implementeringer på nesten alle felt. Det er veldig viktig å forstå det grunnleggende i grafteori, for å utvikle en forståelse av algoritmene til grafstrukturen.
Denne artikkelen var bare en introduksjon til grafer. Det er bare et springbrett. Det anbefales å dypdykk videre i emnet grafteori.
Anbefalte artikler
Dette er en guide til grafen i datastruktur. Her diskuterer vi terminologiene og grunnleggende operasjoner av graf i datastruktur. Du kan også se på følgende artikkel for å lære mer -
- Spørsmål om datastrukturintervju
- Datamodell i Cassandra
- Hva er Data Mart?
- Hva er en dataforsker?