Matematické Fórum

byk7 · 09. 10. 2013 11:12

Je dán (orientovaný) graf $G=(V,E)$ kde $|V|=n$ a $|E|=m$ (řekněme, že $n\le10^5,m\le10^6$ ).
Graf chci reprezentovat pomocí hran, řekněme, že $n=5,m=6$ a hrany jsou (vrcholy si označím čísla 1,2,...,5):

Code:

5 -> 1
2 -> 1
4 -> 2
5 -> 4
4 -> 4
5 -> 3

a chci zjistit, jestli existuje cesta z 5 do 2.
Výstup by měl být buď ano, nebo ne.

Algoritmus by měl vypadat nějak následovně:
napíšu si vrcholy, do kterých vede hrana z 5ky
1,3,4
vezmu si vrchol 1 a zjistím, že z něho žádná hrana už nevede, tj.
3,4
vezmu 3ku, nic nevede
4
ze 4ky vede hrana už pouze do 2ky,
cesta tedy existuje.

(To je tuším fronta?)

Mým problémem je, jak mám vůbec reprezentovat graf v paměti (vím, že možností je víc, zajímá mě tedy teď pokud možno ta nejjednodušší)?
A už vůbec nevím, jak pak tento algoritmus naprogramovat.

Díky za pomoc.

kexixex · 09. 10. 2013 15:37

Ahoj,

obecne by se algoritmus dal prepsat v pseudokodu nejak takhle:

VSTUP: startovni vrchol Start, cilovy vrchol Cil
VYSTUP: ano, nebo ne

alg:
0. pokud Start=Cil, return "ano" jinak jdi na 1.

1. aktualni_vrchol:=start;

2. pridej do fronty vsechny sousedy vrcholu aktualni_vrchol;
aktualni_vrchol vyrad z grafu;
Pokud je fronta prazdna, return "ne";

3. aktualni_vrchol:=prvni_prvek_fronty;

4. pokud aktualni_vrchol==cil, return "ano" jinak jdi na 2;

Takze co budes potrebovat? Za prve urcite frontu a procedury na pridani prvku a odebrani prvku. Za druhe nejakou metodu, jak najit vsechny sousedy danyho vrcholu, coz uzce souvisi s reprezentaci grafu v pameti. Nektere moznosti, jak graf reprezentovat jsou popsany zde. Otazkou je, ktera reprezentace je pro dany ucel nejlepsi. Myslim si, ze v tomhle pripade je nejvyhodnejsi seznam nasledniku, protoze jsou snadno k nalezeni vsichni sousedi urciteho vrcholu. Nakonec si budes muset nejak oznacit vrcholy, ktery uz ve fronte byly, abys je tam nepridaval vic nez jednou, coz lze jednoduse udelat treba jako pole boolu (oznacme ho P). Pak ve chvili kdy vyberes z frotny nejaky vrchol podivas se do P, jestli uz neni vyrazeny, a pokud ano, vyberes z fronty rovnou dalsi vrchol.

To je asi vsechno, co se bude hodit, a uz zbyva procedury vhodne poskladat do cyklu a podminek podle algoritmu.

Matematické Fórum

#1 09. 10. 2013 11:12

Prohledávání grafu v C/C++

Code:

#2 09. 10. 2013 15:37

Re: Prohledávání grafu v C/C++

Zápatí