Co to są wykresy w informatyce i do czego są używane dla? Najlepiej używając terminów laików.
Przeczytałem definicję w Wikipedii :
W informatyce wykres jest abstrakcyjnym typem danych, który ma zaimplementować graf i hipergraph pojęcia z matematyki.
Grafowa struktura danych składa się ze skończonego (i prawdopodobnie zmiennego ) zbiór uporządkowanych par, zwanych krawędziami lub łukami, pewnych obiektów zwanych węzłami lub wierzchołkami. Podobnie jak w matematyce, mówi się, że krawędź (x, y) wskazuje lub biegnie od x do y. Węzły mogą być częścią struktury grafu lub mogą to być jednostki zewnętrzne reprezentowane przez indeksy lub odwołania w postaci liczb całkowitych.
, ale szukam mniej formalnej, łatwiejszej do zrozumienia definicji.
Komentarze
- Czy masz na myśli wykresy struktury danych?
- Tak, przepraszam. Wykresy opisane tutaj en.wikipedia.org/wiki/Graph_(abstract_data_type) , tylko ja ' szukam mniej formalna, łatwiejsza do zrozumienia definicja.
- @ Justin984 Linki do Wikipedii z nawiasami (a jest ich tak dużo) nie działają ', nawiasy nie działają ' Nie graj dobrze z formatem Markdown dla linków. Teraz, na przyszłość, dodaj wyjaśnienia do pytania w samym pytaniu, a nie w komentarzach, nie są one ' t widoczne i ' łatwo je przeoczyć. ' edytuję Twój powyższy komentarz w pytaniu …
- @ Justin984 Zwróć też uwagę, że Informatyka Wymiana stosów może być nieco bardziej odpowiednia w przypadku takich pytań niż programiści. Nie ' nie zrozum mnie źle, pytanie jest tutaj idealnie na temat i ma świetne odpowiedzi, ale nie ' nie zaszkodzi, jeśli odwiedziłeś społeczność, która ' trochę bardziej skupia się na podstawowych koncepcjach informatycznych niż my (nie ' nie publikuj tego samego pytania jednak w wielu witrynach, jeśli zdarzy się, że opublikujesz go w niewłaściwej witrynie, możemy automatycznie przenieść go na właściwą).
Odpowiedź
Idealnym przykładem laika może być Facebook . Sieć zawierająca Ciebie, Twoich znajomych i ich znajomi itp. są określani zbiorczo jako wykres społeczny .
Na tym „wykresie” osoby są uważane za węzły wykresu i
krawędzie to linki przyjaźni .
Na Facebooku przyjaciel jest relacją dwukierunkową (A to przyjaciel B „=> B to przyjaciel A”), więc wykres jest Niekierowany wykres . Sieć taka jak Google+ czy Twitter byłaby uznawana za Wykres skierowany , ponieważ kierunek relacji ma tutaj znaczenie.
Wszystkie te wykresy są określane jako cykliczne wykresy, ponieważ relacje między węzłami mogą tworzyć cykle . Z drugiej strony Drzewo genealogiczne jest specjalnym rodzajem wykresu, którym jest między innymi Acykliczny , ponieważ w relacjach drzewa genealogicznego nie może być cykli. (Technicznie nazywa się to Skierowanym grafem acyklicznym (DAG) , ponieważ jest skierowany i acykliczny)
Powinno to obejmować cały podstawowy żargon dotyczący wykresów, więc teraz powinieneś być w stanie prześledzić resztę materiału w tej dziedzinie.
Komentarze
- Czy ' nie sądzę, że nie ' t przyszło mi do głowy, że ' nazywa się interfejsem facebook Graph API. Dobry przykład!
- Drzewo genealogiczne nie jest cykliczne? Nie powinno być ', ale niestety jest …
- @MarjanVenema, drzewo genealogiczne to cykliczne ? (To ' jest ukierunkowanym wykresem, więc kierunek jest ważny przy określaniu cykli i przypuszczalnie krokowych relacji nie ' naprawdę się liczę.)
- @dbaupp: Nie chcę tu wchodzić w szczegóły, więc ' wspomnę tylko o jednym słowo: kazirodztwo.
- @MarjanVenema, ' nie rozumiesz.Cykl na wykresie skierowanym to wzór taki jak
A -> B -> C -> A(tj. Okrąg strzałek), kazirodztwo daje po prostuA -> B -> CiA -> D -> C(czyli diament). Cykl w drzewie genealogicznym wymaga podróży w czasie.
Odpowiedź
Wykresy to jedno z najważniejszych pojęć matematycznych używany w informatyce.
Wiele razy widziałeś wykresy. Wyobraź sobie, że lecisz samolotem z jednego miasta do drugiego. Nieuchronnie znajdziesz ładny błyszczący magazyn linii lotniczych na siedzeniu kieszeń przed tobą. Na końcu tego magazynu prawie zawsze można znaleźć mapę przedstawiającą miasta obsługiwane przez tę linię lotniczą w postaci okręgów, a loty łączące te miasta są przedstawione jako zakrzywione linie. To „sa wykres!” Miasta przedstawione jako okręgi to węzły tego wykresu, a loty, przedstawione jako zakrzywione linie, to krawędzie. Wykresy to po prostu rzeczy z węzłami i krawędziami, które łączą węzły.
Możesz upiększyć te proste wykresy na różne sposoby. Nie chcesz widzieć tylko kilku okręgów i linii, gdy patrzysz na tę mapę. Te miasta mają nazwy. Oznaczanie tych miast skutkuje oznaczonym wykresem. (Możesz też oznacz krawędzie, np. lot 1234.) Informatyka często wiąże dane z węzłami, czasem z krawędziami, ale to tylko rozszerzenie etykiety. To nadal jest oznaczony wykres. Kolejną ozdobą jest to, że możesz latać bezpośrednio z miasta A do miasta B, ale nie z miasta B do miasta A. Oczywistym sposobem na zobrazowanie tego jest umieszczenie strzałki na linii łączącej miasta aby przedstawić tę jednokierunkową zależność. Teraz masz skierowany wykres.
Połączone listy, drzewa, diagramy przejść stanów i wiele innych informatycznych struktur danych to przykłady wykresów. Jest to bardzo potężny koncepcja.
Komentarze
- I ' d faktycznie rozszerzam ten przykład, aby zauważyć, że wszystkie elementy opisane w twoim przykładzie mogą być przedstawione jako wierzchołki na wykresie (miasto, samolot, magazyn, mapa itp.), a sama mapa jest po prostu pojedynczym wierzchołkiem.
Odpowiedź
Lepszym pytaniem byłoby „Do czego nie są używane wykresy t?”. Informatyka jest pod wieloma względami nauką o grafach.
Graf, używając terminologii laików, to zbiór dowolnych abstrakcyjnych obiektów zwanych „węzłami” lub „wierzchołkami”, które reprezentują punkty połączenia. Są one następnie połączone za pomocą „ścieżek” lub „krawędzi”. Abstrakcyjny typ danych „Wykres” jest implementacją matematycznego „Wykresu”. Tak więc w zasadzie masz węzły i krawędzie jako pola i różne operacje, które możesz na nich wykonywać. może na przykład dodać nowy węzeł do kolekcji wykresu (może to być lista, tablica lub inna struktura w zależności od języka). Następnie możesz połączyć ten węzeł z istniejącymi węzłami. Operacje obejmowałyby również przechodzenie przez wykres, sprawdzanie, czy dwa węzły mają wspólną krawędź (są połączone), pobieranie wartości z węzłów lub krawędzi oraz usuwanie węzłów lub krawędzi z wykresu.
O ile wykorzystanie idzie, wykresy są używane w każdym miejscu. Sieci wykorzystują je szczególnie intensywnie, ale można je znaleźć w sztucznej inteligencji, eksploracji danych, tworzeniu gier, geoinformatyce i wielu innych dyscyplinach. W formalnej informatyce widzą jeszcze większe zastosowanie, mianowicie jako sposób reprezentowania stanu.
W rzeczywistości wszystko, co możesz przedstawić jako zestaw połączeń, może być reprezentowane jako wykres i zaimplementowane za pośrednictwem tego ADT w niektórych formularz.
Oto przykładowa grafika, którą wykonałem:
Odpowiedź
Graf to po prostu zbiór obiektów połączonych ze sobą liniami zwanymi wierzchołkami.
Termin „wykres” to abstrakcja i uogólnienie wielu struktury danych używane w tworzeniu oprogramowania. Połączone listy, drzewa binarne i AST „ to wykresy.
Zasadniczo każdy zbiór obiektów, ma wskaźniki, które wiążą ze sobą obiekty, to wykres. Gdy masz już wykres, możesz zastosować do niego zasady teorii grafów , aby rozwiązać pewne problemy .