Introduktion till diagram i datastruktur
Grafer är icke-linjära datastrukturer innefattande en ändlig uppsättning noder och kanter. Noderna är elementen och kanterna är ordnade par av förbindelser mellan noderna.
Lägg märke till ordet icke-linjärt. En icke-linjär datastruktur är en där elementen inte är arrangerade i sekvensordning. Till exempel är en matris en linjär datastruktur eftersom elementen är ordnade efter varandra. Du kan korsa alla element i en matris i en enda körning. Detta är inte fallet med icke-linjära datastrukturer. Elementen i en icke-linjär datastruktur är arrangerade i flera nivåer, ofta efter ett hierarkiskt mönster. Grafer är icke-linjära.
Nästa ord att uppmärksamma är ändligt. Vi definierar grafen för att ha ett begränsat och räknat antal noder. Detta är en ganska okomplicerad term. I huvudsak kan en graf ha ett oändligt antal noder och fortfarande vara begränsat. Till exempel ett släktträd som sträcker sig tillbaka till Adam och Eva. Detta är en relativt oändlig graf men är fortfarande räknbar och anses därför vara begränsad.
Real-World Exempel
Det bästa exemplet på grafer i den verkliga världen är Facebook. Varje person på Facebook är en nod och är ansluten till kanterna. A är en vän till B. B är en vän till C och så vidare.
terminologier
Här är Terminologierna i diagrammet i datastruktur som nämns nedan
1. Grafrepresentation: Generellt representeras en graf som ett par uppsättningar (V, E). V är uppsättningen av hörn eller noder. E är uppsättningen Edges. I exemplet ovan,
V = (A, B, C, D, E)
E = (AB, AC, AD, BE, CD, DE)
2. Nod eller toppunkt: Elementen i en graf är anslutna genom kanterna.
3. Kanter: En bana eller en linje mellan två vertikaler i en graf.
4. Intilliggande noder: Två noder kallas intill varandra om de är anslutna genom en kant. I exemplet ovan är nod A intill noderna B, C och D, men inte till nod E.
5. Sökväg: Bana är en sekvens av kanter mellan två noder. Det är i huvudsak en genomgång som börjar vid en nod och slutar på en annan. I exemplet ovan finns det flera vägar från nod A till nod E.
Sökväg (A, E) = (AB, BE)
ELLER
Bana (A, E) = (AC, CD, DE)
ELLER
Bana (A, E) = (AD, DE)
6. Odirigerad graf: En riktad graf är en där kanterna inte anger en viss riktning. Kanterna är i två riktningar.
Exempel
I detta exempel kan kanten AC korsas från både A till C och C till A. Liknande alla kanter. En väg från nod B till nod C skulle vara antingen (BA, AC) eller (BD, DC).
7. Riktad graf: En riktad graf är en där kanterna bara kan korsas i en specifik riktning.
Exempel
Således, i samma exempel, är nu kanterna riktade. Du kan bara korsa kanten längs dess riktning. Det finns ingen väg från nod B till nod C nu.
8. Vägt graf: En vägd graf är en där kanterna är associerade med en vikt. Detta är i allmänhet kostnaden för att korsa kanten.
Exempel
I samma exempel har nu kanterna en viss vikt förbunden med dem. Det finns två möjliga vägar mellan nod A till nod E.
Bana 1 = (AB, BD, DE), vikt1 = 3 + 2 + 5 = 10
Bana2 = (AC, CD, DE), vikt2 = 1 + 3 + 5 = 9
Det är uppenbart att man föredrar väg 2 om målet är att nå nod E från nod A med lägsta kostnad.
Grundläggande operationer på graf
Här är de grundläggande operationerna i grafen som nämns nedan
1. Lägg till / ta bort Vertex
Detta är den enklaste operationen i diagrammet. Du lägger helt enkelt till ett toppunkt i en graf. Det behöver inte anslutas till något annat toppunkt genom en kant. När du tar bort ett toppunkt måste du ta bort alla kanter som kommer från och slutar vid det borttagna toppmaterialet.
2. Lägg till / ta bort kant
Denna operation lägger till eller tar bort en kant mellan två toppar. När alla kanter som härstammar från och slutar vid ett toppunkt tas bort blir toppunktet ett isolerat toppunkt.
3. Breadth-First Search (BFS)
Detta är en genomgångsoperation i diagrammet. BFS går horisontellt över grafen. Detta innebär att den går över alla noder på en enda nivå innan du fortsätter till nästa nivå.
BFS-algoritmen börjar högst upp i den första noden i diagrammet och korsar sedan alla angränsande noder till den. När alla angränsande noder har korsats upprepar algoritmen samma procedur för underordnade noder.
Exempel
Att korsa diagrammet ovan på BFS-sätt skulle resultera från A -> B -> C -> D -> E -> F -> G. Algoritmen börjar från nod A och korsar alla dess angränsande noder B, C och D. Den markerar alla fyra noder som besökts. När alla de angränsande noderna för A har passerat, flyttar algoritmen till den första angränsande noden i A och upprepar samma procedur. I detta fall är noden B och de angränsande noderna till B är E och F. Därefter går de angränsande noderna till C. När alla noder har besökt avslutas operationen.
4. Djup första sökning (DFS)
Djup första sökning eller DFS går igenom diagrammet vertikalt. Det börjar med rotnoden eller den första noden i diagrammet och korsar alla underordnade noder innan de flyttas till de angränsande noderna.
Exempel
Att korsa diagrammet ovan på BFS-sätt skulle resultera från A -> B -> E -> F -> C -> G -> D. Algoritmen startar från nod A och korsar alla dess barnnoder. Så snart det möter B verkar det som om det har ytterligare barnnoder. Så, barnnoderna i B går igenom innan de fortsätter till nästa barnnod för A.
Real-World Implementations of Grafer
- Design av elektriska kretsar för kraftöverföring.
- Design av nätverk av sammankopplade datorer.
- Studie av molekylär, kemisk och cellulär struktur för vilket ämne som helst, t.ex. mänskligt DNA.
- Design av transportvägar mellan städer och platser i en stad.
Slutsats - Diagram i datastruktur
Grafer är ett mycket användbart koncept i datastrukturer. Det har praktiska implementationer på nästan alla områden. Det är mycket viktigt att förstå grunderna i grafteori, att utveckla en förståelse för algoritmerna i grafstrukturen.
Denna artikel var bara en introduktion till grafer. Det är bara en springbricka. Det rekommenderas att djupdyka ytterligare i ämnet grafteori.
Rekommenderade artiklar
Detta är en guide till diagrammet i datastruktur. Här diskuterar vi terminologier och grundläggande funktioner för graf i datastruktur. Du kan också titta på följande artikel för att lära dig mer -
- Informationsstrukturintervjufrågor
- Datamodell i Cassandra
- Vad är Data Mart?
- Vad är en datavetare?