Grafalgoritmusok: grafok bejarasa, útmatrix, legrövidebb utak matrixanak meghatarozasa.

Gráfalgoritmusok: gráfok bejárása, útmátrix, legrövidebb utak mátrixának meghatározása.

Gráfok és alkalmazásaik

G=(V,E) egyszerû gráf (irányított), V = m

A csomópontok rendezettek: v₁,v₂,v₃, ...... ,v_m

Szomszédsági mátrix: A=(a_ij) szomszédsági mátrixa G-nek, ha a_ij=0, ha minden v_i v_j él és                    a_ij=0 különben.

Példa

v₁ v₃                     242d32c                      242d32c            0 1 1 1

                     242d32c                      242d32c                      242d32c                 A= 0 0 0 0

                     242d32c                      242d32c                      242d32c                      242d32c      0 0 0 1

v₂ v₄                     242d32c                      242d32c            0 0 1 0

Tétel A a G gráf szomszédsági mátrixa. A²:= A*A, A³:=A*A*A ..., A_k:=(a_k(i,j)). Ekkor a_k(i,j) egyenlõ a v_i-bõl v_j-be vezetõ k hosszúságú utak számával.

Példa

A2= 0 0 1 1                     242d32c   v₁ v₄ v₃

0 0 0 0

0 0 1 0

0 0 0 1

Útmátrix: P=(p_ij) mátrix a G irányított gráf útmátrixa, ha p_ij=1, ha minden v_i-bõl v_j-be út és p_ij=0 különben.

Tétel: p_ij=1 Û ha B_m=A+A²+A³+....+A^m mátrix (i,j)-ik eleme ¹ 0, ahol A a G gráf szomszédsági mátrixa, m a csúcsok száma.

Példa

                     242d32c         v₂                0 1 1                     242d32c    0 0 1                     242d32c      0 0 0

v₁                      242d32c              A= 0 0 1 A²= 0 0 0 A³= 0 0 0

                     242d32c         v₃                0 0 0                     242d32c    0 0 0                     242d32c      0 0 0

                     242d32c         0 1 2                     242d32c                      242d32c                     0 1 1 Nem minden elem

B₂=A+A²+A³= 0 0 1 Összesen kétféle módon P= 0 0 1 egyenlõ 1-gyel Þ

                     242d32c         0 0 0 juthatok el v₁-bõl v₃-ba! 0 0 0 nem szorosan összefüggõ!

Warshall - algoritmus

Cél: G mátrix esetén P útmátrix meghatározása.

Az algoritmus: 1. P:=A

                     242d32c         2. FOR K=1 TO M

                     242d32c                     3. FOR I=1 TO M

                     242d32c                     4. FOR J=1 TO M

                     242d32c                     P(i,j) := P(i,j) vagy (P(i,k) és P(k,j))

Példa Elõzõ

0 1 1                     242d32c           0 1 1                     242d32c      0 1 1                     242d32c      0 1 1

P:= 0 0 1 =A P₁= 0 0 1 P₂= 0 0 1 P₃= 0 0 1

0 0 0                     242d32c           0 0 0                     242d32c      0 0 0                     242d32c      0 0 0

Legrövidebb út algoritmus

(Ez az algoritmus egy módosított Warshall-algoritmus)

G súlyozott irányított gráf, W:=(w_ij) súlymátrix [w_ij = 0, ha nem létezik v_i v_j él]

Cél: Q=(q_ij) mátrix megkeresése, ahol q(i,j) az v_i v_j legrövidebb út hossza.

Jelölés: P_k(i,j):=1, ha létezik v_i v_j út csak v₁, v₂, ... ,v_k csúcsokat tartalmazza, és P_k(i,j):=0 különben.

Megjegyzés: P₀(i,j)=1, ha létezik v_i v_j él, azaz P₀=A szomszédsági mátrix. Továbbá P_m=P                      242d32c     útmátrix.

Állítás: P_k(i,j) = 1, ha

                     242d32c     - vagy P_k-1(i,j) = 1

                     242d32c     - vagy P_k-1(i,j) = 1 és P_k-1(k,j) = 1                     242d32c            v_k

                     242d32c     - vagy                      242d32c                      242d32c vagy                     242d32c     

