Hvad er grafer inden for datalogi, og hvad bruges de til? I lægmænds termer helst.
Jeg har læst definitionen på Wikipedia :
I datalogi er en graf en abstrakt datatype, der er beregnet til at implementere grafen og hypergrafkoncepter fra matematik.
En grafdatastruktur består af en endelig (og muligvis ændret ) sæt af ordnede par, kaldet kanter eller buer, af bestemte enheder kaldet noder eller hjørner. Som i matematik siges en kant (x, y) at pege eller gå fra x til y. Knudepunkterne kan være en del af grafstrukturen eller kan være eksterne enheder repræsenteret af heltal indekser eller referencer.
men jeg leder efter en mindre formel, lettere at forstå definition.
Kommentarer
- Mener du grafer datastrukturen?
- Ja, undskyld. Grafer som beskrevet her da.wikipedia.org/wiki/Graph_(abstract_data_type) , kun jeg ‘ jeg leder efter en mindre formel, lettere at forstå definition.
- @ Justin984 Wikipedia linker med parenteser (og der er så mange af dem) fungerer ikke ‘, parenteserne fungerer ikke ‘ t spiller godt med Markdown-formatet for links. Nu, til fremtidig reference, bedes du tilføje afklaringer til dit spørgsmål i selve spørgsmålet, ikke i kommentarer, de er ‘ t der er synlige, og det ‘ er let at gå glip af dem. Jeg ‘ Jeg redigerer din kommentar ovenfor i spørgsmålet …
- @ Justin984 Bemærk også, at Computer Science Stack Exchange kan være lidt mere passende til spørgsmål som denne end programmører. Gør mig ikke forkert, spørgsmålet er perfekt om emnet her, og det fik gode svar, men det ville ikke ‘ ikke gøre ondt, hvis du ikke ‘ du tjekkede et fællesskab, der ‘ er lidt mere fokuseret på centrale computervidenskabelige koncepter, end vi er (don ‘ t post det samme spørgsmål i flere steder, men hvis du tilfældigvis sender det på det forkerte sted, kan vi automatisk flytte det til det rigtige).
Svar
Et perfekt lægmandss eksempel kan være Facebook . Netværket for dig, dine venner og deres venner osv. betegnes kollektivt som social graf .
I denne “graf” betragtes mennesker noder i grafen og
kanter er venskabslink .
I Facebook er ven et tovejsforhold (A er Bs ven => B er As ven), så grafen er en Ikke-omdirigeret graf . Et netværk som Google+ eller Twitter betragtes som et Dirigeret graf , da forholdet i retning her har betydning.
Alle disse grafer kaldes cykliske grafer, da forholdet mellem knudepunkter kan danne cykler . En Family Tree er på den anden side en speciel slags graf, der blandt andet er Acyklisk da der ikke kan være cyklusser i familietræsforhold. (Det kaldes teknisk en Directed Acyclic Graph (DAG) da den både er rettet og acyklisk)
Dette skal dække alt det grundlæggende jargon, der involverer grafer, så nu skal du kunne følge resten af materialet i marken.
Kommentarer
- Kan ‘ ikke tro det ikke ‘ t forekommer mig, at det ‘ kaldes facebook-grafen api. Godt eksempel!
- Stamtræ ikke cyklisk? Det burde ikke være ‘, men det er desværre …
- @MarjanVenema, stamtræet er cyklisk ? (Det ‘ er en rettet graf, så retningen er vigtig ved bestemmelse af cyklusser, og formodentlig trinforhold don ‘ tæller virkelig ikke.)
- @dbaupp: Jeg har ikke lyst til at gå i detaljer her, så jeg ‘ Jeg nævner bare en word: incest.
- @MarjanVenema, du ‘ mangler mit punkt.En cyklus i en rettet graf er et mønster som
A -> B -> C -> A(dvs. en cirkel med pile), incest giver bareA -> B -> CogA -> D -> C(dvs. en diamant). En cyklus i et stamtræ har brug for tidsrejser.
Svar
Grafer er et af de vigtigste matematiske begreber brugt inden for datalogi.
Du har set grafer mange gange. Forestil dig at du tager en flyflyvning fra en by til en anden. Du vil uundgåeligt finde et dejligt blankt magasin fra flyselskabet i sædet lommen foran dig. Tæt på bagsiden af dette magasin kan du næsten altid finde et kort, der viser de byer, der betjenes af det pågældende flyselskab, repræsenteret som cirkler, med flyvningerne, der forbinder disse byer, repræsenteret som buede linjer. Det “en graf! Byerne, der er repræsenteret som cirkler, er knudepunkterne i denne graf, og flyvningerne, der er repræsenteret som buede linjer, er kanterne. Grafer er bare ting med noder og kanter, der forbinder noder.
Du kan pynte disse enkle grafer på forskellige måder. Du vil ikke bare se en masse cirkler og linjer, når du ser på kortet. Disse byer har navne. Mærkning af disse byer resulterer i en mærket graf. (Du kan også mærk kanterne, f.eks. flyvning 1234.) Datalogi forbinder ofte data med knudepunkterne, nogle gange med kanterne, men det er bare en udvidelse af etiketten. Det er stadig en mærket graf. En anden udsmykning er resultatet, hvis du kan flyve direkte fra by A til by B, men ikke fra by B til by A. En åbenbar måde at skildre dette på er at placere en pil på linjen, der forbinder byerne for at skildre dette envejsforhold. Nu har du en rettet graf.
Sammenkædede lister, træer, tilstandsovergangsdiagrammer og mange andre datalogiske datastrukturer er alle eksempler på grafer. Det er en meget kraftig koncept.
Kommentarer
- I ‘ d udvider faktisk dette eksempel for at bemærke, at alle enheder, der er beskrevet i dit eksempel, kan afbildes som hjørner i en graf (by, plan, magasin, kort osv.), hvor selve kortet kun er et enkelt hjørne.
Svar
Et bedre spørgsmål ville være “Hvad bruges ikke grafer til?”. Datalogi er i mange henseender studiet af grafer.
En graf i lægmænds termer er en samling af vilkårlige abstrakte objekter kaldet “noder” eller “hjørner”, der repræsenterer forbindelsespunkter. De forbindes derefter via “stier” eller “kanter”. Den abstrakte datatype “Graf” er en implementering af den matematiske “Graf”. Så dybest set har du noder og kanter som dine felter og forskellige operationer, du kan udføre på dem. kan for eksempel tilføje en ny node til grafens samling (dette kan være en liste eller et array eller en anden struktur afhængigt af sproget). Du kan derefter linke den node til eksisterende noder. Operationer vil også omfatte gennemkørsel af grafen, kontrol af om to noder deler en kant (er forbundet), hentning af værdier fra noder eller kanter og sletning af noder eller kanter fra grafen.
For så vidt som udnyttelse går, grafer bruges overalt. Netværk gør særlig brug af dem, men de findes i kunstig intelligens, dataudvinding, spiludvikling, geoinformatik og en række andre discipliner. I formel datalogi ser de endnu mere brug, nemlig som en måde at repræsentere tilstand på.
Effektivt kan alt, hvad du kan repræsentere som et sæt forbindelser, repræsenteres som en graf og implementeres via den ADT i nogle form.
Her er et eksempel på en grafik, jeg lavede:
Svar
En graf er bare en samling af objekter, der er forbundet sammen med linjer kaldet hjørner.
Udtrykket “graf” er en abstraktion og generalisering af mange datastrukturer, der bruges til softwareudvikling. Sammenkædede lister, binære træer og AST “s er alle grafer.
Dybest set er enhver samling af objekter, der har markører, der forbinder objekterne med hinanden, er en graf. Når du har en graf, kan du anvende principperne for grafteori på den for at løse visse problemer .