Stromy vyjadřují nějakou hierarchii vztahů. Velice obecným prostředkem pro modelování vztahů mezi prvky jsou grafy. Prvky jsou vrcholy grafu a vztahy mezi nimi vyjadřujeme jejich spojením - hranami. Příkladem může být graf počítačové sítě CESNET na obr.
. Města jsou vrcholy a hrany znázorňují jejich spojení komunikačními linkami. Grafy nemusí znázorňovat jenom prostorové vztahy, ale například i časové, logické ap.
Formálně je graf dvojice G = (V, H), kde V je množina vrcholů (uzlů) a H je množina hran, přičemž hrana je dvojice (u,v) u,vÎV. Počet vrcholů grafu G pak je |V| a počet jeho hran je |H|. Množinu vrcholů grafu G budeme zapisovat V(G) a množinu jeho hran H(G).
Platí-li (u,v) ≠ (v,u) je hrana orientovaná, tj. má začáteční a koncový vrchol. Takový graf nazýváme orientovaný a jsou v nich možné hrany z vrcholu do téhož vrcholu. Příklad orientovaného grafu je na obr.
. Pro tento graf je
V = { 1, 2, 3, 4, 5, 6 } |V| = 6
H = { (1,2) (1,6) (2,5) (3,5) (4,4) (5,6) (6,2) } |H| = 7
Stupeň vrcholu orientovaného grafu je dán součtem počtu hran do něj vstupujících a počtu hran z něj vystupujících. Například stupeň vrcholu 2 na obr. je 3.
V opačném případě (u,v) = (v,u) a graf se nazývá neorientovaný, přičemž budeme požadovat u ≠ v. Příklad neorientovaného grafu je na obr.
. Pro tento graf je
V = { 1, 2, 3, 4, 5, 6 } |V| = 6
H = { (1,2), (1,6), (2,3), (2,5), (2,6), (3,5), (5,6) } |H| = 7
V neorientovaném grafu je stupeň vrcholu dán počtem incidentních hran, tj. hran, kterých je vrchol součástí. Například stupeň vrcholu 2 na obr. je 4.
Dva standardní způsoby v informatice pro reprezentaci grafu jsou
Oba způsoby jsou použitelné pro orientované i neorientované grafy.
Pro každý vrchol grafu G = (V, H) je vytvořen seznam sousedů. Seznam sousedů pro vrchol u Î V obsahuje všechny vrcholy v, pro které je (u,v)ÎH. Sousedící vrcholy jsou obecně uloženy v seznamech v libovolném pořadí.
Příklad reprezentace orientovaného grafu z obr. seznamy sousednosti je na obr.
. Celková délka seznamů sousednosti pro orientovaný graf je zřejmě |H|.
Příklad reprezentace neorientovaného grafu z obr. seznamy sousednosti je na obr.
. Celková délka seznamů sousednosti pro orientovaný graf je zřejmě 2|H|, protože je-li hrana (u,v)Î H, potom v je v seznamu sousedů u a u je v seznamu sousedů v. Požadovaná velikost paměti tedy v obou případech je Θ(|V| + |H|).
Implementace reprezentace grafu seznamy sousednosti potom bude tvořena polem vrcholy, kterého prvky reprezentují vrcholy grafu.
Vrchol[ ] vrcholy = new Vrchol [|V|];
V objektech třídy Vrchol jsou uložena data vrcholu a ukazatel sousedi. Tento obsahuje odkaz na prvního souseda seznamu sousedů anebo null, když vrchol nemá sousedy.
class Vrchol {
...
Soused sousedi;
Vrchol ( ) {
...
sousedi = null;
}
}
Objekty třídy Soused obsahují číslo vrcholu, tj. jeho index v poli vrcholy, a ukazatel dalsi na dalšího souseda.
class Soused {
int vrchol;
Soused dalsi;
Soused (int v) {
...
vrchol = v;
dalsi = null;
}
}
Hrany grafu pak budou vytvářeny metodou hrana( ) tak, že vytvoříme objekt třídy Soused obsahující vrchol, do kterého hrana vede a vložíme ho do seznamu sousedů vrcholu, z kterého hrana vychází.
void hrana(int z, int kam) {
Soused s = new Soused(kam);
s.dalsi = vrcholy[z].sousedi;
vrcholy[z].sousedi = s;
}
Poznamenejme, že vzhledem k tomu, že jsme řekli, že na pořadí sousedů v jejich seznamu nezáleží, sousedy vkládáme přímo na začátek jejich seznamu.
Reprezentace seznamem sousednosti je vhodná i pro ohodnocené grafy. Ohodnocením grafu G se nazývá funkce
w: H(G) -> R
Je-li (u,v)ÎH(G), w(u,v) se uloží ve vrcholu v seznamu sousedů vrcholu u. Příkladem může být ohodnocení hran reprezentujících počítačovou síť přenosovými rychlostmi.
Potenciální nevýhodou reprezentace grafu seznamy sousednosti je zjišťování existence hrany (u,v), což znamená hledat vrchol v v seznamu sousedů vrcholu u.
Označme vrcholy čísly 1, …, |V|. Matice sousednosti je matice S = (sij ), i,j = 1, …, |V|, přičemž
je-li (i,j)ÎH, sij = 1
jinak sij = 0
Reprezentace orientovaného grafu z obr. maticí sousednosti je na obr.
a reprezentace neorientovaného grafu z obr. maticí sousednosti je na obr.
. Požadovaná paměť je Θ( |V |2), bez ohledu na počet hran. Pro neorientovaný graf je S = ST, kde ST je transponovaná matice, což umožňuje snížit nároky na paměť téměř na polovinu.
Další možností snížení nároků na paměť pro orientovaný i neorientovaný graf je uložení matice sousednosti v bitech, což však vyžaduje bitové operace.
Graf je při reprezentaci maticí sousednosti implementován dvourozměrným polem
int[ ][ ] s = new int [|V|] [|V|];
Maticí sousednosti lze implementovat i ohodnocený graf. Pro ohodnocený graf je
suv = w(u,v), je-li (u,v)ÎH(G),
suv je hodnota mimo hodnot možných ohodnocení, není-li (u,v)ÎH(G).
Je-li |H| << |V|2 graf se nazývá řídký a obvykle je vhodnější použít seznam sousednosti. Je-li |H| ~ |V|2 graf se nazývá hustý a obvykle je vhodnější použít matici sousednosti. Matici sousednosti je vhodnější použít také, je-li nutno rychle zjistit existenci hrany.