Hva er grafer, innen informatikk, og hva brukes de til? I lekmannsbetegnelser helst.
Jeg har lest definisjonen på Wikipedia :
I datavitenskap er en graf en abstrakt datatype som er ment å implementere grafen og hypergrafkonseptene fra matematikk.
En grafdatastruktur består av en endelig (og muligens foranderlig ) sett med ordnede par, kalt kanter eller buer, av visse enheter som kalles noder eller hjørner. Som i matematikk, sies en kant (x, y) å peke eller gå fra x til y. Nodene kan være en del av grafstrukturen , eller kan være eksterne enheter representert av heltallindekser eller referanser.
men jeg ser etter en mindre formell, lettere å forstå definisjon.
Kommentarer
- Mener du grafer datastrukturen?
- Ja, beklager. Grafer som beskrevet her en.wikipedia.org/wiki/Graph_(abstract_data_type) , bare jeg ‘ jeg ser etter en mindre formell, lettere å forstå definisjon.
- @ Justin984 Wikipedia lenker med parenteser (og det er så mange av dem) fungerer ikke ‘, parentesene fungerer ikke ‘ t spiller bra med Markdown-formatet for lenker. Nå, for fremtidig referanse, vennligst legg til noen avklaringer til spørsmålet ditt i selve spørsmålet, ikke i kommentarer, de er ‘ t som er synlige og det ‘ er lett å savne dem. Jeg ‘ Jeg vil redigere kommentaren ovenfor i spørsmålet …
- @ Justin984 Vær også oppmerksom på at Datavitenskap Stack Exchange kan være litt mer passende for spørsmål som denne enn programmerere. Ikke misforstå ‘, spørsmålet er perfekt om temaet her, og det fikk gode svar, men det ville ikke ‘ ikke skadet hvis du sjekket ut et fellesskap som ‘ var litt mer fokusert på kjernevitenskapelige begreper enn vi er (ikke ‘ t legg ut det samme spørsmålet i flere nettsteder skjønt, hvis du tilfeldigvis legger det ut på feil nettsted, kan vi flytte det til det rette automatisk.
Svar
Et perfekt lekmannes eksempel kan være Facebook . Nettverket til deg, vennene dine og vennene deres osv. blir samlet referert til som sosiale graf .
I denne «grafen» blir folk betraktet som noder i grafen og
kanter er vennskapskoblinger .
På Facebook er venn et toveis forhold (A er B «s venn => B er en» venn) så grafen er en Udirigert graf . Et nettverk som Google+ eller Twitter vil bli betraktet som et Regissert graf siden retningen på forholdet har betydning her.
Alle disse grafene blir referert til som sykliske grafer, da forholdet mellom noder kan danne sykluser . Et Slektstre er derimot en spesiell slags graf som blant annet er Syklisk siden det ikke kan være sykluser i slektstreforholdet. (Det kalles teknisk Regissert syklisk graf (DAG) siden det både er rettet og acyklisk)
Dette skal dekke alt grunnleggende sjargong som involverer grafer, så nå skal du kunne følge resten av materialet i feltet.
Kommentarer
- Kan ‘ ikke tro at det ikke ‘ t forekommer meg at det ‘ s kalte facebookgrafen api. Godt eksempel!
- Stamtre ikke syklisk? Det burde ikke være ‘, men det er dessverre …
- @MarjanVenema, familietreet er syklisk ? (Det ‘ er en rettet graf, så retningen er viktig for å bestemme sykluser, og antageligvis ikke trinnforhold ‘ teller ikke virkelig.)
- @dbaupp: Jeg har ikke noe ønske om å gå i detaljer her, så jeg ‘ Jeg nevner bare en word: incest.
- @MarjanVenema, du ‘ mangler poenget mitt.En syklus i en rettet graf er et mønster som
A -> B -> C -> A(dvs. en sirkel av piler), incest gir bareA -> B -> CogA -> D -> C(dvs. en diamant). En syklus i et slektstre trenger tidsreiser.
Svar
Grafer er et av de viktigste matematiske begrepene brukt i datavitenskap.
Du har sett grafer mange ganger. Se for deg at du tar en flytur fra en by til en annen. Du vil uunngåelig finne et fint blankt magasin fra flyselskapet i setet lommen foran deg. Nær baksiden av det magasinet kan du nesten alltid finne et kart som viser byene som betjenes av det flyselskapet, representert som sirkler, med flyvningene som forbinder byene representert som buede linjer. Det er en graf! Byene, representert som sirkler, er nodene i denne grafen, og flyene, representert som buede linjer, er kantene. Grafer er bare ting med noder og kanter som forbinder noder.
Du kan pynte de enkle grafene på forskjellige måter. Du vil ikke se bare en haug med sirkler og linjer når du ser på det kartet. Disse byene har navn. Merking av byene resulterer i merket graf. (Du kan også merk kantene, f.eks. fly 1234.) Informatikk knytter ofte data til nodene, noen ganger med kantene, men det er bare en utvidelse av etiketten. Det er fremdeles en merket graf. En annen utsmykning resulterer hvis du kan fly direkte fra by A til by B, men ikke fra by B til by A. En åpenbar måte å skildre dette på er å sette en pil på linjen som forbinder byene for å skildre dette enveisforholdet. Nå har du en rettet graf.
Koblede lister, trær, tilstandsovergangsdiagrammer og mange andre datavitenskapelige datastrukturer er alle eksempler på grafer. Det er en veldig kraftig konsept.
Kommentarer
- Jeg ‘ Jeg utvider faktisk eksemplet for å merke seg at alle enheter som er beskrevet i eksemplet ditt, kan bli avbildet som hjørner i en graf (by, fly, magasin, kart osv.), Kartet i seg selv er bare et enkelt toppunkt.
Svar
Et bedre spørsmål vil være «Hva brukes ikke grafer til?». Datavitenskap er i mange henseender studiet av grafer.
En graf, i lekmanns termer, er en samling av vilkårlige abstrakte objekter kalt «noder» eller «hjørner» som representerer forbindelsespunkter. De blir deretter koblet sammen via «baner» eller «kanter». Den abstrakte datatypen «Graf» er en implementering av den matematiske «Grafen. Så i utgangspunktet har du noder og kanter som felt og forskjellige operasjoner du kan utføre på dem. Du kan for eksempel legge til en ny node i grafsamlingen (dette kan være en liste eller en matrise eller annen struktur avhengig av språk). Du kan da koble den noden til eksisterende noder. Operasjoner vil også være å krysse grafen, kontrollere om to noder deler en kant (er koblet sammen), hente verdier fra noder eller kanter, og sletting av noder eller kanter fra grafen.
Så langt som bruk går, grafer brukes overalt. Nettverk bruker spesielt mye av dem, men de finnes i kunstig intelligens, datautvinning, spillutvikling, geoinformatikk og en rekke andre fagområder. I formell datavitenskap ser de enda mer bruk, nemlig som en måte å representere tilstand på.
Effektivt kan alt du kan representere som et sett med forbindelser bli representert som en graf og implementert via den ADT i noen skjema.
Her er et eksempel på grafikk jeg laget:
Svar
En graf er bare en samling objekter som er koblet sammen med linjer som kalles hjørner.
Begrepet «graf» er en abstraksjon og generalisering av mange datastrukturer som brukes i programvareutvikling. Koblede lister, binære trær og AST «s er alle grafer.
I utgangspunktet er enhver samling objekter som har pekere som knytter objektene til hverandre er en graf. Når du har en graf, kan du bruke prinsippene til grafteori på den, for å løse visse problemer .