Wat zijn grafieken in de informatica en waarvoor worden ze gebruikt voor? Bij voorkeur in lekentaal.
Ik heb de definitie gelezen op Wikipedia :
In de informatica is een grafiek een abstract gegevenstype dat bedoeld is om de grafiek- en hypergraafconcepten uit de wiskunde te implementeren.
Een grafiekgegevensstructuur bestaat uit een eindige (en mogelijk veranderlijke ) set van geordende paren, randen of bogen genaamd, van bepaalde entiteiten die knooppunten of hoekpunten worden genoemd. Net als in de wiskunde wijst een rand (x, y) naar of wijst van x naar y. De knooppunten kunnen deel uitmaken van de grafiekstructuur , of kunnen externe entiteiten zijn die worden vertegenwoordigd door gehele getallen of verwijzingen.
maar ik ben op zoek naar een minder formele, gemakkelijker te begrijpen definitie.
Reacties
- Bedoel je grafieken van de datastructuur?
- Ja, sorry. Grafieken zoals hier beschreven en.wikipedia.org/wiki/Graph_(abstract_data_type) , alleen ik ‘ ben op zoek naar een minder formele, gemakkelijker te begrijpen definitie.
- @ Justin984 Wikipedia-links met haakjes (en er zijn er zo veel) werken niet, de haakjes doneren niet ‘ ‘ spelen niet goed met de Markdown-indeling voor links. Voeg nu voor toekomstige referentie eventuele verduidelijkingen toe aan uw vraag in de vraag zelf, niet in de opmerkingen, ze zijn ‘ zo zichtbaar en het ‘ s gemakkelijk te missen. Ik ‘ bewerk je bovenstaande opmerking in de vraag …
- @ Justin984 Merk ook op dat Computerwetenschappen Stack Exchange is misschien iets geschikter voor vragen als deze dan programmeurs. Begrijp me niet verkeerd, ‘ begrijp me niet verkeerd, de vraag gaat hier perfect over het onderwerp en het kreeg goede antwoorden, maar het zou geen ‘ pijn doen als je hebt een community bezocht die ‘ iets meer gefocust is op de belangrijkste computerwetenschappelijke concepten dan wij zijn (plaats ‘ niet dezelfde vraag in meerdere sites, maar als u deze op de verkeerde site plaatst, kunnen we deze automatisch naar de juiste site verplaatsen).
Antwoord
Een perfect lekenvoorbeeld zou Facebook kunnen zijn. Het netwerk van jou, je vrienden en hun vrienden enz. worden gezamenlijk de sociale grafiek .
In deze “grafiek” worden de mensen beschouwd als knooppunten van de grafiek en de
randen zijn vriendschapslinks .
In Facebook is vriend een bidirectionele relatie (A is B “s vriend => B is A” s vriend), dus de grafiek is een Niet-gerichte grafiek . Een netwerk als Google+ of Twitter zou worden beschouwd als een Directed Graph aangezien de richting van de relatie hier betekenis heeft.
Al deze grafieken worden cyclische grafieken genoemd, omdat de relaties tussen knooppunten cycli kunnen vormen . Een Stamboom daarentegen is een speciaal soort grafiek die onder andere Acyclisch aangezien er geen cycli kunnen zijn in de stamboomrelatie. (Het wordt technisch een Directed Acyclic Graph (DAG) genoemd omdat het zowel gericht als acyclisch is)
Dit zou al het basisjargon met grafieken moeten omvatten, dus nu zou je de rest van het materiaal in het veld moeten kunnen volgen.
Reacties
- Kunnen ‘ niet geloven dat ‘ Het komt bij me op dat het ‘ de facebook graph api wordt genoemd. Goed voorbeeld!
- Stamboom niet cyclisch? Het zou niet ‘ moeten zijn, maar het is helaas …
- @MarjanVenema, de stamboom is cyclisch ? (Het ‘ is een gerichte grafiek, dus de richting is belangrijk bij het bepalen van cycli, en vermoedelijk zijn staprelaties niet ‘ telt niet echt.)
- @dbaupp: Ik heb geen zin om hier in details te treden, dus ik ‘ zal er maar één noemen word: incest.
- @MarjanVenema, je ‘ mist mijn punt.Een cyclus in een gerichte grafiek is een patroon als
A -> B -> C -> A(dwz een cirkel van pijlen), incest geeft alleenA -> B -> CenA -> D -> C(dwz een diamant). Een cyclus in een stamboom heeft tijdreizen nodig.
Antwoord
Grafieken zijn een van de belangrijkste wiskundige concepten gebruikt in de informatica.
Je hebt grafieken vaak gezien. Stel je voor dat je met het vliegtuig van de ene stad naar de andere vliegt. Je zult onvermijdelijk een mooi glossy magazine van de luchtvaartmaatschappij in de stoel vinden zak voor je. Aan de achterkant van dat tijdschrift vindt u bijna altijd een kaart met de steden die door die luchtvaartmaatschappij worden bediend, weergegeven als cirkels, met de vluchten die die steden met elkaar verbinden, weergegeven als gebogen lijnen. Dat is een grafiek! De steden, weergegeven als cirkels, zijn de knooppunten van deze grafiek en de vluchten, weergegeven als gebogen lijnen, zijn de randen. Grafieken zijn gewoon dingen met knooppunten en randen die knooppunten met elkaar verbinden.
U kunt die eenvoudige grafieken op verschillende manieren verfraaien. U wilt niet zomaar een aantal cirkels en lijnen zien als u naar die kaart kijkt. Die steden hebben namen. Als u die steden labelt, krijgt u een gelabelde grafiek. (U kunt ook label de randen, bijv. vlucht 1234.) Computerwetenschappen associëren gegevens vaak met de knooppunten, soms met de randen, maar dat is slechts een uitbreiding van het label. Het is nog steeds een gelabelde grafiek. Een andere verfraaiing is het resultaat als je rechtstreeks van stad A naar stad B kunt vliegen, maar niet van stad B naar stad A. Een voor de hand liggende manier om dit weer te geven, is door een pijl op de lijn te plaatsen die de steden met elkaar verbindt. om deze eenrichtingsrelatie weer te geven. Nu heb je een gerichte grafiek.
Gekoppelde lijsten, bomen, toestandsovergangsdiagrammen en tal van andere informatica-datastructuren zijn allemaal voorbeelden van grafieken. Het is een zeer krachtige concept.
Reacties
- Ik ‘ d eigenlijk uit dat voorbeeld om op te merken dat alle entiteiten die in uw voorbeeld worden beschreven, kunnen worden weergegeven als hoekpunten in een grafiek (stad, vlak, tijdschrift, kaart, enz.), waarbij de kaart zelf slechts één hoekpunt is.
Antwoord
Een betere vraag zou zijn “Waar worden” geen grafieken voor gebruikt? “. Computerwetenschap is in veel opzichten de studie van grafieken.
Een grafiek, in termen van leken, is een verzameling willekeurige abstracte objecten die “knooppunten” of “hoekpunten” worden genoemd en die verbindingspunten vertegenwoordigen. Ze zijn dan verbonden via “paden” of “randen”. Het abstracte gegevenstype “Graph” is een implementatie van de wiskundige “Graph”. Dus eigenlijk heb je knooppunten en randen als je velden en verschillende bewerkingen die je erop kunt uitvoeren. kan bijvoorbeeld een nieuw knooppunt aan de verzameling van de graaf toevoegen (dit kan een lijst zijn, een array of een andere structuur, afhankelijk van de taal). U kunt dat knooppunt dan aan bestaande knooppunten koppelen. Bewerkingen omvatten ook het doorlopen van de grafiek, controleren of twee knooppunten een rand delen (verbonden zijn), waarden ophalen van knooppunten of randen en het verwijderen van knooppunten of randen uit de grafiek.
Voor zover het gebruik betreft gaat, grafieken worden overal gebruikt. Netwerken maakt er bijzonder veel gebruik van, maar ze zijn te vinden in kunstmatige intelligentie, datamining, game-ontwikkeling, geo-informatica en tal van andere disciplines. In de formele informatica zien ze zelfs nog meer nut, namelijk als een manier om de staat weer te geven.
In feite kan alles wat je kunt voorstellen als een reeks verbindingen worden weergegeven als een grafiek en via die ADT worden geïmplementeerd in sommige vorm.
Hier is een voorbeeldafbeelding die ik heb gemaakt:
Antwoord
Een graaf is slechts een verzameling objecten die met elkaar zijn verbonden door lijnen die hoekpunten worden genoemd.
De term “graaf” is een abstractie en generalisatie van vele gegevensstructuren die worden gebruikt bij softwareontwikkeling. Gekoppelde lijsten, binaire bomen en AST “s zijn allemaal grafieken.
Kortom, elke verzameling objecten die heeft aanwijzers die de objecten met elkaar associëren is een grafiek. Zodra u een grafiek heeft, kunt u de principes van grafentheorie erop toepassen om bepaalde problemen op te lossen .