Jakie są wykresy w kategoriach laików?

Co to są wykresy w informatyce i do czego służą? W kategoriach laików najlepiej.

Przeczytałem definicję na Wikipedii :

W informatyce wykres jest abstrakcyjnym typem danych, który ma zaimplementować pojęcia matematyczne oparte na grafie i hiperrafacie.

Struktura danych wykresu składa się ze skończonego (i prawdopodobnie zmiennego) zestawu uporządkowanych par, zwanych krawędziami lub łukami, pewnych bytów zwanych węzłami lub wierzchołkami. Podobnie jak w matematyce, krawędź (x, y) mówi się, że wskazuje lub przechodzi od x do y. Węzły mogą być częścią struktury grafu lub mogą być podmiotami zewnętrznymi reprezentowanymi przez indeksy lub odwołania całkowite.

ale szukam mniej formalnej, łatwiejszej do zrozumienia definicji.

Doskonałym przykładem laika może być Facebook . Sieć twoich, twoich przyjaciół i ich przyjaciół itp. Jest wspólnie określana jako wykres społecznościowy .

Na tym „wykresie” ludzie są uważani za węzły wykresu, a krawędzie są łączami przyjaźni .

Na Facebooku przyjaciel jest dwukierunkowym związkiem (A jest przyjacielem B => B jest przyjacielem A), więc wykres jest wykresem niekierowanym . Sieć taka jak Google+ czy Twitter byłaby uważana za Graf Kierunkowy, ponieważ kierunek relacji ma tutaj znaczenie.

Wszystkie te wykresy są określane jako wykresy cykliczne , ponieważ relacje między węzłami mogą tworzyć cykle. Z kolei drzewo genealogiczne jest szczególnym rodzajem wykresu, który między innymi jest acykliczny, ponieważ w relacjach drzewa genealogicznego nie może być cykli. (Jest technicznie nazywany Directed Acyclic Graph (DAG), ponieważ jest zarówno ukierunkowany, jak i acykliczny)

Powinno to obejmować wszystkie podstawowe żargony obejmujące wykresy, więc teraz powinieneś być w stanie śledzić resztę materiału w terenie.

Wykresy są jedną z najważniejszych pojęć matematycznych stosowanych w informatyce.

Widziałeś wykresy wiele razy. Wyobraź sobie, że lecisz samolotem z jednego miasta do drugiego. Nieuchronnie znajdziesz ładny błyszczący magazyn od linii lotniczej w kieszeni przed sobą. Na końcu tego czasopisma 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ą przedstawiane jako zakrzywione linie. To jest wykres! Miasta, reprezentowane jako koła, są węzłami tego wykresu, a loty, reprezentowane jako linie zakrzywione, są krawędziami. Wykresy to tylko 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 kółek i linii, patrząc na tę mapę. Te miasta mają nazwy. Oznaczenie tych miast wynikiem jest oznaczony wykres. (Można również oznaczyć krawędzie, np. Lot 1234.) Informatyka często kojarzy dane z węzłami, czasami z krawędziami, ale to tylko rozszerzenie etykiety. To wciąż jest oznaczony wykres. Kolejne upiększenie występuje, jeśli możesz lecieć bezpośrednio z miasta A do miasta B, ale nie z miasta B do miasta A. Oczywistym sposobem na przedstawienie tego jest umieszczenie strzałki na linii łączącej miasta, aby przedstawić tę relację jednokierunkową. Teraz masz ukierunkowany wykres.

Połączone listy, drzewa, diagramy zmian stanów i wiele innych struktur danych informatycznych to przykłady grafów. To bardzo potężna koncepcja.

Lepszym pytaniem byłoby „Do czego nie używa się wykresów?”. Informatyka jest pod wieloma względami studium grafów.

Wykres, w kategoriach laików, to zbiór dowolnych obiektów abstrakcyjnych zwanych „węzłami” lub „wierzchołkami”, które reprezentują punkty połączenia. Są one następnie łączone za pomocą „ścieżek” lub „krawędzi”. Abstrakcyjny typ danych „Graph” jest implementacją matematycznego „Graph”. Zasadniczo masz więc węzły i krawędzie jako swoje pola i różne operacje, które możesz na nich wykonywać. Możesz 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ż przemierzanie wykresu, sprawdzanie, czy dwa węzły dzielą 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.

Jeśli chodzi o wykorzystanie, wykresy są używane w dowolnym miejscu. Networking wykorzystuje 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, a mianowicie sposób reprezentowania państwa.

W efekcie wszystko, co możesz reprezentować jako zestaw połączeń, może być reprezentowane jako wykres i zaimplementowane za pośrednictwem tego narzędzia ADT w jakiejś formie.

Oto przykładowa grafika, którą wykonałem:

Wykres to tylko zbiór obiektów połączonych ze sobą liniami zwanymi wierzchołkami.

Termin „wykres” jest abstrakcją i uogólnieniem wielu struktur danych wykorzystywanych w tworzeniu oprogramowania. Połączone listy, drzewa binarne i AST to wykresy.

Zasadniczo każda kolekcja obiektów, która ma wskaźniki, które kojarzą te obiekty ze sobą, jest wykresem. Gdy masz już wykres, możesz zastosować do niego zasady teorii grafów , aby rozwiązać niektóre problemy .