Algoritmu meklēšana grafos

Grafu attēlošana
Grafs sastāv no divām netukšām kopām – viena satur virsotnes, bet otra šķautnes - grafs G = (V, E) (V – virsotņu kopa, E – šķautņu kopa). Pastāv divi standarta veidi kā aprakstīt grafu: ar blakus virsotņu saraksta vai ar blakus virsotņu matricas palīdzību. Blakus virsotņu sarakstu parasti lieto biežāk tāpēc, ka tas nodrošina iespēju kompakti aprakstīt izretinātu grafu – tas ir tāds grafs kur |E| ir daudz mazāks par |V²|. Blakus virsotņu matricas izmantošana grafa aprakstīšanai var būt piemērota tad, kad grafs ir blīvs, proti |E| skaits ir tuvs |V²| skaitam, vai arī tad, kad ir vajadzība ātri noskaidrot vai divas virsotnes ir savā starpā savienotas ar šķautni.
1. att. Divi veidi kā aprakstīt neorientētu grafu. (a) Grafs G sastāv no piecām virsotnēm un septiņām šķautnēm. (b) Grafs G aprakstīts ar blakus virsotņu saraksta palīdzību. (c) Grafs G ir aprakstīts ar blakus virsotņu matricu. 2. att. Divi veidi kā orientētu grafu. (a) Grafs G sastāv no sešām virsotnēm un astoņām šķautnēm. (b) Grafs G aprakstīts ar blakus virsotņu saraksta palīdzību. (c) Grafs G ir aprakstīts ar blakus virsotņu matricu.
Saistīto virsotņu saraksts kas apraksta kādu grafu G = (V,E) sastāv no kopas Adj, kas satur |V| virsotņu sarakstu. Sarakstā ir tik rindas cik ir virsotņu grafā. Priekš katras virsotnes u ∈ V saistīto virsotņu saraksts Adj[u] satur visas virsotnes ar kurām virsotne ir saistīta ar lokiem. Virsotnes blakus virsotņu sarakstā parasti izvieto patvaļīgā kartībā. Attēlā 1(b) ir redzams blakus virsotņu saraksts neorientētam grafam no attēla 1(a). Respektīvi attēlā 2(b) arī redzams blakus virsotņu saraksts orientētam grafam no attēla 2(a).…