Grafdatastrukturopplæring
En node i en graf kalles en toppunkt (flertall - hjørner). Noen ganger kalles det fortsatt en node; Det kan også kalles et punkt. En lenke i en graf kalles en kant. Noen ganger kalles det fortsatt en lenke; Det kan også kalles en linje.
Graf med mange funksjoner
Denne figuren viser en graf med mange funksjoner:
Sirklene (disker) er toppunktene. Enhver rett linje eller buet linje eller sløyfe er en kant.
Funksjoner i grafen
Toppunkt
Et toppunkt er et objekt. Det kan være et hus; det kan være en person; Det kan være et abstrakt substantiv; det kan være et hvilket som helst objekt du kan tenke på.
Kant
En kant er en tilkobling (forhold) mellom to hjørner; forbindelsen kan være abstrakt.
Løkke
En sløyfe er en kant som kobler et toppunkt for seg selv.
Pilkanten
Tenk på to personer: John og Peter. Hvis John låner ut Peter $ 100, og hvis John og Peter er hjørner, vil utlånskanten peke mot Peter. Hvis begge partnerne glemmer at Peter skyldes John, og Peter låner ut John $ 100, vil i den andre enden av samme kant, en pilspiss peke mot John. Hvis Peter lånte ut men $ 75 til John og ikke $ 100, ville en annen kant koble Peter til John. Denne andre kanten vil ha pilspissen som peker mot John. I det andre tilfellet er det to kanter, med en pilspiss hver, og peker i motsatte retninger.
Vertexen som en kant peker på, er et toppunkt for den kanten. Toppunktet som en kant forlater fra, er en haler.
hendelse
En kant kobler to hjørner. Kanten sies å være hendelse på begge toppunkt. Kanten trenger ikke å ha et pilspiss. De to toppunktene er kjent som kantenes endepunkter. Det er mulig å ha en graf der et toppunkt ikke tilhører noen kant, men det vil ikke bli vurdert i denne opplæringen.
Ikke rettet graf
En kant kan være en pil, eller den kan ikke. En graf der ingen kant er en pil er en rettet graf. En kant kan være representert med en rett linje eller en kurve eller en sløyfe.
Regissert graf
En graf der hver kant er en pil (retning) er en rettet graf. En pilkant kan være representert med en rett linje med et pilspiss eller en kurve med pilspiss eller en løkke med pilspiss.
Fraværet av en retning på kanten av en rettet graf, betyr hver kant av den rettede grafen, er toveis.
Grad av et toppunkt
Antallet kanter som er hendelsen på et toppunkt er graden av toppunktet. En sløyfe har to forekomster på et toppunkt, så en sløyfe telles to ganger.
Rekkefølgen på en graf
Rekkefølgen på en graf er antall hjørner i grafen.
Multigraph
En multigraph er en graf, hvor det for noen par hjørner er mer enn en kanter. En rettet multigraph er en slik graf der kantene ikke har veibeskrivelse (er ikke piler). En rettet multigraph er en der hver kant er en pil, og for par hjørner som har mer enn en pil, er den ene toppunktet halen til disse pilene, og den andre toppunktet er hodet til de samme pilene. Følgende diagram viser en rettet multigraph:
Mer enn en kanter (jeg.e. flere kanter) for et par hjørner kalles også parallelle kanter.
Dirrende
En dirrende er en multigraph som tillater løkker (en eller flere løkker). Noen multigrafer tillater ikke løkker.
Enkel graf
En enkel graf er en graf der ingen to par hjørner har flere kanter. Løkker er ikke tillatt i en enkel graf.
Tom graf
En tom graf er en graf uten toppunkter og så ingen kanter.
Blandet graf
En blandet graf er en graf der noen kanter er piler, og andre ikke er det; Med andre ord: Noen kanter har veibeskrivelse, og andre er ikke rettet.
Vektet graf
Det er mulig å ha en graf der et tall, kjent som vekt, blir tildelt hver kant. Noen kanter har samme tall, men tallene er generelt forskjellige. En slik graf kalles en vektet graf. Tallene for en bestemt graf kan representere lengder eller kostnader (priser) eller størrelsen av noe slag, avhengig av problemet.
Indegree og outdegree
Vocabulary, indegree og outdegreree er kun aktuelt for en rettet graf. Grafen er kanskje ikke en multigraph. Grafen har kanskje ikke løkker.
Antall pilspisser koblet til et toppunkt er indreveringen av det toppunktet. En pil med en enkelt pilspiss har en hodeenden og en haleenden. Antall haler som er koblet til et toppunkt, er overgrepet av det toppunktet.
Merk: En graf med flere kanter for parets hjørner, der flere kanter er i motsatte retninger, ikke blir adressert i denne opplæringen.
Programvarerepresentasjon av en graf
En graf kan være representert i programvare slik den tegnes på diagrammet. En graf kan også være representert i programvare av en matematisk matrise (todimensjonal matrise). En av slike matriser kalles adjacency matrix.
Adjacency matrix
En adjacency matrix er en firkantet matrise. Overskriftene for radene er alle toppunktene, skrevet i stigende rekkefølge. Overskriftene for kolonnene er fremdeles de samme toppunktene, skrevet i stigende rekkefølge. Telling av radene eller kolonnene i en matrise begynner fra 1 og ikke null som med matriser. Når du identifiserer et element i en matrise, skrives radnummeret først før kolonnummeret.
For en rettet graf er hver oppføring (element) i adjacency -matrisen antallet kanter som forbinder de to tilsvarende toppunktene. En sløyfe bør telles to ganger. For en rettet graf er hver oppføring i adjacency -matrisen enten antallet kanter som etterlater en rad i rad og legger inn den tilsvarende kolonnehåren eller er antallet kanter som etterlater en kolonneutvikling og legger inn tilsvarende rad toppunkt. Valget er programmereren. I denne situasjonen (begge tilfeller), bør en sløyfe fortsatt telles en gang.
Merk: En graf er et diagram er en datastruktur i seg selv. En adjacency -matrise er også en datastruktur i seg selv.
Ikke rettet graf og adjacency matrix
Følgende diagrammer viser en rettet graf og den tilsvarende adjacency -matrisen:
Den ledende diagonalen til en matrise er diagonalen fra topp til venstre til høyre til høyre. En rettet matrise er symmetrisk om den ledende diagonalen. Matrixoppføringen for rad A og kolonne C er 1, noe som betyr at det er en kant som forbinder Vertex A og Vertex C. Matriksoppføringen for rad C og kolonne B er 3, noe som betyr at det er 3 kanter som forbinder toppunkt C og Vertex B. De andre oppføringene er på samme måte forklart.
Summen av oppføringene for en rad gir antall kanter (grad) for tilsvarende toppunkt. Summen av oppføringene for rad A er 2, noe som betyr at 2 kanter er koblet til toppunkt a. Summen av oppføringene for rad B er 6, noe som betyr at 6 kanter er koblet til toppunkt B. Resten av oppføringene er på samme måte forklart.
Regissert graf og adjacency matrix
Følgende diagrammer viser en rettet graf og den tilsvarende adjacency -matrisen:
Adjacency -matrisen for en rettet graf er ikke nødvendigvis symmetrisk om den ledende diagonalen. Matriksoppføringen for rad A og kolonne C er 1, noe som betyr at den ene kanten forlater fra toppunkt A til Vertex C. Matriksoppføringen for rad C og kolonne B er 3, noe som betyr at 3 kanter lar fra toppunkt C til toppunkt B. De andre oppføringene er på samme måte forklart.
Summen av oppføringene for en kolonne gir indrever for (kolonnen) toppunktet. Summen av oppføringene for en rad gir outdegree for (rad) toppunkt. Summen av oppføringene for kolonne A er 1, noe som betyr at en kant er rettet til toppunkt a. Summen av oppføringene for rad B er 2, noe som betyr at 2 kanter går fra toppunkt B. Resten av oppføringene er på samme måte forklart.
Grafoperasjoner
En datastruktur, for eksempel en graf, består av et sett med dataverdier eller et sett med objekter, pluss forholdet mellom objektene, pluss operasjonene (funksjonene) mellom objektene. Forholdene i en graf indikeres av kantene. Videre til det skal en graf ha minst følgende operasjoner:
tilstøtende (g, x, y)
G betyr graf. Denne operasjonen verifiserer om en kant kobler toppunkt X og Vertex y. Verdien og plasseringen av en oppføring i en matrise indikerer tilkobling av en kant (og dens type).
naboer (g, x)
Denne operasjonen returnerer en liste over alle toppunktene som er direkte koblet til toppunktet x. Verdien og plasseringen av en oppføring i en matrise indikerer tilkobling av en kant.
remove_vertex (g, x)
Denne operasjonen fjerner et toppunkt, x fra en graf. Hvis toppunktet ikke hadde noen kant, er det ikke noe problem. Imidlertid, hvis toppunktet hadde lenker, bør koblingene (kantene) også fjernes. Verdien og plasseringen av en oppføring i en matrise indikerer tilstedeværelsen av et bestemt toppunkt. Hvis et toppunkt fjernes, må matrisen justeres.
add_vertex (g, x)
Dette legger til et toppunkt, x uten å legge til kanter, eller erstatter et toppunkt som hadde kanter, men som hadde blitt fjernet. Verdien og plasseringen av en oppføring i en matrise indikerer tilstedeværelsen av et bestemt toppunkt. Hvis det legges til et toppunkt, må matrisen justeres.
add_edge (g, x, y)
Denne operasjonen tilfører en ny kant mellom toppunktet X og toppunktet Y hvis kanten ikke var der. Verdien og plasseringen av en oppføring i en matrise indikerer tilstedeværelsen av en bestemt kant. Hvis en kant legges til, må matrisen justeres.
Fjern_edge (g, x, y)
Denne operasjonen ville fjerne kanten mellom toppunktet X og toppunktet Y hvis kanten var der. Verdien og plasseringen av en oppføring i en matrise indikerer tilstedeværelsen av en bestemt kant. Hvis en kant fjernes, må matrisen justeres.
Get_Vertex_Value (G, X)
Denne operasjonen returnerer verdien, V tilknyttet toppunktet, x. For å oppnå dette, trenger du et strømsett med undergrupper for toppunktetiketter og deres verdier.
set_vertex_value (g, x, v)
Denne operasjonen gir en ny verdi, v for verdien tilknyttet toppunktet, x. For å oppnå dette, trenger du et strømsett med undergrupper for toppunktetiketter og deres verdier.
Noen grafer knytter også verdier til kantene. Slike grafer trenger følgende tilleggsoperasjoner:
get_edge_value (g, x, y)
Denne operasjonen returnerer verdien, v forbundet med kanten, (x, y). For å oppnå dette, trenger du et strømsett med undergrupper for kanter og deres verdier.
set_edge_value (g, x, y, v)
Denne operasjonen gir en ny verdi, v for verdien som er tilknyttet kanten, (x, y). For å oppnå dette, trenger du et strømsett med undergrupper for kanter og deres verdier.
Konklusjon
En graf er et sett med hjørner forbundet med kanter. En graf kan bli rettet eller rettet. Kantene kan være ikke-retnings eller retningsbestemt. Løkker kan være til stede eller fraværende i en graf. Hva du bør lære neste er satt, strømsett og multisett relatert til grafer. Etter det bør du lære de forskjellige graferstypene, for eksempel en orientert graf, vanlig graf, komplett graf, bipartittgraf, turneringsgraf, flyt nettverksgraf, etc.
Chrys