Vad är diagram inom datavetenskap och vad används de för? I lekmän villkor helst.
Jag har läst definitionen på Wikipedia :
Inom datavetenskap är en graf en abstrakt datatyp som är avsedd att implementera grafen och hypergrafbegrepp från matematik.
En grafdatastruktur består av en ändlig (och möjligen förändrad ) uppsättning ordnade par, kallade kanter eller bågar, av vissa enheter som kallas noder eller hörn. Som i matematik sägs en kant (x, y) peka eller gå från x till y. Noderna kan vara en del av grafstrukturen eller kan vara externa enheter representerade av heltalindex eller referenser.
men jag letar efter en mindre formell, lättare att förstå definition.
Kommentarer
- Menar du diagram datastrukturen?
- Ja, tyvärr. Grafer som beskrivs här en.wikipedia.org/wiki/Graph_(abstract_data_type) , bara jag ’ jag letar efter en mindre formell, lättare att förstå definition.
- @ Justin984 Wikipedia länkar med parenteser (och det finns så många av dem) fungerar inte ’, parenteserna fungerar inte ’ spelar inte bra med Markdown-format för länkar. Nu, för framtida referens, lägg till eventuella förtydliganden i din fråga i själva frågan, inte i kommentarer, de är ’ t som är synliga och det ’ är lätt att sakna dem. Jag ’ Redigerar ovanstående kommentar i frågan …
- @ Justin984 Observera också att Datavetenskap Stack Exchange kan vara lite mer lämpligt för frågor som den här än programmerare. Missförstå inte ’, frågan är perfekt om ämnet här, och det fick fantastiska svar, men det skulle inte ’ göra ont om du kollade ut en grupp som ’ var lite mer fokuserad på grundläggande datavetenskapliga begrepp än vi är (don ’ t posta samma fråga i men om du råkar lägga upp den på fel webbplats kan vi flytta den automatiskt till den rätta.
Svar
Ett perfekt lekmannas exempel kan vara Facebook . Nätverket för dig, dina vänner och deras vänner etc kallas kollektivt sociala diagram .
I denna ”graf” anses människor noder i diagrammet och
kanter är vänskapslänkar .
I Facebook vän är ett dubbelriktat förhållande (A är B ”s vän => B är A” s vän) så grafen är en Oriktad graf . Ett nätverk som Google+ eller Twitter betraktas som en Riktad graf eftersom riktningen för förhållandet har betydelse här.
Alla dessa grafer kallas cykliska grafer, eftersom förhållandena mellan noder kan bilda cykler . En Familjeträd är å andra sidan en speciell typ av diagram som bland annat är Acyklisk eftersom det inte kan finnas cykler i släktträdsförhållande. (Det kallas tekniskt en Riktad acyklisk graf (DAG) eftersom den är både riktad och acyklisk)
Detta bör täcka alla grundläggande jargong med grafer, så nu ska du kunna följa resten av materialet i fältet.
Kommentarer
- Kan ’ inte tro att det inte ’ t förekommer mig att det ’ kallas Facebook-grafen API. Bra exempel!
- Släktträd inte cykliskt? Det borde inte vara ’, men tyvärr är det …
- @MarjanVenema, släktträdet är cykliskt ? (Det ’ är en riktad graf, så riktningen är viktig för att bestämma cykler och förmodligen stegförhållanden inte ’ räknas inte riktigt.)
- @dbaupp: Jag har ingen önskan att gå in på detaljer här, så jag ’ Jag nämner bara en word: incest.
- @MarjanVenema, du ’ saknar min poäng.En cykel i en riktad graf är ett mönster som
A -> B -> C -> A(dvs. en cirkel av pilar), incest ger baraA -> B -> CochA -> D -> C(dvs. en diamant). En cykel i ett släktträd behöver tidsresor.
Svar
Grafer är ett av de viktigaste matematiska begreppen används inom datavetenskap.
Du har sett grafer många gånger. Tänk dig att du flyger från en stad till en annan. Du kommer oundvikligen att hitta en fin blank tidning från flygbolaget i sätet fickan framför dig. Nära baksidan av den tidskriften kan du nästan alltid hitta en karta som visar städerna betjänade av det flygbolaget representerade som cirklar, med flygningarna som förbinder dessa städer representerade som böjda linjer. Det är ett diagram! Städerna, representerade som cirklar, är noderna i denna graf och flygningarna, representerade som böjda linjer, är kanterna. Grafer är bara saker med noder och kanter som förbinder noder.
Du kan försköna de enkla graferna på olika sätt. Du vill inte se bara ett gäng cirklar och linjer när du tittar på kartan. Dessa städer har namn. Märkning av dessa städer resulterar i märkt diagram. (Du kan också märk kanterna, t.ex. flyg 1234.) Datavetenskap associerar ofta data med noderna, ibland med kanterna, men det är bara en förlängning av etiketten. Det är fortfarande ett märkt diagram. En annan utsmyckning blir om du kan flyga direkt från stad A till stad B, men inte från stad B till stad A. Ett uppenbart sätt att skildra detta är att placera en pil på linjen som förbinder städerna för att skildra detta envägsförhållande. Nu har du en riktad graf.
Länkade listor, träd, tillståndsövergångsdiagram och många andra datavetenskapliga datastrukturer är alla exempel på grafer. Det är en mycket kraftfull koncept.
Kommentarer
- Jag ’ Jag utökar faktiskt exemplet för att notera att alla enheter som beskrivs i ditt exempel kan avbildas som hörn i en graf (stad, plan, tidskrift, karta, etc), själva kartan är bara en enda topp.
Svar
En bättre fråga skulle vara ”Vad används inte grafer för?”. Datavetenskap är i många avseenden studier av grafer.
En graf, i lekmän, är en samling godtyckliga abstrakta objekt som kallas ”noder” eller ”vertices” som representerar kopplingspunkter. De ansluts sedan via ”banor” eller ”kanter”. Den abstrakta datatypen ”Graf” är en implementering av den matematiska ”Grafen. Så i princip har du noder och kanter som dina fält och olika operationer du kan utföra på dem. Du kan till exempel lägga till en ny nod i grafens samling (detta kan vara en lista eller en array eller någon annan struktur beroende på språk). Du kan sedan länka den noden till befintliga noder. Operationer skulle också innefatta att korsa diagrammet, kontrollera om två noder delar en kant (är anslutna), hämta värden från noder eller kanter och radera noder eller kanter från diagrammet.
Så långt som användning går, grafer används överallt. Nätverk använder dem särskilt hårt men de finns i artificiell intelligens, datautvinning, spelutveckling, geoinformatik och en mängd andra discipliner. I formell datavetenskap ser de ännu mer användning, nämligen som ett sätt att representera tillstånd.
Effektivt kan allt som du kan representera som en uppsättning anslutningar representeras som en graf och implementeras via den ADT i vissa form.
Här är ett exempel på en grafik som jag gjorde:
Svar
En graf är bara en samling objekt som är sammankopplade med linjer som kallas vertices.
Termen ”diagram” är en abstraktion och generalisering av många datastrukturer som används vid mjukvaruutveckling. Länkade listor, binära träd och AST ”s är alla grafer.
I grund och botten är alla samlingar av objekt som har pekare som associerar objekten med varandra är en graf. När du har en graf kan du tillämpa principerna för grafteori för att lösa vissa problem .