Режа: Асосий тушунчалар ва граф турлари Графларни ифодалаш усуллари Графларни кўрувдан ўтказиш

Қўшма матрица ;

Муносабат матрицаси;

Қўшнилик рўйхати;

Қирралар рўйхати;

G – граф
V – тугунлар
E – қирралар(ёйлар, оғирлик)
n = |V| – тугунлар сони
m = |E| – қирралар сони.
G графнинг қўшма матрицаси бу n ўлчамли А квадрат матрица бўлиб,
ЙЎНАЛТИРИЛМАГАН ГРАФ УЧУН:
Aij = 1 агар i ва j тугунлар ёйлар билан бирлаштирилган бўлса
Aij = 0 агар i ва j тугунлар бирлаштирилмаган.
G графнинг муносабат матрицаси бу n сатр(тугунлар) ва m устунлар(қирралар) дан ташкил топган В матрица бўлиб, унда:
ЙЎНАЛТИРИЛМАГАН ГРАФ УЧУН:
B_ij = 1 агар i тугун j қирра билан тўқнашган бўлса
B_ij = 0 агар i тугун j қирра билан тўқнашмаган бўлса

ЙЎНАЛТИРИЛГАН ГРАФ УЧУН :

B_ij = -1 агар i тугун j ёйнинг боши бўлса
B_ij = 0 агар i тугун j ёй билан тўқнашмаган бўлса
B_ij = 1 агар i тугун j ёйнинг охири бўлса
Қўшнилик рўйхати (қўшни тугунлар) (adjacency list) – бу A[n] массив бўлиб, A[i] хар бир элементи i тугун билан қўшни узеллар рўйхатини ўзида сақлайди.
Ёйлар рўйхати (edges list) – қўшни узеллар ёйларидан иборат чизиқли рўйхатдир.
Графларни кўрикдан ўтказиш
Графни кўрикдан ўтказиш (Graph traversal) – бу берилган тугундан бошлаб барча тугунларни кўриб чиқиш процедурасидир.
Иккита усули мавжуд:
Тубига қараб(Depth-First Search – DFS)
Энига қараб(Breadth-First Search – BFS)
Бу усуллар берилган V тугундан бошлаб биронта контейнерни қўллаган холда барча тугунларни кўриб чиқади.
Тубига қараб кўришда стек қўлланилади.
Энига қараб кўришда навбат ишлатилади.