Grafem skierowanym nazywamy strukturę G = (V,E) składającą się ze zbioru wierzchołków V (węzłów) oraz zbioru krawędzi E (łuków). Formalnie, krawędź jest uporządkowaną parą wierzchołków (v,w).
W grafie nieskierowanym (v,w) = (w,v)

Reprezentacja grafów:

• macierz sąsiedztwa A (tablica dwuwymiarowa)

  • jeżeli istnieje krawędź od wierzchołka i-tego do wierzchołka j-tego, wtedy A[i][j] = 1; w przeciwnym razie A[i][j] = 0.

• tablice sąsiedztwa TS

  • każdemu wierzchołkowi v jest przypisana tablica zawierająca sąsiadujące z nim wierzchołki

Podstawowe operacje na grafach:

• visit(v) - odwiedzanie (wykonywane pewnej czynności) wierzchołka v

• sasiedzi(v) - pobranie wszystkich wierzchołków sąsiadujących z wierzcholkiem v; iterowanie po wszystkich sąsiadach wierzchołka v: "for w in sąsiedzi(v) do ..."

Przechodzenie grafu:

• w głąb (dfs depth-first-search)

• wszerz (bfs breadth-first-search)

Przeszukiwanie w głąb:
http://www.cs.hut.fi/Research/TRAKLA2/exercises/DFS.html

Przeszukiwanie wszerz:
http://www.cs.hut.fi/Research/TRAKLA2/exercises/BFS.html