Graf (ang. graph) jest powszechnie stosowaną strukturą danych we współczesnej informatyce. Pozwala on modelować wszelkiego rodzaju sieci oraz układy, w których występują skomplikowane zależności pomiędzy składnikami. Powstała cała teoria matematyczna, zwana Teorią Grafów (ang. Graph Theory), która zajmuje się tymi strukturami, ich własnościami oraz zasadami wykonywania na nich różnych działań. Za ojca grafów uważany jest Leonard Euler, szwajcarski matematyk, który dokonał bardzo wielu odkryć matematycznych, np. w rachunku różniczkowym i całkowym.

W tym artykule zaprezentujemy podstawowe algorytmy grafowe, z którymi na pewno spotkasz się na studiach informatycznych. Również zadania Olimpiady Informatycznej w dużym stopniu bazują na teorii grafów, zatem jeśli chciałbyś wziąć udział w eliminacjach, to musisz tę teorię poznać. Wbrew pozorom, nie jest to wcale aż takie trudne, ale wymaga wiele pracy.

Zapraszam do lektury.