v_i                      242d32c     v_j                     242d32c              v_i                      242d32c                      242d32c    v_j

                     242d32c                      242d32c         v₁, ... ,v_k-1 csúcsokat tartalmazó út

Azaz P_k(i,j) = P_k-1(i,j) vagy (P_k-1(i,k) és P_k-1(k,j)), ahol:

és 0 1                     242d32c                      242d32c            vagy 0 1

0 0 0                     242d32c                      242d32c               0 0 1

1 0 1                     242d32c                      242d32c               1 1 1

Jelölés: Q_k(i,j) := min(Q_k-1(i,j));Q_k-1(i,k)+Q_k-1(k,j))

v₁,...,v_k-1 csúcsokat felhasználó legrövidebb út hossza

Az algoritmus: 1. Q(i,j):=W(i,j), ha W(i,j) ¹ 0 és Q(i,j):= ¥ különben

                     242d32c         2. For K:=1 to M

                     242d32c              3. For I:=1 to M

                     242d32c                   4. For J:=1 to M

                     242d32c                      242d32c    Q(i,j):= min(Q(i,j);Q(i,k)+Q(k,j))

Példa

1 v₂                     242d32c              0 1 4                     242d32c                  ¥ 1 4

v₁ 2                     242d32c       W= 0 0 2                     242d32c      1. Q= ¥ ¥ 2

4 v₃                     242d32c              0 0 0                     242d32c                  ¥ ¥ ¥

¥ 1 4                     242d32c                  ¥ 1 3                     242d32c           ¥ 1 3

2. ¥ ¥ 2                     242d32c             3. ¥ ¥ 2                     242d32c    4. ¥ ¥ 2

¥ ¥ ¥                     242d32c                 ¥ ¥ ¥                     242d32c          ¥ ¥ ¥

v₁                     242d32c                      242d32c       v₁, v₂                     242d32c              v₁, v₂, v₃

Gráfok megvalósítása kapcsolt adatszerkezettel

Példa v₂

                     242d32c                          242d32c                      242d32c      Csúcs Szomszédsági lista

                     242d32c                      242d32c                      242d32c               v₁ v₂, v₃, v₄

v₁                      242d32c       v₃                     242d32c          v₂ v₃

                     242d32c                      242d32c                      242d32c               v₃ v₄

                     242d32c            v₄                     242d32c                   v₄

A kapcsolt adatszerkezet:

Start                     242d32c   Csúcslista                     242d32c     Éllista

                     242d32c         v₁                      242d32c   Æ

                     242d32c                 v₂                      242d32c   Æ

                     242d32c                 v₃                      242d32c   Æ

                     242d32c                 v₄ Æ Æ

Gráfok bejárása

Keresztirányú keresés:

1. A kiindulópontot vizsgáljuk

2. A szomszédjait vizsgáljuk

3. A szomszédok szomszédjait, stb.

Megvalósítás: sor segítségével.

Jelölés: Egy csomópont státusza (ST) lehet

¾ 1 - készenléti állapot (még nem vizsgált)

¾ 2 - várakozó állapot (a sorban van)

¾ 3 - feldolgozott állapot

Az algoritmus:

1. Minden pont státusza legyen 1.

2. A kiindulópont (A) elhelyezése a sorban ST(A):=2.

3. Ismétlés, amíg a sor üres nem lesz:

4. A sor elsõ elemének (N) eltávolítása, N feldolgozása, ST(N):=3.

5. N készenléti állapotú szomszédainak hozzácsatolása a sorhoz, státuszuk 2-re

                     242d32c     változtatása.

Megjegyzés: Ha maradnak feldolgozandó pontok, melyek A-ból nem érhetõk el, egy ilyen                      242d32c     ponttal újra kell kezdeni az algoritmust.

Példa

                     242d32c                      242d32c                  A sor alakulása: ST(v₁, v₂, v₃):=

                     242d32c              v₂

v₁                      242d32c                      242d32c                 v₁ ST(v₁):=2

                     242d32c              v₃                  v₂ v₃ ST(v₁):=3 ST(v₂,v₃):=2

