Introduktion til graf i datastruktur
Grafer er ikke-lineære datastrukturer omfattende et begrænset sæt knudepunkter og kanter. Knuderne er elementerne, og kanterne er bestilte par forbindelser mellem knudepunkterne.
Bemærk ordet ikke-lineært. En ikke-lineær datastruktur er en, hvor elementerne ikke er arrangeret i rækkefølge. For eksempel er en matrix en lineær datastruktur, fordi elementerne er arrangeret efter hinanden. Du kan krydse alle elementerne i en matrix i en enkelt kørsel. Dette er ikke tilfældet med ikke-lineære datastrukturer. Elementerne i en ikke-lineær datastruktur er arrangeret i flere niveauer, ofte efter et hierarkisk mønster. Grafer er ikke-lineære.
Det næste ord at være opmærksom på er begrænset. Vi definerer grafen til at have et begrænset og tællbart antal noder. Dette er et temmelig ikke-acceptabelt udtryk. I det væsentlige kan en graf have et uendeligt antal knudepunkter og stadig være begrænset. For eksempel et slægtstræ tilbage til Adam og Eva. Dette er en relativt uendelig graf, men er stadig tællelig og betragtes derfor som endelig.
Eksempel i den virkelige verden
Det bedste eksempel på grafer i den virkelige verden er Facebook. Hver person på Facebook er en knude og er forbundet via kanter. A er en ven af B. B er en ven af C og så videre.
terminologier
Her er nedenstående terminologier for graf i datastruktur
1. Grafrepræsentation: Generelt er en graf repræsenteret som et par sæt (V, E). V er sæt af knudepunkter eller knudepunkter. E er sæt af kanter. I ovenstående eksempel
V = (A, B, C, D, E)
E = (AB, AC, AD, BE, CD, DE)
2. Knude eller toppunkt: Elementerne i en graf er forbundet gennem kanterne.
3. Kanter: En sti eller en linje mellem to hjørner i en graf.
4. tilstødende noder: to noder kaldes tilstødende, hvis de er forbundet via en kant. I ovenstående eksempel er knudepunkt A tilstødende til knudepunkter B, C og D, men ikke til knudepunkt E.
5. Sti: Sti er en sekvens af kanter mellem to noder. Det er i det væsentlige en gennemgang der starter ved en knude og slutter ved en anden. I eksemplet ovenfor er der flere stier fra knudepunkt A til knudepunkt E.
Sti (A, E) = (AB, BE)
ELLER
Sti (A, E) = (AC, CD, DE)
ELLER
Sti (A, E) = (AD, DE)
6. Udirigeret graf: En ikke-rettet graf er en, hvor kanterne ikke angiver en bestemt retning. Kanterne er tovejsretninger.
Eksempel
I dette eksempel kan kanten AC således køres fra både A til C og C til A. Ligesom alle kanterne. En sti fra knudepunkt B til knudepunkt C ville være enten (BA, AC) eller (BD, DC).
7. Rettet graf: En rettet graf er en, hvor kanterne kun kan krydses i en specificeret retning.
Eksempel
I det samme eksempel er kanterne nu retningsbestemte. Du kan kun krydse kanten i dens retning. Der er ingen sti fra knudepunkt B til knudepunkt C nu.
8. Vægtet graf: En vægtet graf er en, hvor kanterne er forbundet med en vægt. Dette er generelt prisen for at krydse kanten.
Eksempel
I det samme eksempel har kanterne nu en vis vægt forbundet med dem. Der er to mulige stier mellem knudepunkt A til knudepunkt E.
Sti1 = (AB, BD, DE), vægt1 = 3 + 2 + 5 = 10
Sti2 = (AC, CD, DE), Vægt2 = 1 + 3 + 5 = 9
Det er klart, man foretrækker Path2, hvis målet er at nå knudepunkt E fra knudepunkt A med minimale omkostninger.
Grundlæggende operationer på graf
Her er de grundlæggende funktioner i grafen omtalt nedenfor
1. Tilføj / fjern Vertex
Dette er den enkleste operation i grafen. Du tilføjer blot et toppunkt til en graf. Det behøver ikke at være forbundet til noget andet toppunkt gennem en kant. Når du fjerner et toppunkt, skal du fjerne alle kanter, der stammer fra og slutter ved det slettede toppunkt.
2. Tilføj / fjern kant
Denne handling tilføjer eller fjerner en kant mellem to hjørner. Når alle kanter, der stammer fra og slutter ved et toppunkt, slettes, bliver toppunktet et isoleret toppunkt.
3. Breadth-First Search (BFS)
Dette er en gennemgående operation i grafen. BFS går vandret gennem grafen. Dette betyder, at det krydser alle knudepunkter på et enkelt niveau, før du fortsætter til det næste niveau.
BFS-algoritmen starter øverst på den første knude i grafen og kører derefter alle de tilstødende knudepunkter til den. Når alle de tilstødende noder er gennemgået, gentager algoritmen den samme procedure for underordnede noder.
Eksempel
At krydse ovennævnte graf på BFS-måde ville være resultatet af A -> B -> C -> D -> E -> F -> G. Algoritmen starter fra knudepunkt A og gennemgår alle dens tilstødende knudepunkter B, C og D. Den markerer alle de fire noder som besøgt. Når alle de tilstødende knudepunkter i A er krydset, bevæger algoritmen sig til den første tilstødende knude til A og gentager den samme procedure. I dette tilfælde er knudepunktet B, og de tilstødende knudepunkter til B er E og F. Dernæst krydses de tilstødende knudepunkter til C. Når alle noder er besøgt, afsluttes operationen.
4. Dybde første søgning (DFS)
Dybde Første søgning eller DFS gennemgår grafen lodret. Det starter med rodnoden eller den første knude på grafen og gennemgår alle underordnede knudepunkter, før de flyttes til de tilstødende knudepunkter.
Eksempel
At krydse ovennævnte graf på BFS-måde ville være resultatet af A -> B -> E -> F -> C -> G -> D. Algoritmen starter fra knudepunkt A og gennemgår alle dens underordnede knudepunkter. Så snart det støder på B, ser det ud til, at det har yderligere underordnede knudepunkter. Så krydses barneknudepunkterne af B inden de går videre til den næste barneknudepunkt A.
Virkelig implementering af grafer
- Design af elektriske kredsløb til kraftoverførsel.
- Design af netværk af sammenkoblede computere.
- Undersøgelse af molekylær, kemisk og cellulær struktur af ethvert stof, f.eks. Humant DNA.
- Design af transportruter mellem byer og steder i en by.
Konklusion - Graf i datastruktur
Grafer er et meget nyttigt koncept i datastrukturer. Det har praktiske implementeringer på næsten ethvert felt. Det er meget vigtigt at forstå det grundlæggende i grafteori, at udvikle en forståelse af algoritmerne i grafstrukturen.
Denne artikel var blot en introduktion til grafer. Det er bare et springbræt. Det anbefales at dybe dykket videre i emnet grafteori.
Anbefalede artikler
Dette er en guide til grafen i datastruktur. Her diskuterer vi terminologier og grundlæggende operationer af graf i datastruktur. Du kan også se på den følgende artikel for at lære mere -
- Spørgsmål om datastrukturinterview
- Datamodel i Cassandra
- Hvad er Data Mart?
- Hvad er en datavidenskabsmand?