v₄

                     242d32c                      242d32c                      242d32c       v₃ ST(v₂):=3

                     242d32c                      242d32c                      242d32c       v₄ ST(v₃):=3

                     242d32c                      242d32c                      242d32c       ST(v₄):=3

Hosszirányú keresés:

1. A kiindulópont feldolgozása.

2. A-ból kiinduló egy P út teljes feldolgozása.

3. Visszalépés P-n

(Hasonlít a bináris fa inorder bejárásához.)

Megvalósítás: veremmel

Az algoritmus:

1. Minden csomópont státusza legyen 1.

2. A kiindulópont (A) ráhelyezése a veremre, ST(A) :=2.

3. Ismétlés, amíg a verem ki nem ürül.

4. A verem felsõ elemének (N) leemelése, N feldolgozása, ST(N):=3.

5. N készenléti állapotú szomszédainak ráhelyezése a veremre, státuszuk legyen 2.

Példa

                     242d32c                      242d32c                  ST(v₁, ... ,v₅):=1

                     242d32c              v₅ 1.                     242d32c                     2.

v₁                      242d32c                      242d32c     v₁ ST(v₁) :=2 v₅ ST(v₁):=3

                     242d32c                      242d32c                      242d32c                      242d32c                  v₄ ST(v₃,v₄,v₅):=2

                     242d32c              v_{4                     242d32c                      242d32c                      242d32c                      242d32c}                 v₃

v₂ v₃

3.                     242d32c             4.                     242d32c                5.                     242d32c                  6.

v₄ ST(v₅):=3 ST(v₄):=3                     242d32c   ST(v₃):=3                     242d32c     ST(v₂):=3

v₃                     242d32c             v₃                     242d32c              v₂

Gráfok topológiai rendezése

T.f.h. G gráf nem tartalmaz kört

Definiáljuk az alábbi a relációt: u < v, ha létezik u v út.

Állítás: a részleges rendezési reláció:

Ui.: 1. Minden v csomópontra v ³ v (nem reflexív)

2. Ha u<v, akkor v ³ u (assszimetrikus)

3. Ha u<v és v<w, akkor u<w (tranzitív)

Def.: G gráf topológiai rendezése G csúcsainak olyan lineáris sorbarendezése, melyre, ha létezik v u út G-ben azaz v<u, akkor v megelõzi u-t a sorban.

Példa                     242d32c         A

                     242d32c                                        242d32c                      242d32c      Két topológiai rendezése a gráfnak:

G                      242d32c                      242d32c                      242d32c            B D G A F E C

                     242d32c         F               E C vagy

B                      242d32c                      242d32c                      242d32c                 E G B A D F C

                     242d32c                  

                     242d32c                   D

Tétel: G véges irányított gráf, mely nem tartalmaz köröket. Ekkor G-nek létezik topológiai rendezése.

Jelölés: BE(N) : N csúcs éppen aktuális be-fokának tárolása.

Cél: G topológiai rendezése.

Megvalósítás: sor segítségével.

1. Zérus be-fokú pont megkeresése.

2. N és a hozzá tartozó élek törlése a gráfból.

Az algoritmus:

1. A G gráf minden pontjának be-fokának meghatározása.

2. A zérus be-fokú pontok elhelyezése a sorban.

3. Ismétlés, míg a sor üres nem lesz.

                     242d32c 4. Sor elsõ elemének eltávolítása (N).

                     242d32c 5. Az N pont minden M szomszédjára: BE(M):=BE(M)-1

                     242d32c Ha BE(M)=0, M hozzácsatlakozik a sorhoz.

Példa

                     242d32c         B                     242d32c          A sor alakulása: BE(A):=0 BE(B):=1

A                      242d32c                      242d32c                      242d32c                      242d32c      BE(C):=1 BE(D):=2

                     242d32c                   C

                     242d32c         D

1., A

A 2., BE(B):=1-1=0 BE(C):=1-1=0

3., B C

AB              4., C BE(D):=2-1=1

ABC           5., BE(D):=1-1=0

6., D

ABCD        7.,

a topológiai rendezés